Python之父发文吐槽现有解析器,考虑将它替换掉

本文涉及的产品
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
简介: Python之父发文吐槽现有解析器,考虑将它替换掉

花下猫语: Guido van Rossum 是 Python 的创造者,虽然他现在放弃了“终身仁慈独裁者”的职位,但却成为了指导委员会的五位成员之一,其一举一动依然备受瞩目。近日,他开通了 Medium 账号,并发表了第一篇文章,透露出要替换 Python 的核心部件(解析器)的想法。这篇文章分析了当前的 pgen 解析器的诸多缺陷,并介绍了 PEG 解析器的优点,令人振奋。这项改造工作仍在进行中,Guido 说他还会写更多相关的文章,我们就拭目以待吧。

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。

原文地址: mp.weixin.qq.com/s/yqVVaZVn8…


原题 | PEG Parsers

作者 | Guido van Rossum(Python之父)

译者 | 豌豆花下猫(“Python猫”公众号作者)

原文 | medium.com/@gvanrossum…

声明 | 翻译是出于交流学习的目的,欢迎转载,但请保留本文出处,请勿用于商业或非法用途。

几年前,有人问 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

关于这些符号,解释几句:NAMENUMBER 是标记符(token),预定义在语法之外。引号中的字符串如 '+' 或 'if' 也是标记符。(我以后会讲讲标记符。)语法规则以其名称开头,跟在后面的是 : 号,再后面则是一个或多个以 | 符号分隔的可选内容(alternatives)。

但问题是,如果你这样写语法,解析器不会起作用,pgen 将会罢工。

其中一个原因是某些规则(如 exprterm)是左递归的,而 pgen 还不足以聪明地解析。这通常需要通过重写规则来解决,例如(在保持其它规则不变的情况下):

expr: term ('+' term | '-' term)*
term: atom ('*' atom | '/' atom)*

这就揭示了 pgen 的一部分 EBNF 能力:你可以在括号内嵌套可选内容,并且可以在括号后放 * 来创建重复,所以这里的 expr 规则就意味着:它是一个术语(term),跟着零个或多个语句块,语句块内是加号跟术语,或者是减号跟术语。

这个语法兼容了第一个版本的语言,但它并没有反映出语言设计者的本意——尤其是它并没有表明运算符是左绑定的,而这在你尝试生成代码时非常重要。

但是在这种玩具语言(以及在 Python)中,还有另一个烦人的问题。

由于前向的单一标记符,解析器无法确定它查看的是一个表达式的开头,还是一个赋值。在一个语句的开头,解析器需要根据它看到的第一个标记符,来决定它要查看的 statement 的可选内容。(为什么呢?pgen 的自动解析器就是这样工作的。)

假设我们的程序是这样的:

answer = 42

这句程序会被解析成三个标记符:NAME (值是 answer),‘=’ 和 NUMBER (值为 42)。在程序开始时,我们拥有的唯一的前向标记符是 NAME 。此时,我们试图满足的规则是 statement (这个语法的起始标志)。此规则有三个可选内容:exprassignment 以及 if_statement 。我们可以排除if_statement ,因为前向标记符不是 “if”。

但是 exprassignment 都能以 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 流程,在非常严格的向后兼容性要求以及新的治理结构的帮助下)。所以我并不担心。

我还有很多内容要写,关于 PEG 解析以及我的具体实现,但是要等我整理好代码后,在后续的文章中再去写了。


