原标题|左递归PEG语法的作者|GuidovanRossum（Python之父）译者|作者）声明|本翻译以交流学习为目的，基于CCBY-NC-SA4.0许可协议。为便于阅读，内容略有修改。我已经多次提到左递归是一个绊脚石，是时候解决它了。基本问题是这样的：当使用递归下降解析器时，左递归会由于堆栈溢出而导致程序终止。[这是我的PEG系列的第5部分。其他文章见此目录]假设语法规则如下：expr:expr'+'term|term如果我们天真地将它翻译成递归下降解析器的片段，我们会得到以下内容：returnFalse也就是说，expr()以调用expr()开始，而expr()又以调用expr()开始，依此类推…………只能以堆栈溢出结束，抛出RecursionError。传统的补救措施是重写语法。在以前的文章中，我已经这样做了。其实上面的语法也是可以识别的，如果我们改写成这样：expr:term'+'expr|term但是，如果我们用它来生成解析树，那么解析树的形状就会不同，这将导致破坏性的后果，就像我们在语法中添加一个'-'运算符时（因为a-(b-c)与(a-b)-c)不同。这通常可以使用更强大的PEG功能来解决，例如分组和迭代，我们可以将上面的规则重写为：expr:term('+'term)*事实上，这正是pgen解析器生成时Python当前的语法（pgen与左递归规则有同样的问题）。但这仍然存在一些问题：因为像'+'和'-'这样的运算符基本上是二进制的（在Python中），当我们解析像a+b+c这样的东西时，我们必须遍历解析（基本上是列表['a','+','b','+','c'])构造左递归解析树（类似[['a','+','b'],'+','C']）。原始的左递归文法已经表达了所需的关联性，因此如果我们能够直接以这种形式生成解析器就好了。我们可以！一位粉丝向我指出了一个很好的技巧，并附有数学证明，很容易实现。我会在这里解释一下。让我们以输入foo+bar+baz为例。我们要解析出来的解析树对应的是(foo+bar)+baz。这需要对expr()进行三次左递归调用：一次用于顶级“+”运算符（即第二次）；一个用于内部“+”运算符（即第一个）；和一个用于选择第二个选项（即术语）。由于我不擅长用计算机绘制实际图表，因此我将在此处使用ASCII技巧来演示：expr------------+------+|\\expr--+------+'+'项|\\|expr'+'项||||术语|||||'foo''bar''baz'我们的想法是希望在expr()函数中有一个“oracle”（译注：预言，oracle，后面就不翻译了），它要么告诉我们取第一个选择（即递归调用expr()），或第二个（即调用term()）。在第一次调用expr()时，“oracle”应该返回true；在第二次（递归）调用时，它也应该返回true，但在第三次调用时，它应该返回false，以便我们可以调用term()。在代码中应该是这样的：defexpr():iforacle()andexpr()andexpect('+')andterm():returnTrueifterm():returnTruereturnFalse应该怎么写这个“甲骨文”呢？试一试……我们可以尝试在调用堆栈上记录对expr()的（左递归）调用次数，并将其与下面表达式中“+”运算符的数量进行比较。如果调用堆栈的深度大于运算符的数量，则应返回false。我几乎想用sys._getframe()来完成它，但有更好的方法：让我们反转调用堆栈！这里的想法是我们从返回false的oracle调用，并保存结果。这给出expr()->term()->'foo'。（它应该返回原始术语“foo”的解析树。上面的代码只返回True，但在本系列的第二篇文章中，我已经展示了如何返回解析树。）编写一个oracle很容易实现，它应该在第一次调用时返回false——不需要检查堆栈或向前看。然后我们再次调用expr()，此时oracle会返回true，但是我们不是左递归调用expr()，而是用上次调用保存的结果替换它。瞧，预期的“+”运算符后跟术语也出现了，所以我们将得到foo+bar。我们重复这个过程，事情再次变得清晰起来：这次我们得到了完整表达式的解析树，它是正确的左递归((foo+bar)+baz)。然后我们再次重复这个过程，这一次oracle返回true并且上次调用保存的结果可用，下一步没有'+'运算符，第一个选择无效。所以我们尝试第二种选择，它成功了，准确地找到了原始术语（'foo'）。与之前的调用相比，这是一个糟糕的结果，因此我们在这里停止并保留最长的解析（即(foo+bar)+baz）。为了将其转化为实际工作代码，我首先稍微重写了代码以将对oracle()的调用与对expr()的左递归调用结合起来。我们称之为oracle_expr()。代码：defexpr():iforacle_expr()andexpect('+')andterm():returnTrueifterm():returnTruereturnFalse接下来，我们将编写一个实现上述逻辑的装饰器。它使用一个全局变量（别担心，我稍后会更改）。oracle_expr()函数将读取此全局变量并由装饰器对其进行操作：saved_result=Nonedeforacle_expr():如果saved_result为None：返回False)ifnotnew_result:breaknew_parsed_length=ifnew_parsed_length<=parsed_length:breaksaved_result=new_resultparsed_length=new_parsed_lengthreturnsaved_result这个过程当然是可悲的，但它显示了代码试试看，把它开发成一些东西我们可以自豪。决定性的见解（这是我自己的，虽然我可能不是第一个想到它的人）是我们可以使用记忆缓存而不是全局变量，将一次调用的结果保存到下一次，然后我们不不需要额外的oracle_expr()函数-我们可以生成对expr()的标准调用，无论它是否处于左递归位置。为此，我们需要一个单独的@memoize_left_rec装饰器，它仅用于左递归规则。它通过从内存缓存中获取保存的值来充当oracle_expr()函数，并且它包含一个循环调用，只要每个新结果覆盖比前一个结果更长的部分，就会重复调用expr()。当然，因为memoization分别处理每个输入位置和每个解析方法的缓存，所以它不受回溯或多重递归规则的影响（例如，在玩具语法中，我一直使用expr和term都是左递归的）。我在第3篇文章中创建的基础结构的另一个不错的特性是，它更容易检查新结果是否比旧结果长：mark()方法返回标记输入数组的索引，因此我们可以使用它，而不是上面的parsed_length。我无法证明为什么这个算法总是有效，无论语法多么疯狂。那是因为我还没有真正读过那个证明。我已经看到它适用于简单的情况，比如玩具语法中的expr，但也适用于更复杂的情况（例如，涉及隐藏在替代项中的可选条目后面的左递归，或多个规则之间的相互递归），但我能想到的最复杂的情??况of在Python的语法中仍然相当良性，所以我可以相信这个定理和证明它的人。所以让我们坚持下去并展示一些真实的代码。首先，解析器生成器必须检测哪些规则是左递归的。这是图论中已解决的问题。我不会在这里展示算法，事实上我会进一步简化事情并假设文法中唯一的左递归规则是直接左递归的，就像我们的玩具文法中的expr一样。然后检查左递归只需要寻找以当前规则名称开头的替代方案。我们可以这样写：defis_left_recursive(rule):foraltinrule.alts:ifalt[0]==rule.name:returnTruereturnFalse现在我们修改解析器生成器，以便为左递归规则生成一个不同的装饰器。回想一下，在第3篇文章中，我们用@memoize装饰了所有的解析方法。我们现在对生成器做一个小修改，对于左递归规则，我们替换@memoize_left_rec然后我们在memoize_left_rec装饰器中施展魔法。生成器的其余部分和支持代码无需更改！（但是我不得不摆弄可视化代码。)作为参考，这里是从第3部分复制的原始@memoize装饰器。请注意，self是一个具有memo属性（使用空字典初始化）的Parser实例，mark()和reset()方法用于获取和设置分词器的当前位置：defmemoize(func):defmemoize_wrapper(self,*args):pos=self.mark()memo=self.memos.get(pos)如果memo为None:memo=self.memos[pos]={}key=(func,args)ifkeyinmemo:res,endpos=memo[key]self.reset(endpos)else:res=func(self,*args)endpos=self.mark()memo[key]=res,endposreturnresreturnmemoize_wrapper@memoizedecoratorineach输入位置记住之前的调用-在输入标记的（惰性）数组中的每个位置，都有一个单独的备忘录字典。memoize_wrapper函数的前四行与获取正确的备忘录字典有关。这是@memoize_left_rec。只有else分支与上面的@memoize不同：defmemoize_left_rec(func):defmemoize_left_rec_wrapper(self,*args):pos=self.mark()memo=self.memos.get(pos)ifmemoisNone:memo=self.memos[pos]={}key=(func,args)ifkeyinmemo:res,endpos=memo[key]self.reset(endpos)else:#初始化缓存失败。memo[key]=lastres,lastpos=None,pos#循环直到不再解析。whileTrue:self.reset(pos)res=func(self,*args)endpos=self.mark()如果endpos<=lastpos:breakmemo[key]=lastres,lastpos=res,endposres=lastresself.reset(lastpos)returnresreturnmemoize_left_rec_wrapper它可能有助于显示生成的expr()方法，因此我们可以跟踪装饰器和装饰方法之间的流程：@memoize_left_recdefexpr(self):pos=自我。mark()if((expr:=self.expr())和self.expect('+')and(term:=self.term())):returnNode('expr',[expr,term])self.reset(pos)ifterm:=self.term():returnNode('term',[term])self.reset(pos)returnNone让我们尝试分别解析foo+bar+baz当你调用装饰器时expr()函数，装饰器“拦截”调用，它在当前位置查找之前的调用。在第一次调用时，它进入else分支，在那里它重复调用未修饰的函数。当未修饰的函数调用expr()时，this当然指向修饰后的版本，所以递归调用再次被拦截。递归在这里停止，因为备忘录缓存现在命中了。下一步是什么？初始缓存值来自这一行：#Primethecachewithafailure。memo[key]=lastres,lastpos=None,pos这使得修饰的expr()返回None，第一个if中的expr()将失败（在expr:=self.expr()中）。所以我们继续第二个if，它成功地识别了一个术语（在我们的例子中是'foo'），并且expr返回一个Node实例。它回到了哪里？到装饰器内的while循环。这个新结果更新备忘录缓存（该节点实例）并开始下一次迭代。未修饰的expr()再次被调用，这次拦截的递归调用返回新缓存的Node实例（一个术语）。这样就成功了，继续调用expect('+')。这再次成功，我们现在处于第一个“+”运算符处。在此之后，我们寻找一个术语，它也成功了（找到'bar'）。因此，对于一个空的expr()，foo+bar到目前为止已经被识别，回到while循环，它经历相同的过程：用新的（更长的）结果更新备忘录缓存，并开始下一次迭代。游戏又开始了。截获的递归expr()调用再次从缓存中检索新结果（这次是foo+bar），我们期待并找到另一个'+'（第二个）和另一个术语（'baz'）。我们构造一个表示(foo+bar)+baz的Node并将其返回给while循环，while循环将其填充到memo缓存中并再次迭代。但下一次情况会有所不同。有了新的结果，我们寻找另一个'+'，但没有！所以这个expr()调用退回到它的第二个选择，并返回一个糟糕的术语。到了while循环时，失望的是这个结果比上一个短，break，将较长的结果((foo+bar)+baz)返回给原来的调用，初始化外层expr()调用的地方（例如，statement()调用-此处未显示）。今天的故事到此结束：我们已经成功地在PEG（-ish）解析器中驯服了左递归。至于下周，我将讨论向语法添加“动作”，以便我们可以自定义它为给定替代方法的解析方法返回的结果（而不是总是返回一个Node实例）。如果您想尝试代码，请参阅GitHub存储库。（我还添加了左递归的可视化代码，但我对它不是特别满意，所以我不打算在这里链接它。）本内容和示例代码的许可：CCBY-NC-SA4.0关于作者：GuidovanRossum，Python的创造者，在2018年7月12日退位之前，一直是“终生仁慈的独裁者”。目前，他是新的最高决策层级的五名成员之一，并在社区中保持活跃。本文来自他在Medium博客上写的解析器系列，还在连载中，每周日更新。译者简介：猫下豌豆花，出生于广东，毕业于武汉大学，现为苏飘程序员。他有一些极客思维，有一些人文情怀，有一些温暖，有一些态度。公众号：“蟒猫”（python_cat）。公众号【Python猫】，本号连载系列精品文章，包括喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐与翻译等，欢迎收看注意。
