いくつかのパーサーとレクサー生成ツール (Lex と Bison に似ていますが、C# 用) を使用して、後で評価できる抽象構文ツリーに文字列を解析するプログラムを生成しています。
私はエラー回復を行いたいと思っていました (つまり、生成された抽象文ツリーで、欠落しているトークンなどがあることを報告します)。生成された文法を構造化するために 2 つのアプローチを念頭に置いていましたが、どちらのアプローチが優れているか、より柔軟であるか、または競合が発生しないか疑問に思っていました (.y および .lex ファイルは、電卓の記述に基づいて生成されます)。
電卓の説明により、ユーザーは端末/正規表現と演算子の配置、および結合性を指定できます。次のようなものです：
grammar.AddTerminal("Plus", "\\+").
AddNonTerminal(new NonTerminal("Add", Associativity.LeftToRight).
AddTerminal("Expression").
AddTerminal("Plus").
AddTerminal("Expression"));
(優先順位は、TerminalとNonTerminalが追加された順序で指定されます。"Add"は、リフレクションを介して発見されたメソッドの名前です。基本的には、抽象構文ツリーで演算子を呼び出すものを NonTerminal に伝えます。)
アプローチ 1 : (任意の式に対して空のルールを許可する)
S -> E
E -> E + T
E -> T
T -> T * P
T -> P
P -> (E)
P -> (E [error]
P -> a
P -> @ [error]
a端末です。
@空です。
アプローチ 2 : (開始ルールに空のルールのみを許可する)
S -> E
S -> @ [error]
E -> + [error]
E -> T + [error]
E -> + T [error]
E -> E + T
E -> T
T -> * [error]
T -> * P [error]
T -> P * [error]
T -> T * P
T -> P
P -> (E)
P -> (E [error]
P -> a
これは、各アプローチを使用した悪い入力の左端の導出を示す例です。
入力： (a +
アプローチ 1 :
S
E
T
P
(E
(E + T
(T + T
(P + T
(a + T
(a + P
(a +
アプローチ 2 :
S
E
T
P
(E
(T +
(P +
(a +
A -> A - Bアプローチ 2 のコーディングははるかに困難です (減算/単項負の演算子を検討してください。単純に減算を見て、最初にそれを取り出してAエラーを報告することはできません。A -> - Bこれは単項演算子に有効であるためです)。私は今朝、アプローチ 2 をコーディングしました。文法の問題があり、アプローチ 1 のように空のルールを使用すると、コードの観点から物事がはるかに単純になることがわかりましたが、私の主な関心事は、プログラマーが電卓の説明を次のように作成するときに、どのアプローチが文法の問題を最小限に抑えるかです。上で説明した。