语法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）状态机。 （1）状态机比LR（0）状态机多一个状态 。

的LR（0）状态机包含此状态：

X -> a . 
Y -> a . 

的LR（1）状态机包含的这两种状态而不是 上面显示的一个：

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

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

问题与LALR是国家是第一个 没有任何知识的头看。然后，在创建状态之后检查或创建外观 。然后LALR 有这样一个状态和外观-A-头，这通常是后来添加的， 看起来就像这样：

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

任何人可以在这里看到了问题？如果预见是't'，你选择哪种减少方式？ ？它含糊不清！因此，LALR（1）解析器生成器会为您提供减少 - 减少冲突报告，这可能会使作者无经验的语法 混淆。

很少有现实世界的计算机语言，它们的LALR（1）冲突可以用LR（1）解析器生成器来解决。 但是，这些冲突通常可以使用LALR（2） 解析器生成器来解决。

这就是为什么我使LRSTAR为LALR（k）解析器生成器。它可以通过在 运行时使用前面的2来处理上述语法。如果有人向我展示LR（1）但不是 LALR（1）的现实世界语法，它将来可能会成为LR（k）解析器生成器， 。