LR(1) 解析表与 epsilon 产品

Question

我无法使用包含 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, $
U -> .eps, $

我在这里做什么？我是否需要使用 eps 移动并使用该项目进行设置U -> eps., $？如果我有另一个终端作为前瞻，即X -> .eps, a/$？如果我搬家，最终得到一组表格X -> eps., $，我会减少吗？

还有更多：我需要在解析表中插入 eps 作为符号吗？

谢谢

Answer 1

1. FIRST(U$)意思是“可能是“的第一个推导的符号集U$”。显然，如果U可以导出空字符串，则$必须是该集合的一部分。输入结束标记$确保我们永远不必担心FIRST集合中的epsilon 。（如果我们使用 LR(k) 而不是 LR(1)，我们将使用k结束标记，以便所有字符串都具有长度。FIRSTkk

2. 与U → （或U → ε如果您坚持）相关联的项目是U → • 。换句话说，它是可缩减的，并且应该触发匹配前瞻的缩减操作。

3. ?不是一个符号；我们只使用它（有时）来使空字符串可见。但是空字符串是空的。