SLR(1)解析器和epsilon的涉及

Question

假设我有以下语法：

S → X  
X → a | ϵ

如果语法中没有涉及ϵ，我会像这样构建第一个状态：

S' → .S
S → .X
X → .a

但是关于符号 ϵ 呢？我应该包含它吗：

X → .ϵ

也就是说...在创建下一个状态时，我应该执行GOTO(Io,ϵ)，其中Io是第一个状态吗？

- Oscar Mederos

Answer 1

我同意 Howard 的观点。在 DFA 中，你的状态应该包含项：x → . 这是我为一个使用两个 epsilon 产生式的语法识别 SLR(1) 解析器所绘制的 DFA：

- Rose Perrone

---

我对这个扫描示例有问题。让我们看一下T(n)：T -> .(E)goto(T(n), () = { [T->(.E)], [E->.TX], [T->.(E)] , [T->.intY]} 如果是这样，那么对于T(n+1): X->.+E 我不应该有：goto(T(n+1), +) = {[X->+.E], [E->.TX], [T->.(E)] , [T-> .intY]} ? 相反，在这个例子中，我有：goto(T(n+1), +) = {[X->+.E], [E->.TX]} 为什么我们在goto(T(n+1), +)中没有包括T的产生式？ - Joanna

你是正确的，@joanna。虽然我不理解你所说的T(n)和T(n+1)，但你提到的LR状态，即{[X->+.E]，[E->.TX]}，应该通过预测包含T的产生式。在当前的表述中，由于点号右侧没有终端符号，因此无法从给定状态进行进展。 - corwin.amber

Answer 2

由于ϵ本身不是终止符，所以您必须从规则中将其删除，这将给出：

X → .

那么以后你就不会有任何奇怪的使用带有“符号” ϵ 的 GOTO，而是会用状态来替代。

S' → S.

在你的图中是一个接受状态。

- Howard

---

那很有道理。你有一个应用了epsilon的文法LR分析器的例子吗？ - Oscar Mederos

@Oscar 很抱歉我没有演示如何进行的示例。但是，根据您的语法，手动构建这个应该很简单。 - Howard

我今天在一本书中确认了它 ;) 它正如你所说的那样。谢谢你的回复。 - Oscar Mederos

那么你的意思是应该应用epsilon消除吗？ - Parsa Noori