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

Question

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

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

首先，我开始使用添加了 S' -> S 产生式的增强语法找到关联的 LR(0) 自动机，并开始计算各种状态。我找到的状态是：

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) 自动机：

Automaton Picture

在那之后，我做了解析器table（但我认为不需要它来回答我的问题）所以我有疑问： epsilon 转换是否以正确的方式处理？我的意思是，我将其视为普通字符，因为我们必须在某个时候减少规则编号 4。如果我错了，我应该如何对待这种转变？在此先感谢，希望这对其他人也有帮助。

Answer 1

否，无需创建状态 I6

Y->Ɛ 中可能出现了混乱。例如，当您在扩充产生式中放置一个点时，S->A.B 表示 A 已完成，而 B 尚未完成（此处的完成表示解析取得进展）。同样，如果你写 Y->.Ɛ ，这意味着 Ɛ 还没有结束，但我们也知道 Ɛ 是 null string 即什么都没有，因此 Y->.Ɛ 被解释为Y->.

你可以使用 JFLAP Software and see it's documentation about SLR(1)

Answer 2

不需要... 即使我在删除以下语法的左递归时也遇到了同样的问题

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

没关系，因为

x->.e 和 x->e。没有significance.Since 移动Epsilon 前后的时间段是疯子的工作

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

SLR(1) parser with epsilon transitions in the grammar

parsing

compiler-construction

computer-science

grammar

formal-languages