Python 之父新发文,将替换现有解析器

几年前,有人问 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),然后再被编译成字节码。(还有更多细节,但在这我不关注。)
【Python 之父新发文,将替换现有解析器】为什么不直接从解析树编译呢?这其实正是它最早的工作方式,但是大约在 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” 即可免费获取,每日干货分享
Python 之父新发文,将替换现有解析器
文章图片

    推荐阅读