如何将表达式规则转换为LL(1)而不变成右结合？

Question

在下面的小语法中，我对如何将定义二元运算符组合的基本规则转换为将生成左关联 AST 的 LL(1) 语法感到困惑：

program    ::= statement

statement  ::= expression ;

expression ::= number
             | expression binary-operator expression

据我了解，我可以引入一些新规则，例如：

expression ::= number rest-expr 

rest-expr  ::= binary-operator expression
             |  ϵ

这将允许像“4 + 2;”这样的语句和“4 + 3 + 3；”才能被正确识别。然而，由于语句中的递归，生成的抽象语法树将是右关联的。

Answer 1

您可以将右关联 AST 转换为左关联 AST。

但是如果您希望解析器本身生成左关联 AST，则需要左递归语法。并且左递归语法不能是 LL(1)，因为对于递归非终结符，您无法根据 1 个前瞻符号区分递归替代和非递归替代。 （事实上，对于任何 k，它都不可能是 LL(k)。）