基于DFS的通用AST构建器：循环退出条件问题求助

嘿，这个问题我太熟悉了——左递归文法在DFS递归下降解析器里确实是个经典的“死循环陷阱”！你遇到的核心矛盾很清晰：右递归文法能避免无限循环，但会生成不符合预期的右结合AST；改成左递归文法符合左结合语义，却触发了无限递归。下面给你几个不用靠“随机最大深度”的合理解决方案，还能保留你的DFS实现：

1. 标准解法：消除左递归（最推荐） #

编译原理里有一套成熟的左递归消除方法，能把你的左递归文法转换成等价的、不会触发无限递归的形式，同时保留左结合的语义。

你的左递归文法：

expr := addExpr;
addExpr := NUMBER | expr OPERATOR NUMBER ;

消除左递归后，可以改成：

expr := addExpr;
addExpr := NUMBER (OPERATOR NUMBER)* ;

这里的(OPERATOR NUMBER)*表示零次或多次重复匹配OPERATOR NUMBER组合。在DFS实现里，你可以这么处理：

• 先匹配一个NUMBER作为基础节点
• 然后进入循环：尝试匹配OPERATOR + NUMBER，每匹配成功一次，就把当前的addExpr节点和新的NUMBER用OPERATOR组合成新的左结合节点（比如把(4-2)和2用+组合成((4-2)+2)）
• 直到无法匹配OPERATOR为止，退出循环

这种方式完全避免了左递归的无限调用，而且天然支持左结合，AST的结构也完全符合你的预期。

2. 给DFS加「进度检查」终止条件（适合不想改文法的场景） #

如果你不想修改文法结构，想直接在DFS里解决无限循环问题，可以给递归函数加一个令牌消耗进度检查的终止规则：

每次进入一个递归分支（比如尝试匹配expr OPERATOR NUMBER）时，先记录当前的令牌指针位置（比如当前读到第几个令牌）。如果递归调用expr之后，令牌指针没有前进（也就是没有消耗任何令牌），说明这个分支是无效的，直接回溯，不再继续递归。

举个具体的执行流程例子（以"4 - 2 + 2"为例）：

1. 调用addExpr，先尝试第一个分支NUMBER，匹配了"4"，令牌指针前进到第2个令牌（"-"），但此时addExpr还可以尝试第二个分支，所以进入回溯
2. 尝试第二个分支expr OPERATOR NUMBER：
   • 先记录当前令牌指针位置是0
   • 调用expr，expr又调用addExpr，addExpr匹配NUMBER（"4"），令牌指针前进到1
   • 回到expr OPERATOR NUMBER分支，现在匹配OPERATOR（"-"），令牌指针前进到2；再匹配NUMBER（"2"），令牌指针前进到3
   • 此时令牌指针从0前进到3，说明有效，继续处理剩下的"+ 2"：再次进入addExpr的循环，匹配OPERATOR（"+"）和NUMBER（"2"），最终生成左结合AST
3. 如果某次递归调用expr后，令牌指针停在原地（比如空输入或者无法匹配的情况），就直接终止这个分支的递归，避免无限循环

这个方法的核心逻辑是：没有消耗任何令牌的递归调用一定是无效的，必须终止，这比你之前尝试的“记录历史”更精准，不会过早终止有效分支。

为什么你的历史记录方法会过早终止？ #

你之前尝试的“同一表达式匹配剩余令牌时停止”的问题在于：同一个剩余令牌序列可能对应多个有效解析分支（比如不同的规则匹配），但进度检查只看是否有实际的令牌消耗，能准确区分“无限递归的无效分支”和“正常递归的有效分支”。

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