带有epsilon的SLR(1)解析器

Question

让我们假设我有以下语法：

E -> TX

T -> (E) \x{e76f} int Y

X -+E=ε

Y ->*T_xε

构建项目集--我得到一个类似于此的状态：

T -> int .Y

Y ->* T

Y -> .

这种状态是否足够？也就是说，语法是SLR(1)还是不？谢谢

Answer 1

是的，您在状态中指定的条目绝对正确。

  T->int.Y
  Y->.*T
  Y->.

这是为给定语法的SLR(1)解析器创建的DFA中的第5个状态。

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

我为这个语法创建了DFA (13个状态)，并发现给定的语法是SLR(1)，因为没有减少-减少或移位-减少冲突。

Answer 2

您必须构造以下集合，并查看下面(Y)是否包含int或*。如果是这样的话，就会发生移位/减少冲突，语法也不会是SLR(1)。检查所有状态，如果没有冲突，则语法为SLR(1)。