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产生，会有移位/归约冲突。

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

见维基百科文章

Answer 2

您可以使用此站点来计算： https ://cyberzhg.github.io/toolbox/lr1

查看结果：