Python 之父再发文：构建一个 PEG 解析器

我们再补充一个便利方法peek_token()，它返回下一个标记且不推进索引。

然后，这就成了Tokenizer类的核心代码：

classTokenizer:definit(self,tokengen):“”“Callwithtokenize.generate_tokens(…).”““self.tokengen=tokengenself.tokens=[]self.pos=0defmark(self):returnself.posdefreset(self,pos):self.pos=posdefget_token(self):token=self.peek_token()self.pos+=1returntokendefpeek_token(self):ifself.pos==len(self.tokens):self.tokens.append(next(self.tokengen))returnself.tokens[self.pos]

现在，仍然缺失着很多东西（而且方法和实例变量的名称应该以下划线开头），但这作为TokenizerAPI的初稿已经够了。

解析器也需要变成一个类，以便可以拥有statement()、expr()和其它方法。

标记器则变成一个实例变量，不过我们不希望解析方法（parsingmethods）直接调用get_token()——相反，我们给Parser类一个expect()方法，它可以像解析类方法一样，表示执行成功或失败。

expect()的参数是一个预期的标记——一个字符串（像“+”）或者一个标记类型（像NAME）。

讨论完了解析器的输出，我继续讲返回类型（returntype）。

在我初稿的解析器中，解析函数只返回True或False。那对于理论计算机科学来说是好的（解析器要解答的那类问题是“语言中的这个是否是有效的字符串？”），但是对于构建解析器却不是——相反，我们希望用解析器来创建一个AST。

所以我们就这么办，即让每个解析方法在成功时返回Node对象，在失败时返回None。

该Node类可以超级简单：

classNode:definit(self,type,children):self.type=typeself.children=children

在这里，type表示了该AST节点是什么类型（例如是个“add”节点或者“if”节点），children表示了一些节点和标记（TokenInfo类的实例）。

尽管将来我可能会改变表示AST的方式，但这足以让编译器生成代码或对其作分析了，例如linting（译注：不懂）或者是静态类型检查。

为了适应这个方案，expect()方法在成功时会返回一个TokenInfo对象，在失败时返回None。为了支持回溯，我还封装了标记器的mark()和reset()方法（不改变API）。

这是Parser类的基础结构：

classParser:definit(self,tokenizer):self.tokenizer=tokenizerdefmark(self):returnself.tokenizer.mark()defreset(self,pos):self.tokenizer.reset(pos)defexpect(self,arg):token=self.tokenizer.peek_token()iftoken.type==argortoken.string==arg:returnself.tokenizer.get_token()returnNone

同样地，我放弃了某些细节，但它可以工作。

在这里，我有必要介绍解析方法的一个重要的需求：一个解析方法要么返回一个Node，并将标记器定位到它能识别的语法规则的最后一个标记之后；要么返回None，然后保持标记器的位置不变。

如果解析方法在读取了多个标记之后失败了，则它必须重置标记器的位置。这就是mark()与reset()的用途。请注意，expect()也遵循此规则。

所以解析器的实际草稿如下。请注意，我使用了Python3.8的海象运算符（:=）：

classToyParser(Parser):defstatement(self):ifa:=self.assignment():returnaife:=self.expr():returneifi:=self.if_statement():returnireturnNonedefexpr(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):#Verysimilar…defatom(self):iftoken:=self.expect(NAME):returntokeniftoken:=self.expect(NUMBER):returntokenpos=self.mark()ifself.expect(“(”):ife:=self.expr():ifself.expect(“)”):returneself.reset(pos)returnNone

我给读者们留了一些解析方法作为练习（这实际上不仅仅是为了介绍解析器长什么样子），最终我们将像这样从语法中自动地生成代码。

NAME和NUMBER等常量可从标准库的token库中导入。（这能令我们快速地进入Python的标记过程；但如果想要构建一个更加通用的PEG解析器，则应该探索一些其它方法。）

我还作了个小弊：expr是左递归的，但我的解析器用了右递归，因为递归下降解析器不适用于左递归的语法规则。

有一个解决方案，但它还只是一些学术研究上的课题，我想以后单独介绍它。你们只需知道，修复的版本与这个玩具语法并非100%相符。

我希望你们得到的关键信息是：

如果所有的解析方法都遵守这些规则，则不必在单个解析方法中使用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

但我发现这太“神奇”了——在阅读这些代码时，你必须清醒地意识到每个解析方法（以及expect()）都可能会引发异常，而这个异常会被with语句的上下文管理器捕获并忽略掉。

这相当不寻常，尽管肯定会支持（通过从exit返回true）。

还有，我的最终目标是生成C，不是Python，而在C里，没有with语句来改变控制流。

不管怎样，下面是未来的一些主题：