LR(0)解析器冲突

Question

我对lr(0)解析器有疑问。例如，我有以下语法：

S -> S N
   | 

N -> terminalsymbol

如果我试图构造lr0自动机的第一个状态，我得到以下第一个状态：

S ' -> . S $ 

S -> . S N
S -> . 

所以在我看来这是一个愚蠢的疑问。因为我有"S ->“在第一种状态下，这是lr0解析器中的shift/reduce的情况吗？因为解析器可以通过非终结符S来转移操作，或者通过空转换来减少操作(我认为)。

我已经在网络上搜索了一个空转换的例子，但是我没有找到。

Answer 1

如果你从扩充语法开始，就不会有冲突。

在初始状态下，没有可能的shift操作，并且只有一个reduce操作。因此，reduce操作必须无条件地发生。

一旦你减少了S，你最终会处于这样的状态：

S' -> S . $
S  -> S . N
N  -> . nonterminal

它将移位输入结束标记或下面的非终止标记。假设它是非终结符，我们最终会得到：

N  -> nonterminal .

这是另一种强制缩减，它引导我们

S  -> S N .

然后我们又回到：

S' -> . S $
S  -> . S N
S  -> .

然而，原始的非增广文法不是LR(0)。(同时包含空字符串和其他字符串的语言不能是LR(0)。)