我多次提到左递归是绊脚石，是时候弄清楚了。 主要问题是具有左递归下降的解析器由于堆栈溢出而立即崩溃。
请考虑以下假设的语法规则：
expr: expr '+' term | term
如果我们将这种语法实现到左递归解析器方法中，则将得到如下所示的内容：
def expr(): if expr() and expect('+') and term(): return True if term(): return True return False
因此， expr()以对expr()的调用开始，该调用以expr()的调用为开始，该调用以调用...开始。这只能以栈溢出结束，表示为RecursionError异常。
传统的解决方案是重写语法。 在前面的部分中，我只是这样做的。 实际上，上面的语法规则可以重写如下：
expr: term '+' expr | term
但是，在构造解析树的步骤中，其形状将有所不同。 如果我们在语法中添加'-'运算符，这可能会破坏情况（因为a- a - (b - c)与(a - b) - c不相同）。 这通常可以通过更强大的PEG功能（例如分组和迭代）来解决，我们可以将上述规则重写为：
expr: term ('+' term)*
实际上，这就是为pgen解析器编写当前Python语法的方式（与左递归规则存在相同的问题）。
但是，存在一个小问题：由于运算符'+'和'-' （在Python中）大多是二进制的，因此当我们分析a + b + c类a + b + c东西时，我们必须经历解析的结果（本质上是['a', '+', 'b', '+', 'c']以创建左递归解析树（看起来像这样的[['a', '+', 'b'] , '+', 'c'] ）。
原始的左递归语法已经暗示了所需的关联性，因此直接从此形式生成解析器将是很好的选择。 而且我们可以！ 一位读者指出了一个简单易行的数学证明。 现在我将尝试解释。
让我们看一下输入foo + bar + baz的示例。 我们想从中得到的解析树对应于(foo + bar) + baz 。 这需要对expr()函数进行三个左递归调用：一个对应于顶级运算符'+' （即第二个）；第二个对应于顶级运算符'+' 。 一个-内部运算符'+' （即第一个）； 第三是第二种选择（即term ）的选择。
由于我不擅长使用特殊工具绘制实际图表，因此我将在这里使用ASCII文字进行演示：
expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz'
这个想法是，在expr()函数中，我们需要一个“ oracle”来告诉我们选择第一个选择（即对expr()的递归调用）还是选择第二个选择（即term()调用）。 在第一次调用expr() oracle应告诉我们遵循第一个选择（ expr() ）； 在第二个（递归）调用中-类似，但是在第三个调用中，它应该提示我们调用term() 。 在代码中，它将如下所示：
def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False
怎么写这样的甲骨文？ 让我们看看...我们可以尝试跟踪调用堆栈中（左递归） expr()调用的数量，并将其与以下表达式中的'+'运算符进行比较。 如果调用堆栈的深度大于语句数，则oracle应该返回false（迫使我们选择term() ）。 我迫不及待地想用sys._getframe()实现它，但是有一个更好的方法：让我们翻转调用堆栈！
这个想法是，我们从oracle返回false的调用开始，然后保存结果。 这给了我们序列expr() -> term() -> 'foo' 。 （它应该为初始term即'foo'返回一个分析树。上面的代码仅返回True ，但是在系列文章的第二部分中，我已经展示了如何返回该分析树。）这样的oracle易于实现，因为它应该只需在第一次调用时返回False无需进行堆栈检查或查看将来的内容。
然后，我们再次调用expr() ，这一次oracle返回True ，但不是用左递归调用expr() ，而是expr()一次调用保存的结果代替。 并且由于还存在期望的运算符'+'和下一个合适的令牌，因此这将为我们提供foo + bar的解析树。
再次重复该算法，然后一切都变得正确了：这次我们得到了完整表达式的解析树，它实际上是左递归（ (foo + bar) + baz ）。
然后，我们再次重复该算法。 但是这一次，尽管Oracle返回True ，并且上一次调用的保存结果也可用，但是不再有'+'运算符，并且第一种选择失败。 因此，我们尝试第二个选项，该选项成功，并且仅找到初始项（ 'foo' ）。 该结果比从第一种方法获得的结果差，因此在此阶段我们停止并保存最长的分析（即(foo + bar) + baz ）。
为了将其转换为工作代码，我首先对算法进行了一些修改，以将oracle()调用与对expr()的左递归调用相结合。 我们称之为oracle_expr() 。 代码：
def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False
接下来，我们将编写一个实现上述逻辑的包装器。 它使用了一个全局变量（不用担心，我稍后会删除它）。 oracle_expr()函数将读取全局变量，然后包装程序将对其进行控制：
saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result
代码当然很糟糕，但是至少它传达了算法的本质。 让我们对其进行重构，以便我们为此感到自豪。
最重要的理解（尽管我可能不是第一个注意到这一点的人，这属于我）是我们可以使用备忘录缓存而不是全局变量。 在其中，我们将存储呼叫之间的结果。 因此，我们摆脱了单独的函数oracle_expr() ，因为 我们可以生成对expr()的标准调用，而不管它是位于左侧还是右侧的递归位置。
因此，我们需要一个单独的@memoize_left_rec装饰器，该装饰器仅用于左递归规则。 它调用oracle_expr()函数，从备注缓存中提取存储的值，并包含一个循环，该循环多次调用expr()函数，直到每个新结果都可与输入数据中比前一个部分更长的时间相媲美。 而且，当然，由于每个输入位置和每种解析方法都是分别缓存的，因此它不必担心回溯或一些递归规则（例如，在我使用的玩具语法中， expr和term都是递归的）。
我在第三部分中创建的原型的另一个优点是，它使得检查新结果是否比旧结果更容易： mark()方法返回输入令牌数组中的索引，因此我们可以使用它代替parsed_length 。
我忽略了无论语法多么疯狂，该算法为何始终有效的证明。 实际上，我什至没有看过。 我看到这适用于简单的情况，例如我的玩具语法中的expr ，以及更复杂的情况（例如，使用左递归隐藏在可选元素的后面，或者使用多个规则之间的相互递归）。 这个算法仍然可以解决我在Python语法中可以回忆到的最困难的情况，所以我只相信定理和证明它的人。
让我们编写战斗代码。
首先，解析器生成器必须确定哪些规则是递归的。 这是图论中已解决的问题。 我不会在这里展示该算法，实际上，我什至想进一步简化它。 我假设语法中唯一的左递归规则就是直接左递归，就像我们的玩具语法中的expr一样。 然后，要检查左递归性，您只需要查找一个以当前规则的名称开头的替代方法：
def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False
现在，我们将更改解析器生成器，以便为左递归规则生成另一个装饰器。 回想一下，在第三部分中，我们将所有解析器方法包装在@memoize 。 现在，我们将对生成器进行一个小的更改，以便对于左递归规则，我们使用@memoize_left_rec ，然后在memoize_left_rec装饰器中实现魔术。 生成器的其余部分和其他代码无需更改！ （尽管我不得不修改可视化代码）
作为参考，这是@memoize从第3部分复制而来的原始@memoize装饰器。请记住， self是一个具有memo属性（用空字典初始化）和mark()和reset()方法的获取和设置当前位置的Parser实例。标记器：
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
@memoize装饰器会记住先前对输入流中每个位置的调用-对于输入令牌的（懒散）数组中的每个位置，都有一个单独的memo字典。 memoize_wrapper的前四行专用于获取正确的memo字典。
这是@memoize_left_rec 。 只有else分支与上面@memoize的实现略有不同：
def memoize_left_rec(func): def memoize_left_rec_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else:
这对于expr()方法的工作方式可能很有趣。 让我们看看下面的代码将如何执行：
@memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None
在解析foo + bar + baz的示例中。
每当您调用expr()函数时，装饰者都会“调用”该呼叫，该装饰者正在当前位置寻找上一个呼叫。 在第一次调用时，我们到达else分支，在这里我们反复调用装饰函数expr() 。 显然，我们将再次首先到达装饰器，但是这次缓存中已经有一些值，因此递归被中断了。
接下来会发生什么？ 初始缓存值是在以下行上计算的：
这导致装饰的expr()返回None ，然后在expr()的第一个if下降（当expr: = self.expr() ）。 也就是说，我们继续第二个if ，它成功识别出该term （在我们的示例中为'foo' ），并且expr返回Node一个实例。 我们从哪里回来？ 到装饰器中的while 。 我们使用新结果（ Node实例）更新备忘录缓存，然后运行下一个迭代。
再次调用expr() ，这次拦截的递归调用返回Node （term）的缓存实例，然后继续进行expect('+')的调用expect('+') 。 一切都井井有条，因为我们现在是第一个'+'运算符。 之后，我们寻找一个也会成功的术语（找到'bar' ）。
因此，现在已经识别出foo + bar expr()返回while ，该while执行相同的操作：它使用新的（更长的）结果更新备注缓存，并开始下一次迭代。
再次重复该游戏。 再次，拦截的递归调用expr()从缓存中检索新结果（这次是foo + bar ），我们希望看到另一个'+' （第二个）和另一个term （ 'baz' ）。 我们创建一个表示(foo + bar) + baz的Node ，将其返回到while ，将其放入缓存中并再次重复。
但是现在，我们将继续该算法的另一个分支。 我们希望遇到另一个'+' ，但找不到它！ 因此，对expr()此调用返回其第二个选择，并且仅返回term 。 当这在while之前弹出while ，表明结果比最后一个要短。 因此，它会中断并向发起expr()调用的用户返回更长的结果（ (foo + bar) + baz ）（例如，此处未显示statement()调用）。
因此，这就是今天的故事的结尾：我们在PEG解析器中成功实现了左递归。 下周，我计划讨论在语法中添加“动作”的方法，这将使我们能够自定义解析器方法针对此替代方法返回的结果（而不是始终返回Node实例）。
如果您想使用这些代码，请查看GitHub存储库 。 （我还为左递归添加了可视化代码，但我对此不太满意，因此在此不提供指向它的链接。）
本文和引用代码的许可： CC BY-NC-SA 4.0