解析器组合子库需实现何种回溯？贪心OR算法是否足够？

贪心OR失效的典型案例 #

假设你的贪心OR逻辑是仅选择当前位置最长匹配的产生式，再继续后续解析（而非完整尝试每个产生式的全输入匹配），那么以下文法+输入会导致合法输入匹配失败：

文法定义 #

S → P Q
P → "x" | "xa"
Q → "a" | "ay"

输入 #

"xay"

问题分析 #

1. 解析S时，先处理P：
   • P的两个候选产生式中，"xa"的匹配长度（2）大于"x"的匹配长度（1），贪心OR会选择"xa"。
2. 此时剩余输入为"y"，接下来处理Q：
   • Q的两个候选产生式都要求以"a"开头，无法匹配剩余的"y"，导致整个解析失败。
3. 但实际上，输入是合法的：选择P的"x"（匹配长度1），剩余输入"ay"可被Q的"ay"完全匹配，最终S能完整匹配整个输入。

如果你的贪心OR逻辑是完整尝试每个产生式的全输入匹配，再选择最长的成功匹配，上述案例可以被正确处理，但仍存在更复杂的失效场景——比如需要多层回溯的歧义文法：

文法定义 #

Expr → Expr "+" Term | Term
Term → Term "*" Factor | Factor
Factor → "(" Expr ")" | Number
Number → "0".."9"

输入 #

"1+2*3"

问题分析 #

若产生式顺序为Expr → Term | Expr "+" Term（先尝试Term），贪心OR完整尝试时：

1. 先尝试Expr → Term，匹配"1"后，剩余"+2*3"无法继续匹配，此路径匹配长度为1。
2. 再尝试Expr → Expr "+" Term：
   • 递归解析第一个Expr时，又会先尝试Term匹配"1"，然后匹配"+"，再解析Term时，尝试Term → Term "*" Factor匹配"2*3"，最终完整匹配整个输入，长度为5。
     此时贪心OR能选择正确路径，但如果是更复杂的嵌套歧义（比如"1+(2*3+4)"），贪心OR需要多次递归尝试不同产生式，本质上已经是回溯解析的一种变体。

最小回溯程度 #

要覆盖所有CFG的合法输入，你需要实现带回溯的递归下降解析，但可以通过以下方式最小化回溯：

• 仅在OR组合子处回溯：当某个产生式匹配失败时，回退到OR的选择点，尝试下一个候选产生式，而非全局回溯。
• 缓存匹配结果（Memoization）：对于相同的输入位置和非终结符，缓存已尝试过的匹配结果，避免重复计算（即实现Packrat解析），这能将递归下降解析的时间复杂度从指数级优化到线性级。
• 优先尝试更具体的产生式：在OR组合子中，将更具体、匹配长度更长的产生式放在前面，减少不必要的回溯（比如先尝试带后缀的产生式，再尝试短的）。

如果你的目标是仅处理LL(k)文法（无需回溯的上下文无关文法），那么贪心OR结合k-lookahead（向前看k个符号选择产生式）即可，无需回溯。但如果要支持任意CFG，最小回溯程度就是在OR组合子处实现选择点的回溯，并结合Memoization避免冗余计算。

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