parsing - LR1 解析器和 Epsilon

Question

我试图了解 LR1 解析器的工作原理，但我想到了一个奇怪的问题:如果语法包含 Epsilons 怎么办？例如:如果我有语法:

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

是的，完全正确(将 epsilon 视为空白空间，其中两侧的点没有两个位置)。

在 LR(0) 自动机中，您将使状态接受并减少到 A。但是，由于 A->a A a生产，会有一个转变/减少冲突。

在 LR(1) 自动机中，您将使用前瞻(a -> shift，FOLLOW(A) -> reduce 中的任何内容)确定是移位还是减少

见 Wikipedia article