是否可以为递归语法构造LR(0)状态机？

Question

考虑以下语法：

S -> aA
A -> Aa|b

这个语法产生了无限的语言。是否可以为这个语法构造一个 LR(0) 状态机？

Answer 1

语法没有“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

的前瞻相关，而状态机中没有转换。

规范 LR(1) 解析器不使用相同的状态机（在大多数情况下）；在 CLR 解析器中，同一组项目可能有两种状态。这有时可以解决冲突。但在这个语法中这是没有必要的。

注释

1. 如果一种语言具有 prefix 属性，那么它只能是 LR(0)；换句话说，没有一个句子是另一个句子的前缀。 （将其称为“无前缀属性”可能会更好，但这并不容易谈论。）为语言提供前缀属性的最简单方法是为每个输入添加一个输入结束标记（通常用符号

   $

   ）。输入结束标记必须是一个新符号，不会出现在语法中的任何位置。由于新语言中的每个句子都以

   $

   结尾，并且除结尾之外没有句子包含

   $

   ，因此一个句子不可能成为另一个句子的前缀。

   所以要使这个文法LR(0)，只需要将规则

   S -> a A

   改为

   S -> a A $

   即可。这解决了状态 3 中的移位-归约冲突，并且仍然产生无限语言。

Answer 2

不是LR(0)。留声机告诉我：

LR(0) 不是 LR(0) — 它包含移位归约冲突。

添加

E -> S end-of-input .

也没有帮助，你需要去 LR(1)。