语法是LALR吗？

Question

假设相同的语法不是LR(1)，我们可以安全地说该语法也不是LALR吗？

如果不是，语法是LALR的条件是什么？(或者是什么条件使语法不是LALR)

谢谢你的帮助！

Answer 1

LALR(1)，⊂LR(1)，所以是的，我们可以假设。这两种语法以类似的方式表达语言，但LR(1)比LALR(1)跟踪更左的状态。请参阅These lecture notes，它讨论了两种表示之间的状态差异。

通常，解析器生成器将为您处理创建shift-reduce步骤的所有细节；不同之处在于，基于较大语法的生成器更有可能找到无冲突的解析策略。

Answer 2

This document对两者进行了比较。

Answer 3

下面是一个简单的语法，它是LR(1)，但不是LALR(1)：

G -> S 
S -> c X t 
  -> c Y n
  -> r Y t
  -> r X n 
X -> a
Y -> a

LALR(1)解析器生成器为您提供了LR(0)状态机。LR(1)解析器生成器为您提供了LR(1)状态机。使用此语法，LR(1)状态机比LR(0)状态机多一个状态。

LR(0)状态机包含以下状态：

X -> a . 
Y -> a .

LR(1)状态机包含这两个状态，而不是上面显示的状态：

X -> a . { t }
Y -> a . { n }

X -> a . { n }
Y -> a . { t }

LALR的问题是，状态是在不了解任何look-a-heads的情况下首先建立的。然后，在建立状态之后检查或创建look-a-heads。然后LALR有这一种状态，通常稍后添加的look -a-head将如下所示：

X -> a . { t, n }
Y -> a . { n, t }

有人能看到这里有什么问题吗？如果前瞻是't'，你会选择哪一个减少？模棱两可！因此，LALR(1)解析器生成器会给出一个reduce-reduce冲突报告，这可能会让没有经验的语法作者感到困惑。

这就是为什么我让LRSTAR成为LR(1)解析器生成器的原因。它可以处理上面的语法。