2

式を表す文法があります。簡単にするために、次のようにしましょう。

S -> E
E -> T + E | T
T -> P * T | P
P -> a | (E)

、a、+、*が私(の)アルファベットの文字です。

上記のルールは、適切な演算順序と結合規則を使用して、括弧、乗算、および加算を含む有効な算術式を生成できます。

私の目標は、私のアルファベットの文字を 0 個以上含むすべての文字列を受け入れることです。ここに私の制約があります：

  • 文法は、アルファベットの 0 文字以上を含むすべての文字列を「受け入れる」必要があります。
  • 新しい端末は、アルゴリズムによって入力に導入および挿入できます。(端末を明示的に指定するEOFと、何らかの理由で、有効な式を超える余分なトークンを検出するのに役立つことがわかりました。)
  • 新しい生産ルールが導入される場合があります。新しいルールはエラー フラグになります (つまり、文字列がエラー フラグを使用して解析された場合、文字列は受け入れられますが、意味的にはエラーと見なされます)。
  • 新たに導入された端末が挿入されるように、生産ルールが変更される場合があります。
  • 文法は、少なくとも Lex/Yacc のようなツールで処理できる LALR(1) でなければなりません (Lex/Yacc と互換性があるにもかかわらず、ダングリング else 問題は非 LALR(1) を必要とすることを思い出すと)。

さらに、さまざまな種類のエラー (2 項演算の引数の欠落、括弧の欠落 - 左または右 - 許容可能な式を超える余分なトークンなど) に対応する追加のルールが必要です。私の質問に答えて、そうでなければエラー報告には役に立たないすべての入力を「受け入れる」簡単な方法があるかもしれないからです。

これらのルールが有用であることがわかりましたが、それらが私の制約に違反しているかどうかはわかりません:

P -> @      [error]
P -> (E     [error]
S -> E $    [instead of S -> E]
S -> E X $  [error]
X -> X Y    [error]
X -> Y      [error]
Y -> a      [error]
Y -> (      [error]
Y -> )      [error]
Y -> *      [error]
Y -> +      [error]

ここ$で、 は明示的なEOFトークンで、@は空の文字列です。

私の質問が明確ではなかった場合: 制約内で文法を変更して、すべての入力を受け入れるという目標を達成するにはどうすればよいですか? ルールは目標を満たしていますか?

4

1 に答える 1