判断语法是否为LR(0)

Question

我对编译这一主题很陌生，并且刚刚开始底层-up解析的练习。

我一直困在以下问题上。

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

1) E –> E + T
2) E –> T
3) T –> (E)
4) T –> id


I0 :

   E' –> .E
   E –> .E + T
   E –> .T
   T –> .(E)
   T –> .id

关于E，DFA的下一个州是：

 I1:

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

据我所知，这不是一场S冲突吗？因为解析器不知道是减少还是移位，因为它没有前瞻性变量？所以这不应该是LR(0)语法吗？

但是我正在读的PDF已经建立了LR(0)表。那么，PDF中是否有错误，或者我在哪里理解了这个概念？

Answer 1

这确实是一种转变/减少冲突。这个语法不是LR(0)。您还可以看到这一点，因为它不是无前缀的；语法包含多个字符串，这些字符串是彼此的前缀，所以它不能是LR(0)。

也就是说，您仍然可以构造所有LR(0)配置集，并生成LR(0)自动机。它将不会是决定性的，因为转移/减少冲突。因此，有可能你是对的，施舍也是对的。

希望这能有所帮助！

Answer 2

您用E' -> E增强了语法。通常，您会增加像E' -> E $这样的产品，其中$是语法中没有出现的(终端)符号，并表示输入结束。

所以I1实际上是

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

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