几年前，有人问 Python 是否会转换用 PEG 解析器（或者是 PEG 语法，我不记得确切内容、谁说的、什么时候说的）。
我稍微看过这个主题，但没有头绪，就放弃了。
最近，我学了很多关于 PEG（Parsing Expression Grammars）的知识，如今我认为它是个有趣的替代品，正好替换掉我在 30 年前刚开始创造 Python 时自制的（home-grown）语法分析生成器（parser generator）（那个语法分析生成器，被称为“pgen”，是我为 Python 写下的第一段代码）。
我现在感兴趣于 PEG，原因是对 pgen 的局限性感到有些恼火了。
它使用了我自己写的 LL(1) 解析的变种——我不喜欢可以产生空字符串的语法规则，所以我禁用了它，进而稍微地简化了生成解析表的算法。
同时，我还发明了一套类似 EBNF 的语法符号（译注：
Extended Backus-Naur Form，BNF 的扩展，是一种形式化符号，用于描述给定语言中的语法），至今仍非常喜欢。
以下是 pgen 令我感到烦恼的一些问题。
LL(1) 名字中的 “1” 表明它只使用单一的前向标记符（a single token lookahead），而这限制了我们编写漂亮的语法规则的能力。
例如，一个 Python 语句（statement）既可以是表达式（expression），又可以是赋值（assignment）（或者是其它东西，但那些都以 if 或 def 这类专用的关键字开头）。
我们希望使用 pgen 表示法来编写如下的语法。
（请注意，这个示例描述了一种玩具语言（toy language），它是 Python 的一个微小的子集，就像传统中的语言设计一样。
）
statement: assignment | expr | if_statement
expr: expr '+' term | expr '-' term | term
term: term '*' atom | term '/' atom | atom
atom: NAME | NUMBER | '(' expr ')'
assignment: target '=' expr
target: NAME
if_statement: 'if' expr ':' statement
关于这些符号，解释几句：
NAME
和
NUMBER
是标记符（token），预定义在语法之外。
引号中的字符串如 '+' 或 'if' 也是标记符。
（我以后会讲讲标记符。
）语法规则以其名称开头，跟在后面的是
:
号，再后面则是一个或多个以
|
符号分隔的可选内容（alternatives）。
但问题是，如果你这样写语法，解析器不会起作用，pgen 将会罢工。
其中一个原因是某些规则（如
expr
和
term
）是左递归的，而 pgen 还不足以聪明地解析。
这通常需要通过重写规则来解决，例如（在保持其它规则不变的情况下）：
expr: term ('+' term | '-' term)*
term: atom ('*' atom | '/' atom)*
这就揭示了 pgen 的一部分 EBNF 能力：
你可以在括号内嵌套可选内容，并且可以在括号后放
*
来创建重复，所以这里的
expr
规则就意味着：
它是一个术语（term），跟着零个或多个语句块，语句块内是加号跟术语，或者是减号跟术语。
这个语法兼容了第一个版本的语言，但它并没有反映出语言设计者的本意——尤其是它并没有表明运算符是左绑定的，而这在你尝试生成代码时非常重要。
但是在这种玩具语言（以及在 Python）中，
还有另一个烦人的问题。
由于前向的单一标记符，解析器无法确定它查看的是一个表达式的开头，还是一个赋值。
在一个语句的开头，解析器需要根据它看到的第一个标记符，来决定它要查看的
statement
的可选内容。
（为什么呢？
pgen 的自动解析器就是这样工作的。
）
假设我们的程序是这样的：
answer = 42
这句程序会被解析成三个标记符：
NAME
（值是
answer
），‘=’ 和
NUMBER
（值为 42）。
在程序开始时，我们拥有的唯一的前向标记符是
NAME
。
此时，我们试图满足的规则是
statement
（这个语法的起始标志）。
此规则有三个可选内容：
expr
、
assignment
以及
if_statement
。
我们可以排除
if_statement
，因为前向标记符不是 “if”。
但是
expr
与
assignment
都能以
NAME
标记符开头，因此就会引起歧义（ambiguous），pgen 会拒绝我们的语法。
（这也不完全正确，因为语法在技术上并不会导致歧义；
但我们先不管它，因为我想不到更好的词来表达。
那么 pgen 是如何做决定的呢？
它会为每条语法规则计算出一个叫做
FIRST
组的东西，如果在给定的点上，FIRST 组出现了重叠选项，它就会抱怨）（译注：
抱怨？
应该指的是解析不下去，前文译作了罢工）。
那么，
我们能否为解析器提供一个更大的前向缓冲区，来解决这个烦恼呢？
对于我们的玩具语言，第二个前向标记符就足够了，因为在这个语法中，assignment 的第二个标记符必须是 “=”。
但是在 Python 这种更现实的语言中，你可能需要一个无限的前向缓冲，因为在 “=” 标记符左侧的东西可能极其复杂，例如：
table[index + 1].name.first = 'Steven'
在 “=” 标记符之前，它已经用了 10 个标记符，如果想挑战的话，我还可以举出任意长的例子。
为了在 pgen 中解决它，我们的方法是修改语法，并增加一个额外的检查，令它能接收一些非法的程序，但如果检查到对左侧的赋值是无效的，则会抛出一个
SyntaxError
。
对于我们的玩具语言，这可归结成如下写法：
statement: assignment_or_expr | if_statement
assignment_or_expr: expr ['=' expr]
（方括号表示了一个可选部分。
）然后在随后的编译过程中（比如，在生成字节码时），我们会检查是否存在 “=”，如果存在，我们再检查左侧是否有
target
语法。
在调用函数时，关键字参数也有类似的麻烦。
我们想要写成这样（同样，这是 Python 的调用语法的简化版本）：
call: atom '(' arguments ')'
arguments: arg (',' arg)*
arg: posarg | kwarg
posarg: expr
kwarg: NAME '=' expr
但是前向的单一标记符无法告诉解析器，一个参数的开头中的
NAME
到底是
posarg
的开头（因为
expr
可能以
NAME
开头）还是
kwarg
的开头。
同样地，Python 当前的解析器在解决这个问题时，是通过特别声明：
arg: expr ['=' expr]
然后在后续的编译过程中再解决问题。
（我们甚至出了点小错，允许了像
foo((a)=1)
这样的东西，给了它跟
foo(a=1)
相同的含义，直到 Python 3.8 时才修复掉。
）
那么，
PEG 解析器是如何解决这些烦恼的呢？
通过使用无限的前向缓冲！
PEG 解析器的经典实现中使用了一个叫作“packrat parsing”（译注：
PackRat，口袋老鼠）的东西，它不仅会在解析之前将整个程序加载到内存中，而且还能允许解析器任意地回溯。
虽然 PEG 这个术语主要指的是语法符号，但是以 PEG 语法生成的解析器是可以无限回溯的递归下降（recursive-descent）解析器，“packrat parsing”通过记忆每个位置所匹配的规则，来使之生效。
这使一切变得简单，然而当然也有成本：
内存。
三十年前，我有充分的理由来使用单一前向标记符的解析技术：
内存很昂贵。
LL(1) 解析（以及其它技术像 LALR(1)，因 YACC 而著名）使用状态机和堆栈（一种“下推自动机”）来有效地构造解析树。
幸运的是，运行 CPython 的计算机比 30 年前有了更多的内存，将整个文件存在内存中确实已不再是一个负担。
例如，我能在标准库中找到的最大的非测试文件是
_pydecimal.py
，它大约有 223 千字节（译注：
kilobytes，即 KB）。
在一个 GB 级的世界里，这基本不算什么。
这就是令我再次研究解析技术的原因。
但是，
当前 CPython 中的解析器还有另一个 bug 我的东西。
编译器都是复杂的，CPython 也不例外：
虽然 pgen-驱动的解析器输出的是一个解析树，但是这个解析树并不直接用作代码生成器的输入：
它首先会被转换成抽象语法树（AST），然后再被编译成字节码。
（还有更多细节，但在这我不关注。
）
为什么不直接从解析树编译呢？
这其实正是它最早的工作方式，但是大约在 15 年前，我们发现编译器因为解析树的结构而变得复杂了，所以我们引入了一个单独的 AST，还引入了一个将解析树翻译成 AST 的环节。
随着 Python 的发展，AST 比解析树更稳定，这减少了编译器出错的可能。
AST 对于那些想要检查（inspect）Python 代码的第三方代码，也更加容易，它还通过被大众欢迎的
ast
模块而公开。
这个模块还允许你从头构建 AST 节点，或是修改现有的 AST 节点，然后你可以将新的节点编译成字节码。
后一项能力支撑起了一整个为 Python 语言添加扩展的家庭手工业（译注：
