按照 http://blog.ptsecurity.com/2016/06/theory-and-practice-of-source-code.html#java--and-java8-grammars，我试图在相当复杂的语法中减少左递归。 据我了解，递归的非原始形式可能会导致内存和处理时间方面的性能问题。
所以我试图在我的语法中重构这些规则，只使用"原始"递归。 当然，那篇博文是我唯一一次看到关于Antlr的"原始"递归一词。 所以我只是猜测它的含义/意图。 在我看来，这意味着一个规则，它将自己称为最多只有一个规则分支的 lhs。 正确？
目前我有一个表达式规则，如下所示：
expression
: expression DOUBLE_PIPE expression # ConcatenationExpression
| expression PLUS expression # AdditionExpression
| expression MINUS expression # SubtractionExpression
| expression ASTERISK expression # MultiplicationExpression
| expression SLASH expression # DivisionExpression
| expression PERCENT expression # ModuloExpression
...
;
该...包括相当多的子规则，这些子规则也可以追溯到expression. 但这些是唯一具有直接递归的。
如果我理解正确，将这些重构为"原始"递归将如下所示：
expression
: binaryOpExpression # BinaryOpExpression
...
;
binaryOpExpression
: expression DOUBLE_PIPE expression # ConcatenationExpression
| expression PLUS expression # AdditionExpression
| expression MINUS expression # SubtractionExpression
| expression ASTERISK expression # MultiplicationExpression
| expression SLASH expression # DivisionExpression
| expression PERCENT expression # ModuloExpression
;
首先，这是正确的重构吗？
其次，这真的有助于性能吗？ 归根结底，它仍然是相同的决定，所以我并不真正了解这如何帮助性能(除了可能产生更少的 ATNConfig 对象(。
谢谢
我以前没有在这种情况下听说过"原始递归"，作者可能只是想在 ANTLR4 中命名一种特定形式的递归。
事实上，ANTLR4 中有 3 种相关的递归形式：
- 直接左递归：从规则中的第一个规则引用(到同一规则(的递归。例如：
a: ab | c;
间接左递归 - ：不直接来自同一规则的左递归。例如：
a: b | c; b: c | d; c: a | e;(在ANTLR4中不允许( - 右递归：规则中的任何其他递归。例如：
a: ba | c;.然而，名称"右递归"仅在二进制表达式的情况下是正确的，但通常用于与一般的左递归区分开来。
话虽如此，很明显您的重写是错误的，因为它会产生间接的左递归，而 ANLTR4 不支持。直接左递归通常不是问题(从内存或性能的角度来看(，因为ANTLR4将它们转换为非递归ATN规则图。
可能成为问题的是右递归，因为它们是通过代码递归(运行时中的递归函数调用(实现的，这可能会耗尽 CPU 堆栈。我见过无法在单独线程中解析的大表达式的情况，因为我无法将线程堆栈大小设置为更大的值(主线程堆栈大小通常可以通过链接器设置进行调整(。
对于后一种情况，我发现它很有用，是减少语法中相互调用的解析器规则的数量。当然，将某些表达式元素放在不同的规则中(例如andExpression、orExpression、bitExpression等(是结构、可读性等问题，但这可能会导致相当深的调用堆栈，这可能会耗尽 CPU 堆栈和/或需要大量时间来处理它们。