我试图了解 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 中的这个状态接受？
任何帮助将不胜感激！
我无法使用包含 epsilon 产生式的语法为 LR(1) 解析器构建项目集的集合。例如，给定以下语法（其中 eps 代表 epsilon）
S -> a S U
U -> b
| eps
State0 将是
S' -> .S, $
S -> .a S U, $
从 State0 移动 'a' 将给出以下状态，我们称之为 State2
S -> a .S U, $
S -> .a S U, $/???
为了对 State2 的第二项进行前瞻，我需要计算 FIRST(U$)。我知道 FIRST(U) = {'b', eps}。我的第一个问题是：State2 的第二项的前瞻是 $ 和 'b'？由于 U 可以是 eps，我的大脑告诉我，我也可以将 $ 作为前瞻，而不仅仅是 'b'。如果 FIRST(U) 只是 {'b'}，它就只是 'b'。那是对的吗？
第二个问题：在某些时候，我会有一个状态如下
S -> a S .U, $
U -> .b, …我用Java编写了一个解析器生成器,经过几次颠簸(例如早期版本并不特别喜欢左递归),我设法让它与一些简单的语法一起工作(所以我可以手工验证产品是否正确我试着给它一个更复杂的语法,输出结果是它不是一个LR(1)语法(源于解析后试图在解析表中的同一个单元格上写两次)
有问题的语法是
S-> aAb | SA
A-> aA | e | S.
我很确定这个语法是LR(1),无论如何,这是我程序的输出 http://pastebin.com/hJNC9uuN
任何建议都将是最宝贵的谢谢(如果有人有一个解析器生成器输出自动机和解析表,所以我可以面对它们更好)
在哪里可以找到 LR(1) 解析器生成器的简单（尽可能多，但不能更简单！）实现？
我不是在寻找性能，只是在寻找生成 LR(1) 状态（项目集）的能力。
C++、C#、Java 和 Python 都适合我。