SLR(1)语法中带有epsilon转换的解析器

Question

我正在根据以下语法编写SLR(1)解析器：

1) S -> aSb
2) S -> cB
3) B -> cB
4) B -> ε

首先，我开始寻找相关的LR(0)自动机，并添加S' -> S产生的增广文法，并开始计算各种状态。我发现的州是：

I0 ={S‘->·S，S->·aSb，S->·cB}

(I0，S) = I1；(I0，a) = I2；(I0，c) = I3；

I1 ={S‘->S·}

I2 ={S->a·Sb，S->·aSb，S->·cB}

(I2，S) = I4；(I2，a) = I2；(I2，c) = I3

I3 ={S->c·B，B->·cB，B->·ε}

(I3，B) = I5；(I3，ε) = I6；(I3，c) = I7；

I4 ={S->aS·b}

(I4，b) = I8；

I5 ={S->cB·}

I6 ={B->ε·}

I7 ={B->c·B，B->·cB，B->·ε}

(I7，B) = I9；(I7，ε) = I6；(I7，c) = I7；

I8 ={S->aSb·}

I9 ={B->cB·}

这里有LR(0)自动机：

自动机图

在那之后，我做了解析器表(但我认为不需要它来回答我的问题)，所以我有一个疑问: epsilon转换是否以正确的方式处理？我的意思是，我把它当作一个正常的角色，因为我们必须在某个时候减少第4条规则。如果我错了，我该如何对待这种转变？提前感谢，希望这对其他人也有帮助。

Answer 1

不，没有必要创建状态I6

在Y->Ɛ中可能会出现混淆。当您在增广的产品中放置一个点时，例如S->A.B，这意味着A已经完成，B还没有完成(这里的完成意味着解析的进展)。类似地，如果您编写Y->.Ɛ，这意味着Ɛ尚未结束，但我们也知道Ɛ是null string，也就是说，没有任何东西被解释为Y->.

您可以使用JFLAP软件并看到它是关于SLR的文献(1)

Answer 2

不需要..。就连我也面临着同样的问题，同时去掉了下面语法的左重述

E->E+T|E-T|T转换后的规则看起来像E->T X X->+TX|-TX|*e*

这不重要因为

x->.e和x->e.在Epsilon是疯子的工作前后没有任何significance.Since移动。