如果在进行基本的语法更改后，直接使用LL语法进行LR解析器，会发生什么情况？

Question

很抱歉我问了这么个业余的问题。我有一个LL文法，我想写一个LR文法。我是否可以使用LL语法，对它进行最小的语法修改，以适应LR解析器并使用它？这是个坏主意吗？它们之间是否存在无法翻译的结构差异？

Answer 1

所有的LL(1)语法都是LR(1)，所以如果你有一个LR(1)解析器生成器，你肯定可以使用你的LL(1)语法，假设BNF语法是解析器生成器使用的语法。

但是您可能没有LR(1)解析器生成器，而是只能处理LR(1)语法的LALR(1)子集的解析器生成器。尽管如此，你可能还好。“大多数”LL(1)语法都是用LALR(1)编写的，很少能找到不是这样的有用的LL(1)。(例如，This pattern不太可能出现在实用语法中。)

所以这可能是可能的。但这可能不是一个好主意。

自上而下的解析器不能处理左递归，如果没有左递归，你就不能编写表示左结合运算符的语法，也就是说大多数算术运算符。在实践中，这个问题通常是通过使用右联想语法和一个特殊的评估函数来解决的，该函数纠正了关联性。这是不太理想的。此外，通过机械地删除左递归创建的LL语法往往很难阅读。

因此，最好使用专为LR解析而设计的语法。但你可能不需要这么做。