1

私は Java でパーサー ジェネレーターを作成しました。いくつかのバンプの後 (たとえば、初期のバージョンでは左再帰が特に好きではありませんでした)、いくつかの単純な文法で動作させることができました (したがって、プロダクションが正しいことを手で確認できます)。 ) より複雑な文法を入力してみましたが、出力は LR(1) 文法ではありません (解析対象が解析テーブルの同じセルに 2 回書き込もうとしたという事実に由来します)

問題の文法は

S->aAb|SA
A->aA|e|S

とにかく、この文法はLR（1）であると確信しています。これが私のプログラムの出力です http://pastebin.com/hJNC9uuN

どんなアドバイスも非常に貴重です ありがとうございます (誰かがオートマトンと解析テーブルを出力するパーサージェネレーターを持っていれば、私はそれらに立ち向かうことができます)

4

1 に答える 1

5

この文法はあいまいなので、LR(1) にすることはできません。文字列を導出する 2 つの方法を次に示しますab。

S → aAb → ab

S → SA → aAbA → abA → ab

LR(1) セットには、実際にはシフト/リデュースの競合が含まれています。次の項目を含む State 5 を確認してください。

[A->S. { $a }]
[A->.aA { $a }]

これは shift/reduce の競合です: shift をオンaにしますか、それとも on を reduce しaますか? したがって、ツールはこの入力を正しく認識します。文法は LR(1) ではなく、LR(1) ではないことがわかります。

お役に立てれば！

于 2015-07-02T23:42:45.537 に答える