目录
相关文章
|
1月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
47 0
|
12天前
|
算法 Python
Python 大神修炼手册:图的深度优先&广度优先遍历,深入骨髓的解析
在 Python 编程中,掌握图的深度优先遍历(DFS)和广度优先遍历(BFS)是进阶的关键。这两种算法不仅理论重要,还能解决实际问题。本文介绍了图的基本概念、邻接表表示方法,并给出了 DFS 和 BFS 的 Python 实现代码示例,帮助读者深入理解并应用这些算法。
25 2
|
21天前
|
测试技术 开发者 Python
深入浅出:Python中的装饰器解析与应用###
【10月更文挑战第22天】 本文将带你走进Python装饰器的世界,揭示其背后的魔法。我们将一起探索装饰器的定义、工作原理、常见用法以及如何自定义装饰器,让你的代码更加简洁高效。无论你是Python新手还是有一定经验的开发者,相信这篇文章都能为你带来新的启发和收获。 ###
12 1
|
21天前
|
设计模式 测试技术 开发者
Python中的装饰器深度解析
【10月更文挑战第24天】在Python的世界中,装饰器是那些能够为函数或类“添彩”的魔法工具。本文将带你深入理解装饰器的概念、工作原理以及如何自定义装饰器,让你的代码更加优雅和高效。
|
1月前
|
XML 前端开发 数据格式
Beautiful Soup 解析html | python小知识
在数据驱动的时代,网页数据是非常宝贵的资源。很多时候我们需要从网页上提取数据,进行分析和处理。Beautiful Soup 是一个非常流行的 Python 库,可以帮助我们轻松地解析和提取网页中的数据。本文将详细介绍 Beautiful Soup 的基础知识和常用操作,帮助初学者快速入门和精通这一强大的工具。【10月更文挑战第11天】
56 2
|
1月前
|
数据安全/隐私保护 流计算 开发者
python知识点100篇系列(18)-解析m3u8文件的下载视频
【10月更文挑战第6天】m3u8是苹果公司推出的一种视频播放标准,采用UTF-8编码,主要用于记录视频的网络地址。HLS(Http Live Streaming)是苹果公司提出的一种基于HTTP的流媒体传输协议,通过m3u8索引文件按序访问ts文件,实现音视频播放。本文介绍了如何通过浏览器找到m3u8文件,解析m3u8文件获取ts文件地址,下载ts文件并解密(如有必要),最后使用ffmpeg合并ts文件为mp4文件。
|
1月前
|
Web App开发 SQL 数据库
使用 Python 解析火狐浏览器的 SQLite3 数据库
本文介绍如何使用 Python 解析火狐浏览器的 SQLite3 数据库,包括书签、历史记录和下载记录等。通过安装 Python 和 SQLite3,定位火狐数据库文件路径,编写 Python 脚本连接数据库并执行 SQL 查询,最终输出最近访问的网站历史记录。
|
1月前
|
机器学习/深度学习 算法 Python
深度解析机器学习中过拟合与欠拟合现象:理解模型偏差背后的原因及其解决方案,附带Python示例代码助你轻松掌握平衡技巧
【10月更文挑战第10天】机器学习模型旨在从数据中学习规律并预测新数据。训练过程中常遇过拟合和欠拟合问题。过拟合指模型在训练集上表现优异但泛化能力差,欠拟合则指模型未能充分学习数据规律,两者均影响模型效果。解决方法包括正则化、增加训练数据和特征选择等。示例代码展示了如何使用Python和Scikit-learn进行线性回归建模,并观察不同情况下的表现。
284 3
|
1月前
|
网络协议 Python
IP地址探秘:识别与解析的Python之旅 🚀
《IP地址探秘:识别与解析的Python之旅》通过Python的`ipaddress`模块,轻松实现IP地址的分类(如单播、多播、私有、环回或公有)及子网内所有IP的生成,使网络管理更加便捷高效。示例代码直观展示了功能实现过程。
|
1月前
|
运维 安全 网络协议
Python 网络编程:端口检测与IP解析
本文介绍了使用Python进行网络编程的两个重要技能:检查端口状态和根据IP地址解析主机名。通过`socket`库实现端口扫描和主机名解析的功能,并提供了详细的示例代码。文章最后还展示了如何整合这两部分代码,实现一个简单的命令行端口扫描器,适用于网络故障排查和安全审计。