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-> 移位，FOLLOW(A)-> 减少中的任何内容）来确定是否进行移位或归约

请参阅维基百科文章