parsing - LR1 パーサーとイプシロン

Question

LR1 パーサーがどのように機能するかを理解しようとしていますが、奇妙な問題が発生しました: 文法にイプシロンが含まれている場合はどうなりますか? 例：文法がある場合：

S -> A
A -> a A | B
B -> a

開始方法は明らかです。

S -> .A
A -> .a A 
A -> .B

... 等々

しかし、私はそのような文法のためにそれを行う方法がわかりません:

S -> A
A -> a A a | \epsilon

するのは正しいですか：

S -> .A
A -> .a A a
( A -> .\epsilon )

そして、DFA でこの状態を受け入れますか?

どんな助けでも本当に感謝します！

Answer 1

はい、そのとおりです (イプシロンは、両側にドットの場所が 2 つない空のスペースと考えてください)。

LR(0) オートマトンでは、状態を受け入れて A に還元します。ただし、A->a A a生産のために、シフト/還元の競合が発生します。

LR(1) オートマトンでは、先読みを使用してシフトまたは削減するかどうかを決定します ( a-> シフト、何でもFOLLOW(A)-> 削減) 。

ウィキペディアの記事を参照してください