我对形式语言和编译器理论的了解有限。所以我正在通过Terence Parr 的The Definitive ANTLR 4 Reference这本书来学习。

书上说:

Now, with v4, you can match expressions with rules that look like this:

expr : expr '*' expr // match subexpressions joined with '*' operator
     | expr '+' expr // match subexpressions joined with '+' operator
     | INT           // matches simple integer atom
     ;

Self-referential rules like expr are recursive and, in particular, left recursive because at least one of its alternatives immediately refers to itself.

但我认为粗体部分是不正确的。根据here ，如果右侧最左边的符号与左侧的非终结符相同，则产生式是左递归的。例如，

    expr → expr + term.

所以回到 Terence 的书中的示例，它既不是左递归也不是右递归。它只是递归的。

我说的对吗？还是我误解了作者？

加1

感谢到目前为止的回复。抱歉，我没有说清楚。

我的理解是:left-recursive 意味着右侧的 left-most 部分与左侧的非终结符相同。 AND 右侧的剩余部分是ONLY 后缀，不是 左侧。

Parr's book sample中，右边的reamining部分不是后缀，是another same expr，所以我觉得不是严格符合左递归规则。

最佳答案

让我们比较一下书上给出的左递归规则的例子:

expr → expr + term.

使用您正在检查的复合规则的第一部分:

expr : expr '*' expr // match subexpressions joined with '*' operator

这里，左边是expr；右边是expr '*' expr，右边最左边的符号是expr。由于右边最左边的符号expr与左边的符号相同，也是expr，所以这部分规则是左递归的。

出于同样的原因，复合规则的第二部分也是左递归的:

expr : expr '+' expr

复合规则的第三部分不是递归的，因为 INT 是一个原子:

expr : INT           // matches simple integer atom

当您使用 | 运算符将 expr 的这三个不同表达式合并为一个时，您会得到问题中的原始表达式:

expr : expr '*' expr // match subexpressions joined with '*' operator
     | expr '+' expr // match subexpressions joined with '+' operator
     | INT           // matches simple integer atom
     ;

因为它的三个选择中至少有一个是左递归的，所以它本身也是左递归的。

https://stackoverflow.com/questions/41404765/