language-agnostic - 次の文法で左再帰を削除するにはどうすればよいですか?

Question

これは、カンマを区切り文字としてネストされた中括弧の言語を記述することになっている文法です。

L ::= {L} | L,L |

文法が受け入れて拒否することを期待する文字列の例をさらにいくつか示します。

承認：

{,{,,{,}},,{,}}
{{{{}}}}
{,{}}

拒絶：

{}{}
{,{}{}}
{{},{}

Answer 1

手で行う：

L ::= {L }| {中} ,| ,中 | ε

または、単にウィングする代わりに、より体系的なアプローチを使用して、ウィキペディアのアルゴリズムを適用して、即時の左再帰を削除することもできます。

L ::= {L }L ₁ | L ₁
L ₁ ::= ε | ,LL1 _{_}

Answer 2

まず第一に、その文法は最初の例を受け入れません。なぜなら、カンマが右中括弧の後と左中括弧の前にある必要があるからです。のように書き直すことをお勧めします。

L::= {L} | ,L

これで左再帰が取り除かれることはありませんが、少なくとも許容できる答えと一致します。