原标题|PEG解析器的元语法GuidovanRossum（Python之父）译者|”公众号作者）声明|本翻译以交流学习为目的，基于CCBY-NC-SA4.0许可协议。为便于阅读，内容略有修改。本系列的翻译已经在Github上开源，项目地址：https://github.com/chinesehuazhou/guido_blog_translation这周我们让解析器生成器完成了“自托管”，也就是让它自己生成一个解析器.首先我们有一个解析器生成器，其中一部分是解析器。我们可以称它为元解析器。这个元解析器类似于要生成的元解析器：GrammarParser继承自Parser，它使用相同的mark()/reset()/expect()机制。然而，它是手写的。但是只能手写吗？编译器设计中有一个传统，即编译器是用它编译所针对的语言编写的。还记得刚开始学编程的时候，Pascal编译器是Pascal本身写的，GCC是用C写的，Rust编译器当然是用Rust写的。这怎么可能？有一个辅助过程（bootstrap，引导程序，通常翻译为“自举”）：对于一种语言的子集或更早版本，其编译器是用其他语言编写的。（我记得原来的Pascal编译器是用FORTRAN写的！）然后用编译语言写一个新的编译器，用helper编译器编译。一旦新编译器工作得足够好，辅助编译器就会过时，每个新版本的语言或新编译器都受制于前一版本编译器的编译能力。让我们对我们的元解析器做同样的事情。我们将为语法编写一个语法（元语法），然后我们将从中生成一个新的元解析器。幸运的是，我从一开始就计划好了，所以这是一个非常简单的练习。我们在上一篇文章中添加的操作是必不可少的，因为我们不想被迫更改生成器-因此我们需要能够生成兼容的数据结构。这是没有操作的元语法的简化版本：start:rulesENDMARKERrules:rulerules|rulerrule:NAME":"altsNEWLINEalts:alt"|"替代品|altalt:itemsitems:项目items|项目：名称|自下而上显示如何添加操作。参考第3部分，我们有一些具有name和alts属性的规则对象。最初，alts只是一个包含字符串列表的列表（外部列表表示备选方案，内部列表表示备选方案的条目），但我稍微改变了一些内容以添加操作，备选方案由带有项目的Alt和动作属性对象来表示。条目仍然由纯字符串表示。对于item规则，我们有：item:NAME{name.string}|STRING{string.string}这需要一些解释：当解析器处理一个标识符时，它返回一个具有类型、字符串和其他属性的TokenInfo对象。我们不希望生成器处理TokenInfo对象，因此我们添加将从令牌中提取字符串的操作。请注意，对于像NAME这样的全大写标识符，生成的解析器使用小写版本（此处为name）作为变量名。接下来是items规则，它必须返回一个字符串列表：items:itemitems{[item]+items}|item{[item]}我在这里使用右递归规则，所以我们不依赖于添加左递归处理。（为什么不呢？让事情尽可能简单总是一个好主意。这种语法是左递归的，这不是很清楚。）请注意，各个项目是分层的，但递归项目不是，因为它已经一个列表。alt规则用于构建Alt对象：alt:items{Alt(items)}我不会介绍规则和开始规则，因为它们遵循相同的模式。但是，还有两个未解决的问题。首先，生成的代码如何知道在哪里可以找到Rule和Alt类？为此，我们需要在生成的代码中添加一些导入语句。最简单的方法是向生成器传递一个标志，上面写着“这是元语法”，并让生成器在生成的程序顶部引入一个额外的import语句。但是现在我们有了动作，许多其他解析器会想要自定义他们的导入，所以我们为什么不尝试看看我们是否可以添加更通用的功能。有很多方法可以给这只猫剥皮。一种简单而通用的机制是在语法顶部添加一段“变量定义”，让生成器使用这些变量来控制生成代码的各个方面。我选择以@字符开始变量定义，后跟变量名称(NAME)和值(STRING)。例如，我们可以将以下内容放在元语法的顶部：@subheader"fromgrammarimportRule,Alt"标准导入将始终打印（例如，goimportmemoize），之后解析器生成器将打印subheader的值变量。如果需要多次导入，可以在变量声明中使用三引号字符串，例如：@subheader"""fromtokenimportOPfromgrammarimportRule,Alt"""这个很容易加到meta语法中，我们替换start使用此规则：开始：metas规则ENDMARKER|规则ENDMARKER元数据：元元元|metameta：“@”NAMESTRINGNEWLINE（我不记得为什么我称它们为“metas”，但这是我在编写代码时选择的名称，我会继续这样称呼它。:-)我们还必须添加它到辅助元解析器。现在语法不仅仅是一系列规则，让我们添加一个具有属性元和规则的语法对象。我们可以加入这样的动作：start:metasrulesENDMARKER{Grammar(rules,metas)}|规则ENDMARKER{Grammar(rules,[])}metas:metas{[meta]+metas}|meta{[meta]}meta:"@"NAMESTRING{(name.string,eval(string.string))}（注意meta返回一个元组，注意它使用eval()来处理字符串引号。）行动，我遗漏了谈论替代规则行动！原因是这里有些混乱。但是我不能再忽略它了，让我们进入代码：alt:itemsaction{Alt(items,action)}|items{Alt(items,None)}action:"{"stuffs"}"{stuffs}stuffs:东西stuffs{stuff+""+stuffs}|东西{东西}东西：“{”东西“}”{“{”+东西+“}”}|名称{名称.string}|NUMBER{数字.string}|字符串{字符串.字符串}|OP{Noneifop.stringin("{","}")elseop.string}这种混淆是由于我希望在大括号之间允许任意Python代码描述操作，并允许成对的大括号嵌套在其中。为此，我们使用特殊标识符OP，分词器使用它来生成Python识别的所有标点字符（返回OP类型的标识符用于多字符运算符，例如<=或**）。唯一可以合法出现在Python表达式中的其他标识符是名称、数字和字符串。因此，动作最外层花括号之间的“某物”似乎是一组NAME|编号|字符串|OP。Woohoo，那没用，因为OP也匹配大括号，但由于PEG解析器是贪婪的，它会吞下右大括号，我们永远看不到动作的结束。因此，我们将对生成的解析器添加一些调整，以允许通过返回None来使替代项无效的操作。我不知道这是否是其他PEG解析器的标准——当我想到如何解决识别右括号（甚至嵌套符号）的问题时，立即想到了这种方法。它似乎运行良好，而且我认为它符合PEG解析的一般原理。它可以被看作是一种特殊形式的前瞻（我在下面描述）。使用这个小调整，我们可以在花括号出现时使OP上的匹配无效，这将通过内容和操作进行匹配。有了这些东西，元语法就可以被辅助元解析器解析，生成器可以将它转换成一个新的元解析器，从而解析自己。更重要的是，新的元解析器仍然可以解析相同的元语法。如果我们用新的元编译器编译元语法，输出是一样的：这证明生成的元解析器工作正常。这是带有操作的完整元语法。只要你把解析过程序串起来，它就可以自己解析：@subheader"""fromgrammarimportGrammar,Rule,AltfromtokenimportOP"""start:metasrulesENDMARKER{Grammar(rules,metas)}|rulesENDMARKER{Grammar(rules,[])}metas:metametas{[meta]+metas}|meta{[meta]}meta:"@"NAMESTRINGNEWLINE{(name.string,eval(string.string))}rules:rulerules{[rule]+rules}|rule{[rule]}rule:NAME":"altsNEWLINE{Rule(name.string,alts)}alts:alt"|"alts{[alt]+alts}|alt{[alt]}alt:itemsaction{Alt(items,action)}|items{Alt(items,None)}items:项目items{[item]+items}|item{[item]}item:名称{name.string}|STRING{string.string}action:"{"stuffs"}"{stuffs}stuffs:stuffstuffs{stuff+""+stuffs}|东西{东西}东西：“{”东西“}”{“{”+东西+“}”}|名称{名称.string}|NUMBER{数字.string}|字符串{字符串.字符串}|OP{Noneifop.stringin("{","}")elseop.string}现在我们有了一个可用的元语法，我们准备做一些改进，但首先，有一个小烦恼需要处理：空行！事实证明，标准库的tokenize会生成额外的标识符来跟踪重要的换行符和注释。对于前者，它生成一个NL标识符，对于后者，它生成一个COMMENT标识符。与其将它们同化到语法中（我已经尝试过，但这并不容易！），我们可以向tokenizer类添加一段非常简单的代码来过滤掉这些标记。这是改进的peek_token方法：defpeek_token(self):ifself.pos==len(self.tokens):whileTrue:token=next(self.tokengen)iftoken.typein(NL,COMMENT):continuebreakself.tokens.append(token)self.report()returnself.tokens[self.pos]这完全过滤掉了NL和COMMENT标记，因此语法中无需担心它们。最后让我们完善元语法！我想做的纯粹是装饰性的：我不喜欢被迫将所有备选方案放在同一条线上。我在上面展示的元语法实际上并没有解析自己，因为有这样的情况：start:metasrulesENDMARKER{Grammar(rules,metas)}|rulesENDMARKER{Grammar(rules,[])}这是因为标识符生成标记器在第一行的末尾生成一个NEWLINE标识符，元解析器认为这是规则的结尾。此外，INDENT标识符出现在NEWLINE之后，因为下一行是缩进的。在下一个规则开始之前还会有一个DEDENT标识符。这是解决方案。要了解tokenize模块的行为，我们可以将tokenize模块作为脚本运行并为其提供一些文本以查看为缩进块生成了哪些标记序列：$python-mtokenizefoobarbazdahdum^D我们发现它产生以下标识符序列（我简化了上面运行的输出）：NAME'foo'NAME'bar'NEWLINEINDENTNAME'baz'NEWLINENAME'dah'NEWLINEDEDENTNAME'dum'NEWLINE这意味着一组缩进通过INDENT和DEDENT标签。现在，我们可以重写元语法规则如下：rule:NAME":"altsNEWLINEINDENTmore_altsDEDENT{Rule(name.string,alts+more_alts)}|NAME":"altsNEWLINE{Rule(name.string,alts)}|NAME":"NEWLINEINDENTmore_altsDEDENT{Rule(name.string,more_alts)}more_alts:"|"altsNEWLINEmore_alts{alts+more_alts}|“|”altsNEWLINE{alts}（我跨行拆分，以便它们适合Medium网站的窄页面——这是有效的，因为标识符生成器忽略了成对括号内的换行符。）这样做的好处是我们甚至不需要更改生成器：这个改进的元语法生成与以前相同的数据结构。还要注意规则的第三个替代方案，让我们写：开始：|metas规则ENDMARKER{Grammar(rules,metas)}|rulesENDMARKER{Grammar(rules,[])}显示的版本更清晰。让两种形式共存很容易，所以我们不必争论风格。在下一篇文章中，我将展示如何实现各种PEG功能，例如可选条目、重复和前瞻。（公平地说，我本来打算把它放在这篇文章中的，但是它太长了，所以我要把它分成两部分。）这篇文章的内容和示例代码是根据CCBY-NC许可的-SA4.0公众号【Python猫】，本号连载系列精品文章，包括喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐翻译等.欢迎关注。
