花猫语：Python之父在Medium上开了博客，现在已经写了两篇了。本文是第二篇文章的译文。上一篇文章的翻译，在这里，宣布当前的pgen解析器将被PEG解析器取代。本文主要介绍构建PEG解析器的总体思路，介绍一些基本的语法规则。根据Python之父的描述，这个PEG解析器还是一个很一般的实验，他也预测这个解析器会在以后的系列文章中得到丰富。阅读本文就像阅读教程。虽然难懂，但感觉很神奇：我们竟然可以见证Python之父是如何思考问题，如何设计，如何一点一点丰富功能，并传承下去。这种机会很难得！我会继续关注后续文章的翻译。由于能力有限，翻译可能存在不足之处。请广大读者批评指正。本文首发于公众号【蟒猫】，未经授权请勿转载。原文地址：https://mp.weixin.qq.com/s/yU...原文标题|构建PEG解析器作者|GuidovanRossum（Python之父）译者|猫底下的豌豆花（《蟒猫》作者）原文|https://medium.com/@gvanrossum_83706/building-a-peg-parser-d4869b5958fb声明|转载仅供交流学习，欢迎转载，但请保留本文出处，请勿用于商业或非法用途。在只了解PEG解析器的一小部分之后，我受到启发，自己构建了一个。结果可能不是一个很棒的通用PEG解析器生成器-已经有很多这样的生成器（例如TatSu，用Python编写，它生成Python代码）-但它是了解PEG的好方法，推这遇见了我目标是用PEG语法构建的解析器替换CPython的解析器。在本文中，我通过展示一个简单的手写解析器来为理解解析器的工作原理打下基础。（顺便说一下，作为一个实验，我不会在这里和那里放参考链接。如果你不明白什么，请谷歌它:-)解析PEG的最常见方法是使用递归下降解析器，它可以无限回溯。以上周文章中的玩具语言为例：statement:assignment|表达式|if_statementexpr:expr'+'项|expr'-'术语|termterm：术语“*”原子|术语“/”原子|原子：名称|编号|'('expr')'assignment:target'='exprtarget:NAMEif_statement:'if'expr':'statement这种语言中的超抽象递归下降解析器将为每个尝试调用该函数的符号定义一个函数对应于备选方案。比如for语句，我们有如下函数：defstatement():ifassignment():returnTrueifexpr():returnTrueifif_statement():returnTruereturnFalse当然这是一个极其简化的版本：解析器不被认为是必要的输入和输出。让我们从输入端开始。经典解析器使用单个标记器将输入（文本文件或字符串）分解为一系列标记，例如关键字、标识符（名称）、数字和运算符。（译注：tokengenerator，或tokenizer，用于生成token标记。以下简称“tokenizer”）PEG解析器（像其他现代解析器，如ANTLR）通常统一标记化和解析过程。但对于我的项目，我选择保留单独的分词器。标记Python太复杂，我不想以PEG形式重新实现它。例如，您必须跟踪缩进（这需要标记器内部的堆栈），并且在Python中处理换行符很有趣（它们很重要，除了在匹配的括号内）。字符串的多个引号也增加了复杂性。简而言之，我不抱怨Python现有的分词器，所以我想保留它。（CPython有两种分词器，一种供解析器内部使用，用C编写，另一种在标准库中，用纯Python重写。这对我的项目很有帮助。）经典分词器通常有一个简单的接口供您进行函数调用，例如get_token()，它返回输入中的下一个标记，一次消耗几个字符。tokenize模块进一步简化了这一点：它的基础API是一个生成器，一次生成一个令牌。每个标签都是一个TypeInfo对象，它有几个字段，其中最重要的一个是标签的类型（比如NAME、NUMBER、STRING），还有一个很重要的是字符串值，表示标签是字符包括（例如abc、42或“helloworld”）。还有一些字段指示每个标记在输入文件中出现的坐标，这对于报告错误很有用。有一个特殊的标记类型ENDMARKER，它表示已经到达输入文件的末尾。如果您忽略它，并尝试获取下一个令牌，生成器将终止。题外话，回归主题。我们如何实现无限回溯？回溯要求您记住您在源代码中的位置，并能够从那里重新解析。分词器的API不允许我们重置其输入指针，但将分词流打包到数组中并在那里重置指针相对容易，因此我们将这样做。（您也可以使用itertools.tee()来完成，但根据文档中的警告，在我们的案例中它的效率可能较低。）我想您可能会首先将整个输入标记为Python列表，作为解析器，但这意味着如果文件末尾有无效标记（例如缺少右引号的字符串），并且文件之前有语法错误，您首先会收到有关标记错误的信息。我认为这是一种糟糕的用户体验，因为这种语法错误可能是导致字符串损坏的根本原因。所以我的设计是按需标记，使用的列表是惰性列表。底层API非常简单。Tokenizer对象封装了一个存储令牌及其位置信息的数组。它具有三个基本方法：get_token()返回下一个标记，并推进数组的索引（如果到达数组末尾，则从源中读取另一个标记）mark()返回数组的当前索引reset(pos)设置数组的索引（参数必须从mark()方法中获取）我们还添加了一个方便的方法peek_token()，它返回下一个标记而不推进索引。然后，这就变成了Tokenizer类的核心代码：]self.pos=0defmark(self):returnself.posdefreset(self,pos):self.pos=posdefget_token(self):token=self.peek_token()self.pos+=1返回令牌defpeek_token(self):ifself.pos==len(self.tokens):self.tokens.append(next(self.tokengen))returnself.tokens[self.pos]现在，很多东西仍然缺失（并且方法和实例变量名称应以下划线开头），但这对于TokenizerAPI的初稿来说已经足够了。解析器也需要变成一个类，这样它就可以有statement()、expr()等方法。tokenizer然后变成一个实例变量，但我们不希望解析方法直接调用get_token()——相反，我们给Parser类一个expect()方法，它可以像解析类方法一样指示成功或失败。expect()的参数是一个预期的标记——字符串（如“+”）或标记类型（如NAME）。讨论完解析器的输出后，我继续讨论返回类型。在我的解析器初稿中，解析函数只返回True或False。这对理论计算机科学来说很好（解析器要回答的问题是“这是语言中的有效字符串吗？”），但不适用于构建解析器——相反，我们想使用解析来创建AST。所以我们要做的是让每个resolve方法在成功时返回一个Node对象，在失败时返回None。Node类可以非常简单：classNode:def__init__(self,type,children):self.type=typeself.children=children其中type表示AST节点的类型（例如，“add”节点或“if"节点），子节点代表一些节点和令牌（TokenInfo类的实例）。虽然我以后可能会改变我表示AST的方式，但这足以让编译器生成代码或分析它，例如linting（译注：我不懂）或静态类型检查。为了适应这种方案，expect()方法在成功时返回一个TokenInfo对象，在失败时返回None。为了支持回溯，我还包装了标记的mark()和reset()方法（不更改API）。这是Parser类的基本结构：classParser:def__init__(self,tokenizer):self.tokenizer=tokenizerdefmark(self):returnself.tokenizer.mark()defreset(self,pos):self.分词器。reset(pos)defexpect(self,arg):token=self.tokenizer.peek_token()iftoken.type==argortoken.string==arg:returnself.tokenizer.get_token()returnNone同样，我给了去掉某些细节，但它有效。这里需要介绍一下解析方法的一个重要要求：解析方法要么返回一个Node，将tokenizer定位在它能识别的文法规则的最后一个token之后；或者返回None，然后保持分词器的位置不变。如果解析方法在读取多个标记后失败，则它必须重置标记器的位置。这就是mark()和reset()的作用。请注意，expect()也遵循此规则。所以解析器的实际草稿如下。请注意，我使用了Python3.8的海象运算符（:=）：classToyParser(Parser):defstatement(self):ifa:=self.assignment():returnaife:=self.expr():returneifi:=self.if_statement():返回ireturnNonedefexpr(self):ift:=self.term():pos=self.mark()ifop:=self.expect("+"):ife:=self.expr():returnNode("add",[t,e])self.reset(pos)ifop:=self.expect("-"):ife:=self.expr():returnNode("sub",[t,e])self.reset(pos)returntreturnNonedefterm(self):#非常相似...defatom(self):iftoken:=self.expect(NAME):返回令牌如果token:=self.expect(NUMBER):返回令牌pos=self.mark()ifself.expect("("):ife:=self.expr():if硒lf.expect(")"):returneself.reset(pos)returnNone我留下一些解析作为读者的练习（这不仅仅是为了展示解析器的样子），并且在endwe'llendupwithsomethinglike这样就可以从标准库的token库中导入NAME、NUMBER等常量，根据语法自动生成代码。（这让我们很快进入Python的标记化过程；但如果你想构建一个更通用的PEG解析器，你应该探索一些其他方法。）我也作弊了一点：expr是左递归的，但我的解析器使用右递归,因为递归下降解析器不适用于左递归文法规则。是有解决办法的，不过目前还是一些学术研究的课题，后面我想单独说一下。你只需要知道固定版本并不100%匹配这个玩具语法。我希望你得到的关键信息是：语法规则等同于解析器方法，当一个语法规则引用另一个语法规则时，它的解析方法调用另一个规则的解析方法当多个项目构成备选方案时，解析方法将调用相应的方法逐个。当一个语法规则引用一个标记时，它的解析方法将调用expect()。当一个解析方法在给定的输入位置成功识别出它的语法规则时，它为一个AST节点返回对应的AnAST节点；识别失败时返回None。当一个解析方法在消耗一个或多个标记后放弃解析时（直接或间接地，通过调用另一个成功的解析方法），它必须显式地重做设置标记的位置。这适用于放弃一种选择并尝试下一种，以及完全放弃解析如果所有解析方法都遵循这些规则，则没有必要在单个解析方法中使用mark()和reset()。你可以通过归纳来证明这一点。作为旁注，虽然使用上下文管理器和with语句而不是显式调用mark()和reset()很诱人，但这不起作用：成功时不应调用reset()！要修复它，您可以在控制流中使用异常，以便上下文管理器知道是否该重置分词器（我认为TatSu做了类似的事情）。例如，你可以这样做：defstatement(self):withself.alt():returnself.assignment()withself.alt():returnself.expr()withself.alt():returnself.if_statement()raiseParsingFailure特别地，识别括号表达式的atom()中的if语句可以变成：withself.alt():self.expect("(")e=self.expr()self.expect(")")returne但我觉得这太“神奇”——阅读这段代码时，你必须清醒地意识到每一个parse方法（和expect()）都可能抛出异常，而这个异常会被上下文管理器捕获并忽略的with声明。这是相当不寻常的，尽管肯定支持（通过从__exit__返回true）。此外，我的最终目标是生成C，而不是Python，并且在C中，没有with语句来更改控制流。不管怎样，这里有一些未来的主题：从EBNF的语法packrat解析（助记）特性生成解析代码，例如(x|y)、[xy...]、x*、x+tracing（用于调试解析器或lookahead、“切割”等PEG特性如何处理左递归规则生成C代码公众号【Python猫】，本号连载一系列优质文章，包括喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐与翻译等，欢迎关注。
