parsing - 判断文法是否为 LR(0)

Question

我是编译主题的新手，刚刚开始了自下而上解析的练习。

我一直坚持以下问题。

为以下语法构建一个 LR(0) 解析表：

1) E –&gt; E + T
2) E –&gt; T
3) T –&gt; (E)
4) T –&gt; id


I0 :

   E' –&gt; .E
   E –&gt; .E + T
   E –&gt; .T
   T –&gt; .(E)
   T –&gt; .id

在 E 上，DFA 中的下一个状态是：

 I1:

    E' -> E.
    E  -> E. + T

从我目前了解到的情况来看，这不是 SR 冲突吗？因为解析器不知道是减少还是移位，因为它没有前瞻变量？所以这不应该是 LR(0) 语法吗？

但是我正在阅读的 PDF 已经构建了 LR(0) 表。那么PDF中有错误还是我在理解这个概念的地方出错了？

score 3 · Accepted Answer

你用 . 扩充了语法E' -> E。通常，您会使用类似的产生式进行扩充E' -> E $，其中 $ 是语法中不会出现的（终端）符号，表示输入结束。

所以 I1 实际上是


E' -> E. $
E  -> E. + T

并且没有冲突。（而且我相信语法是LR(0)。）

score 2 · Accepted Answer

这确实是一个移位/减少冲突。该文法不是 LR(0)。您也可以看到这一点，因为它不是无前缀的；该语法包含多个字符串，它们是彼此的前缀，因此它不能是 LR(0)。

也就是说，您仍然可以构造所有 LR(0) 配置集并制作 LR(0) 自动机。由于移位/减少冲突，它不会是确定性的。因此，有可能你是对的，而且讲义是对的。

希望这可以帮助！

2 回答 2