递归文法可以有 LR(0) 状态吗？
Can a recursive grammar have a LR(0) state?
在这个例子中：
S -> aA
A -> Aa|b
上述语法生成的语言（字符串集）是无限的。有没有可能找到它的LR(0)状态机？
语法没有“a”LR(0) 状态。您可以为语法构造一个 LR(0) 状态机；那台机器有几个状态。
这是您的语法的 LR(0) 状态机，由 Grammophone:
生成
上面的状态机没有显示归约转换，但可以从每个状态的项目中推导出来；项目末尾带有 • 的状态是缩减状态（状态 1、3、4 和 5）。由于 LR(0) 解析器可能不会参考下一个标记来决定是否进行归约，因此语法不是 LR(0)；状态 3 既有转换又有还原 [注 1]。
虽然文法不是LR(0)，但LR(0)状态机仍然很重要，因为SLR(1)和LALR(1)解析器使用相同的状态机，它们具有完全相同的状态.因此，构造 SLR(1) 和 LALR(1) 解析器从构造 LR(0) 状态机开始。不同之处在于 SLR(1) 和 LALR(1) 解析器确实使用 (1) 前瞻符号来确定归约操作。使用这两种算法中的任何一种，状态 3 中的冲突都将得到解决，因为缩减仅与 b 的先行相关联，状态机中没有转换。
Canonical LR(1) 解析器不使用相同的状态机（在大多数情况下）；在 CLR 解析器中，可以有两个状态具有相同的项目集。这有时可以解决冲突。但是在这个语法中是没有必要的。
备注
一种语言如果具有 前缀 属性 则只能是 LR(0)；换句话说，没有一个句子是另一个句子的前缀。 （将其称为“无前缀 属性”可能更好，但这并不是那么容易谈论。）为语言提供前缀 属性 的最简单方法是添加一个结尾 -每个输入的输入标记（通常用符号 $）。输入结束标记必须是一个新符号，它不会出现在语法中的任何地方。由于新语言中的每个句子都以 $ 结尾，并且除了结尾之外没有任何句子包含 $，所以一个句子不可能是另一个句子的前缀。
所以要使这个文法成为LR(0)，只需要将规则S -> a A改为S -> a A $。这解决了状态 3 中的 shift-reduce 冲突，并且仍然产生无限语言。
不是LR(0)。留声机告诉我：
LR(0) Not LR(0) — it contains a shift-reduce conflict.
添加 E -> S end-of-input . 也无济于事，您需要转到 LR(1)。
在这个例子中：
S -> aA
A -> Aa|b
上述语法生成的语言（字符串集）是无限的。有没有可能找到它的LR(0)状态机？
语法没有“a”LR(0) 状态。您可以为语法构造一个 LR(0) 状态机；那台机器有几个状态。
这是您的语法的 LR(0) 状态机，由 Grammophone:
生成上面的状态机没有显示归约转换，但可以从每个状态的项目中推导出来；项目末尾带有 • 的状态是缩减状态（状态 1、3、4 和 5）。由于 LR(0) 解析器可能不会参考下一个标记来决定是否进行归约，因此语法不是 LR(0)；状态 3 既有转换又有还原 [注 1]。
虽然文法不是LR(0)，但LR(0)状态机仍然很重要，因为SLR(1)和LALR(1)解析器使用相同的状态机，它们具有完全相同的状态.因此，构造 SLR(1) 和 LALR(1) 解析器从构造 LR(0) 状态机开始。不同之处在于 SLR(1) 和 LALR(1) 解析器确实使用 (1) 前瞻符号来确定归约操作。使用这两种算法中的任何一种，状态 3 中的冲突都将得到解决，因为缩减仅与 b 的先行相关联，状态机中没有转换。
Canonical LR(1) 解析器不使用相同的状态机（在大多数情况下）；在 CLR 解析器中，可以有两个状态具有相同的项目集。这有时可以解决冲突。但是在这个语法中是没有必要的。
备注
一种语言如果具有 前缀 属性 则只能是 LR(0)；换句话说，没有一个句子是另一个句子的前缀。 （将其称为“无前缀 属性”可能更好，但这并不是那么容易谈论。）为语言提供前缀 属性 的最简单方法是添加一个结尾 -每个输入的输入标记（通常用符号
$）。输入结束标记必须是一个新符号，它不会出现在语法中的任何地方。由于新语言中的每个句子都以$结尾，并且除了结尾之外没有任何句子包含$，所以一个句子不可能是另一个句子的前缀。所以要使这个文法成为LR(0)，只需要将规则
S -> a A改为S -> a A $。这解决了状态 3 中的 shift-reduce 冲突，并且仍然产生无限语言。
不是LR(0)。留声机告诉我：
LR(0) Not LR(0) — it contains a shift-reduce conflict.
添加 E -> S end-of-input . 也无济于事，您需要转到 LR(1)。