共计 4189 个字符，预计需要花费 11 分钟才能阅读完成。
几年前，有人问 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 语言增加扩大的家庭手工业（译注：ast 模块为 Python 的三方扩大提供了便当）。（借助 parser 模块，解析树同样能面向 Python 的用户凋谢，但它应用起来太麻烦了，因而相比于 ast 模块，它就过期了。）
综上所述， 我当初的想法是看看是否为 CPython 发明一个新的解析器，在解析时，应用 PEG 与 packrat parsing 来间接构建 AST，从而跳过两头解析树结构，并尽可能地节俭内存，只管它会应用有限的前向缓冲。
我还没停顿到这个境地，但曾经有了一个原型，能够将一个 Python 的子集编译成一个 AST，其速度与以后 CPython 的解析器大抵相当。只不过，它占用的内存更多，所以我预计在将它扩大到整个语言时，将会升高 PEG 解析器的速度。
然而，我还没去优化它，所以还是挺有心愿的。
转换成 PEG 的最初一个益处是它为语言的将来演变提供了更大的灵活性。
过来有人曾说，pgen 的 LL(1) 缺点帮忙了 Python 放弃语法的简略。这很有情理，但咱们还有很多适当的流程，能够避免语言不受管制地收缩（次要是 PEP 流程，在十分严格的向后兼容性要求以及新的治理构造的帮忙下）。所以我并不放心。
以上就是本次分享的所有内容，想要理解更多 python 常识欢送返回公众号：Python 编程学习圈 ，发送“J”即可收费获取，每日干货分享