Python 之父的解析器系列之七：PEG 解析器的元语法

原题 | ​​A Meta-Grammar for PEG Parsers​​

作者 | Guido van Rossum（Python之父）

译者 | 豌豆花下猫（“Python猫”公众号作者）

声明 | 本翻译是出于交流学习的目的，基于 ​​CC BY-NC-SA 4.0​​​ 授权协议。为便于阅读，内容略有改动。本系列的译文已在 Github 开源，项目地址：​​https://github.com/chinesehuazhou/guido_blog_translation​​

本周我们使解析器生成器完成“自托管”（self-hosted），也就是让它自己生成解析器。

首先我们有了一个解析器生成器，其中一部分是语法解析器。我们可以称之为元解析器（meta-parser）。该元解析器与要生成的解析器类似：​​GrammarParser​​​ 继承自​​Parser​​ ，它使用相同的 mark()/reset()/expect() 机制。然而，它是手写的。但是，只能是手写么？

在编译器设计中有一个传统，即编译器使用它要编译的语言编写。我深切地记得在我初学编程时，当时用的 Pascal 编译器是用 Pascal 本身编写的，GCC 是用 C 编写的，Rust 编译器当然是用 Rust 编写的。

这是怎么做到的呢？有一个辅助过程（bootstrap，引导程序，通常译作“自举”）：对于一种语言的子集或早期版本，它的编译器是用其它的语言编写的。（我记得最初的 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 篇，我们有了一些带 name 和 alts 属性的 Rule 对象。最初，alts 只是一个包含字符串列表的列表（外层列表代表备选项，内层列表代表备选项的条目），但为了添加动作，我更改了一些内容，备选项由具有 items 和 action 属性的 Alt 对象来表示。条目仍然由纯字符串表示。对于 item 规则，我们有：

item: NAME { name.string } | STRING { string.string }

这需要一些解释：当解析器处理一个标识符时，它返回一个 TokenInfo 对象，该对象具有 type、string 及其它属性。我们不希望生成器来处理 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 语句。但是既然我们已经有了动作，许多其它解析器也会想要自定义它们的导入，所以为什么我们不试试看，能否添加一个更通用的功能呢。

有很多方法可以剥了这只猫的皮（译注：skin this cat，解决这个难题）。一个简单而通用的机制是在语法的顶部添加一部分“变量定义”，并让生成器使用这些变量，来控制生成的代码的各个方面。我选择使用 @ 字符来开始一个变量定义，在它之后是变量名（一个 NAME）和值（一个 STRING）。例如，我们可以将以下内容放在元语法的顶部：

@subheader "from grammar import Rule, Alt"

标准的导入总是会打印（例如，去导入 memoize），在那之后，解析器生成器会打印 ​​subheader​​ 变量的值。如果需要多个 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”，但这是我在编写代码时选择的名称，我会坚持这样叫。