ANTLR4是否缓存Token？表达式交替匹配的回溯与缓存机制咨询

先看你给出的左递归表达式定义：

expr
  : expr BitwiseAnd expr
  | expr BitwiseXor expr
// ...
;

针对你的问题，解答如下：

• 能否「保存」左侧expr的解析结果，避免分支匹配时从零开始？
  ANTLR 4及之后版本原生支持直接左递归语法，会自动将左递归规则转换为迭代式解析逻辑。当左侧expr解析完成并生成1MB的解析树节点后，这个节点会被直接保留，后续匹配BitwiseAnd或BitwiseXor分支时，完全不需要重新从零解析左侧的expr——解析器会直接复用已生成的结果，接着处理后续的运算符和右侧表达式。

• 分支匹配失败时需要回溯多远？
  ANTLR是LL(*)解析器，会通过向前看符号预判分支选择。比如左侧expr解析完成后，它会查看下一个输入符号：是BitwiseAnd就走第一个分支，是BitwiseXor就走第二个分支。如果某个分支匹配失败（比如预期BitwiseAnd但实际是其他符号），回溯只会回到当前决策点（即左侧expr解析完成后的位置），不会回溯到整个左侧expr的起始位置重新解析。加上左递归已被转为迭代逻辑，这种回溯的开销极小，不会出现从头解析1MB节点的情况。

内容的提问来源于stack exchange，提问作者David542