关于python:Python-之父新发文将替换现有解析器

58次阅读

共计 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”即可收费获取,每日干货分享

正文完
 0