本周，我们使解析器生成器“独立”，也就是说，它将生成自己的解析器。
因此，我们已经有一个解析器生成器，其中一部分是语法解析器。 我们可以称其为元解析器。 元解析器的工作原理与生成的解析器类似： GrammarParser继承自Parser并使用相同的mark() / reset() / hope()机制。 但是，所有内容都是手工编写的。 但是，对吗？
在设计编译器时，习惯上以编译器的语言编写编译器。 我满怀爱意地记得，我第一次学习编程的时候使用的Pascal编译器是用Pascal本身编写的，GCC是用C编写的，而Rust编译器是用Rust编写的。
怎么做？ 从一开始，就为另一种语言的语言的子集或早期版本实现编译器。 （让我提醒您，原始的Pascal编译器是用FORTRAN编写的！）然后，新的编译器将以目标语言编写，并使用一开始就实现的引导程序编译器进行编译。 一旦新的编译器开始能够正常工作，就将删除引导编译器，并且该语言或编译器的每个后续版本都将限制为可以使用先前版本的编译器进行编译的版本。
让我们为元解析器做一下。 我们将为文法（元文法）编写文法，然后从中生成一个新的元解析器。 幸运的是，我从一开始就计划了此举，所以这将非常简单。 我们在上一集中添加的操作是重要的组成部分，因为我们不需要更改生成器，因此需要创建兼容的数据结构。
这是不带操作的元图的简化版本：
start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING
我将向您展示如何从底部到顶部添加操作。 回想一下第3部分，有一些Rule对象具有name和alts 。 最初， alts只是行列表的列表（替代项的外部列表，替代项的每个元素的内部列表），但是为了实现操作，我对其进行了更改，以使替代items由具有items和action属性的Alt对象表示。 元素仍然表示为简单字符串。 对于item我们得到：
item: NAME { name.string } | STRING { string.string }
这需要一些解释：分析器处理令牌时，它将返回具有type ， string和其他属性的TokenInfo对象。 我们不希望生成器处理TokenInfo对象，因此此处的操作从令牌中提取字符串。 请注意，对于所有大写标记，例如NAME ，生成的解析器都使用字符串版本（此处为name ）作为变量的名称。
接下来是应该返回字符串列表的items ：
items: item items { [item] + items } | item { [item] }
在这里，我使用右递归规则，因此我们不依赖于第5部分中添加的处理左递归。 item列出，但递归items未列出，因为它已经是列表。
创建Alt对象的alt规则：
alt: items { Alt(items) }
我将省略rules和start的动作，因为它们是通过这种方式定义的。
但是，有两个悬而未决的问题。 首先，如何找到Rule和Alt类的定义？ 为此，我们需要在生成的代码中添加几个import语句。 最简单的方法是将标志传递给生成器，该生成器说“这是一个元语法”，然后让生成器在生成的程序的开头插入其他import 。 但是既然有了动作，许多其他解析器也将希望自定义其导入，所以为什么不看看我们是否可以实现更通用的方法。
有很多方法可以实现它。 一种简单而通用的机制是在语法顶部添加“变量定义”部分，并允许生成器使用这些变量来控制所生成代码的各个方面。 我决定使用@符号开始定义变量，然后使用变量名称（ NAME ）和值（ STRING ）。 例如，我们可以将以下代码块放在元语法的顶部：
@subheader "from grammar import Rule, Alt"
解析器生成器将在标准导入后打印subheader变量的值，该默认导入是默认添加的（例如，导入memoize ）。 如果您需要多个import元素，则可以使用带三引号的字符串，例如，
@subheader """ from token import OP from grammar import Rule, Alt """
这很容易添加到元语法中：我们将start规则分解为以下内容：
start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE
（我不记得为什么我称它为“元”，但是我在编写代码时选择了这个名称，所以我会坚持下去。
我们必须将其添加到引导元分析器中。 现在，语法不仅仅是一个规则列表，让我们添加一个带有metas和rules属性的语法对象。 我们可以设置以下操作：
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) }
（请注意， meta返回一个元组；并且它使用eval()处理字符串引号。）
我没有在alt规则中提及执行动作！ 原因是它们有点杂乱。 但是进一步推迟没有任何意义，因此在这里：
alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
定义中的污垢是由于我希望使花括号之间的任意Python代码有效，包括嵌套在另一个花括号中。 为此，我们使用一个特殊的OP令牌，该令牌为Python识别的所有标点生成令牌生成器（为多字符运算符（如<=或**返回OP类型的单个令牌）。 Python表达式中可能出现的其他唯一标记是名称，数字和字符串。 因此，看起来动作的大括号之间的代码似乎可以通过NAME | NUMBER | STRING | OP重复来表示NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP 。
las，这将不起作用，因为OP也匹配花括号，并且由于PEG分析器总是贪婪，这将捕获结束括号，而我们将永远看不到操作的结束。 因此，我们进行了一些调整，允许操作引发替代选择错误，并返回None。 我不知道这在其他PEG解析器中是否是标准现象-当我不得不解决识别闭合括号（即使没有嵌套对）的问题时，我是当场提出来的。 这似乎运作良好，并且我认为它适合PEG分析的总体原理。 这可以被视为一种特殊的预见性（我将在下面讨论）。
使用这个小技巧，我们就可以将OP的比较放到大括号中。 这样就可以比较stuff和action 。
有了这些东西，元语法就可以由引导元解析器解析，并且生成器可以将其转换为可以自我分析的新元解析器。 而且，重要的是，新的元解析器仍可以解析相同的元语法。 如果我们使用新的meta编译器编译meta语法，则结果是相同的：这证明生成的meta解析器可以正常工作。
这是完整的动作元语法。 他可以分析自己，因为他知道如何组合长线：
@subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
现在我们有了一个有效的元语法，我们几乎准备进行一些改进。
但是首先，您需要考虑一下：空行！ 事实证明，stdlib tokenize模块创建了其他标记来跟踪无关紧要的tokenize （ NL标记）和注释（ COMMENT标记）。 与其将它们包括在语法中（我尝试过，没有什么好玩的！），而是有一段非常简单的代码，我们可以将其添加到tokenizer类中以对其进行过滤。 这是改进的peek_token方法：
def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos]
这将完全删除NL和COMMENT标记，因此我们不再需要担心它们在语法上的问题。
最后，让我们对元语法进行改进！ 它们将纯粹是装饰性的：当我被迫将所有替代项写成一行时，我不喜欢它。 由于上述原因，我在上面显示的元语法实际上并未对其自身进行解析：
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
这是由于令牌生成器在第一行的末尾创建了NEWLINE令牌，并且此时元分析器会将其视为规则的结尾。 此外，此NEWLINE后面将有INDENT令牌，因为下一行是缩进的。 在下一条规则开始之前，还将存在DEDENT令牌。
这是处理方法。 为了了解tokenize模块的行为，我们可以通过将tokenize模块作为脚本运行并向其传递一些文本来查看为缩进块生成的令牌序列：
$ python -m tokenize foo bar baz dah dum ^D
我们看到这会产生以下令牌序列（我简化了上面代码的输出）：
NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE
因此，由INDENT和DEDENT指示选定的字符串组。 现在，我们可以按如下所示重写rule的元语法rule ：
rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts }
（我将这些动作分成几行，以便它们在狭窄的文本列中正常读取。这是可能的，因为令牌生成器会忽略相应花括号内的换行符。）
这样做的好处是，我们甚至不需要更改生成器：通过改进的元语法创建的数据结构与以前相同。 还请注意rule的第三个选项：这使我们可以编写：
start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
有些人可能会发现它比我之前显示的版本更干净。 两种形式都易于解析，因此我们无需争论样式。
在下一篇文章中，我将展示如何实现各种PEG功能，例如可选元素，重复和工具提示。 （说实话，我计划在本文中讨论它们，但是它已经太大了。因此，我将其分为两部分。）
本文和引用代码的许可： CC BY-NC-SA 4.0