递归文法是否具有LR(0)状态？

Question

在本例中：

S -> aA
A -> Aa|b

由上述语法生成的语言(字符串集)是无限的。有可能找到它的LR(0)状态机吗？

Answer 1

语法没有“一个”LR(0)状态。您可以为语法构造一个LR(0)状态机；该机器有几个状态。

下面是用格莱美管生成的用于语法的LR(0)状态机

​

​

上面的状态机没有显示约简转换，但它们可以从每种状态中的项中推断出来；在结束时带有..项的状态是一个约简状态(状态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. 只有当语言具有前缀属性时，语言才能成为LR(0)；换句话说，没有一个句子是另一个句子的前缀。(将其称为“无前缀属性”可能更好，但谈论起来并不容易。)赋予语言前缀属性的最简单方法是在每个输入(通常是符号化的$)中添加一个输入结束标记。输入结束标记必须是语法中没有出现的新符号.由于新语言中的每个句子都以$结尾，而且除了末尾没有任何句子包含$，所以句子不可能成为另一个句子的前缀。 因此，要使该语法成为LR(0)，只需将规则S -> a A更改为S -> a A $即可。这解决了状态3中的shift-还原冲突，并且仍然产生了无限的语言。

Answer 2

它不是LR(0)。格莱美管告诉我：

LR(0)不是LR(0) -它包含一个移位-减少冲突。

添加E -> S end-of-input .也无济于事，您需要选择LR(1)。

​

​