Python之父的解析器系列之三：生成一个PEG解析器作者)statement|本翻译以交流学习为目的，基于CCBY-NC-SA4.0许可协议。为便于阅读，内容略有修改。起始地址：https://mp.weixin.qq.com/s/oj...我在本系列的第二篇文章中已经简单介绍了解析器的基本结构，并展示了一个简单的手写解析器，如约而至，我们'转向从语法生成解析器。我还将展示如何使用@memoize装饰器来启用packrat解析。[这是PEG系列的第3部分。参见Part1,Part2]在上一篇文章中，我们以一个手写的解析器结束。通过对文法施加一些约束，很容易从文法自动生成这样的解析器。（我们稍后会取消这些限制。）我们需要两件事：读取语法并构造表示语法规则的数据结构的东西，以及使用该数据结构生成解析器的东西。我们还需要无聊的胶水，这个我就不提了。所以我们在这里创建的是一个简单的编译器-编译器。我稍微简化了语法符号，只留下规则和备选方案；对于我在本系列前面使用的玩具语法来说，这实际上绰绰有余。语句：赋值|表达式|if_statementexpr:expr'+'项|expr'-'术语|termterm：术语“*”原子|术语“/”原子|原子：名称|编号|'('expr')'assignment:target'='exprtarget:NAMEif_statement:'if'expr':'statement有了完整的符号，我们就可以为文法文件写文法了：grammar:rule+ENDMARKERrule:NAME':'alternative('|'alternative)*NEWLINEalternative:item+item:NAME|STRING换句话说，这是我们的第一个元语法（语法的语法），我们的解析器生成器将是一个元编译器（编译器是将其他程序从一种语言转换为另一种语言的程序；元编译器是一个编译器，其输入是语法其输出是一个解析器）。有一种简单的元语法表达方式，主要是使用内置的数据类型：规则的右侧只是一个项目列表，这些项目只能是字符串。（技巧：我们可以通过检查第一个字符是否是引号来区分NAME和STRING）对于规则，我使用了一个简单的Rule类，所以整个语法只是一些Rule对象。这是Rule类，省略了__repr__和__eq__：请参阅我之前的帖子）：classGrammarParser(Parser):defgrammar(self):pos=self.mark()ifrule:=self.rule():rules=[rule]whilerule:=self.rule()：rules.append(rule)ifself.expect(ENDMARKER):returnrules#<------------最终结果self.reset(pos)returnNonedefrule(self):pos=self.mark()ifname:=self.expect(NAME):ifself.expect(":"):ifalt:=self.alternative():alts=[alt]apos=self.mark()while(self.expect("|")and(alt:=self.alternative())):alts.追加（alt）apos=自我。标记（）自我。关于设置（apos）如果自己。期望（NEWLINE）：返回规则（名称。字符串，替代）自我。reset(pos)returnNonedefalternative(self):items=[]而item:=self.item():items.append(item)返回项目defitem(self):ifname:=self.expect(NAME):returnname.stringifstring:=self.expect(STRING):returnstring.stringreturnNone注意ENDMARKER，它用于确保在最后一条规则之后没有遗漏任何内容（如果语法中有拼写错误可能会发生）我放了一个简单的箭头指向grammar()方法的返回值，这是一个存储规则列表。其余的和上一篇文章中的ToyParser类很像，就不做解释了。请注意item()返回一个字符串，alternative()返回一个字符串列表，而rule()中的alts变量是一个字符串列表列表。rule()方法然后将规则名称（字符串）与alts组合到Rule对象中。如果将此代码应用于包含玩具语法的文件，则grammar()方法将返回以下规则对象列表：[Rule('statement',[['assignment'],['expr'],['if_statement']]),Rule('expr',[['term',"'+'",'expr'],['term',"'-'",'term'],['term']]),Rule('term',[['atom',"'*'",'term'],['atom',"'/'",'atom'],['atom']]),Rule('atom',[['NAME'],['NUMBER'],["'('",'expr',"')'"]]),Rule('assignment',[['target',"'='",'expr']]),Rule('target',[['NAME']]),Rule('if_statement',[["'if'",'expr',"':'",'statement']]),]现在我们有了元编译器的解析部分，让我们创建代码生成器。将这些聚合起来构成一个基本的元编译器：defgenerate_parser_class(rules):print(f"classToyParser(Parser):")forruleinrules:print()print(f"@memoize")print(f"def{rule.name}(self):")打印(f"pos=self.mark()")foraltinrule.alts:items=[]print(f"if(True")foriteminalt:ifitem[0]in('"',"'"):print(f"andself.expect({item})")else:var=item.lower()ifvarinitems:var+=str(len(items))items.append(var)ifitem.isupper():print(""+f"and({var}:=self.expect({item}))")else:print(f""+f"and({var}:=self.{item}())")打印(f"):")print(f""+f"returnNode({rule.name!r},[{','.join(items)}])")print(f"self.reset(pos)")print(f"returnNone")这段代码非常难看，但它（有点）有效，反正我打算以后重写它在“foraltinrule.alts”循环中，一些代码细节可能需要解释：对于alternatives中的每一项，我们有三个选项：如果item是一个字符串文字，比如'+'，我们生成self.expect('+')如果item都是大写的，例如NAME，我们生成(name:=self.expr())否则，例如项目是expr，我们生成(expr:=self.expr())如果具有相同名称的多个条目出现在单个替代项中（例如术语“-”术语)，我们会在第二个条目后面追加一个数字。这里还有一个小bug，我会在后面的内容中修复。这只是它的输出的一部分（完整的类很无聊）。不用担心关于那些杂散的、长的if(Trueand…)语句，我使用它们以便每个生成的条件都可以以and开头。Python的字节码编译器将优化它。classToyParser(Parser):@memoizedefstatement(self):pos=self.mark()if(Trueand(assignment:=self.assignment())):returnNode('statement',[assignment])self.reset(pos)if(Trueand(expr:=self.expr())):返回Node('statement',[expr])self.reset(pos)if(Trueand(if_statement:=self.if_statement())):returnNode('statement',[if_statement])self.reset(pos)returnNone...注意@memoize装饰器：我“走私”它是为了转移到另一个主题：使用记忆方法（记忆）来加速生成的解析器。这是实现装饰器的memoize()函数：defmemoize(func):defmemoize_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:res=func(self,*args)endpos=self．)ToyParser类的方法。因为包装函数是一个方法，包装器实际上是一个方法：它的第一个参数是self，它指向调用包装函数的ToyParser实例。包装器缓存每次调用解析方法的结果——这就是它被称为“packrat解析”的原因！这个缓存是一个字典，其元素是存储在Parser实例上的那些字典。外部字典的键是输入的地方；我将self.memos={}添加到Parser.__init__()以对其进行初始化。内部字典按需添加，其键由方法及其参数组成。（在当前设计中没有参数，但我们应该记得expect()恰好有一个参数，它以很小的代价增加了通用性。)一个解析方法的结果被表示为一个元组，因为它恰好有两个结果：一个显式返回值（对于我们生成的解析器，它是一个代表匹配规则的节点），以及在self中获得的一个新的输入位置。标记（）。调用parse方法后，我们将其返回值(res)和新的输入位置(endpos)存储在一个内存字典中。当再次调用相同的解析方法时（在相同的位置，使用相同的参数），我们将从缓存中取出这两个结果，并使用self.reset()将输入位置向前移动，最后返回returnin缓存值。缓存负面结果也很重要——事实上，大多数调用resolve方法的结果都是负面的。在这种情况下，返回值为None，输入位置不变。您可以添加一个assert断言来检查它。注意：Python中常用的助记符是在memoize()函数中将缓存定义为局部变量。但我们没有：正如我在最后一分钟的调试会话中发现的那样，每个Parser实例都必须有自己的缓存。但是，您可以使用(pos,func,args)作为键来摆脱嵌套字典设计。下周我将通过代码演示所有这些模块在解析示例程序时实际上是如何协同工作的。我仍在摸索如何最好地可视化分词器缓冲区、解析器和内存缓存协同工作。也许我会尝试生成动画ASCII图稿而不仅仅是跟踪日志输出。（译注：感觉他在开玩笑，但这句话的原意很难翻译，建议阅读原文。）本文许可协议及示例代码：CCBY-NC-SA4.0英文原文：https://medium.com/@gvanrossum_83706/generating-a-peg-parser-520057d642a9关于作者：GuidovanRossum，Python的创造者，在2018年7月12日退位之前是一位“终身仁慈的独裁者”。目前，他是新的最高决策层级的五名成员，并在社区中保持活跃。译者简介：猫下豌豆花，出生于广东，毕业于武汉大学，现为苏飘程序员。他有一些极客思维，有一些人文情怀，有一些温暖，有一些态度。公众号：“蟒猫”（python_cat）。公众号【Python猫】，本号连载系列精品文章，包括喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐与翻译等，欢迎收看注意。
