EBNF 文法を文脈自由文法に変換

Question

JavaCUP 仕様を作成する必要があり、EBNF 文法を与えられました。ただし、この 2 つを変換する方法がわかりません。基本的な考え方は聞いたものの、何を変更する必要があるのか​​、「端子」は何になるのかなど、よくわかりません。

あるものから別のものに変換する方法を誰かが説明できますか、またはそれについて読める場所があるか?

Answer 1

EBNF 文法は通常の BNF に似ていますが、構文糖としていくつかの追加機能 (正規表現演算子と同様) が追加されています。文法を示していないので、通常の BNF に変換するにはどの部分を脱糖する必要があるか推測することしかできませんが、最も一般的なものは次のとおりです (JavaCUP のような LALR ジェネレーターの場合)。

B*    becomes Bstar, defined as Bstar ::= epsilon; Bstar ::= Bstar B
B+    becomes Bplus, defined as Bplus ::= B; Bplus ::= Bplus B
B?    becomes Bquestion, defined as Bquestion ::= epsilon; Bquestion ::= B
B | C becomes BorC, defined as BorC ::= B; BorC ::= C

の epsilon ただし、ここでの識別子はパーサージェネレーターが空の文字列を示します。