查看原文
其他

Python 之父撰文回忆:为什么要创造 pgen 解析器?

豌豆花下猫 Python猫 2019-10-30

👆 Python猫” ,一个值得加星标的公众号

花下猫语:近日,Python 之父在 Medium 上开通了博客,并发布了一篇关于 PEG 解析器的文章(参见我翻的 全文译文)。据我所知,他有自己的博客,为什么还会跑去 Medium 上写文呢?好奇之下,我就打开了他的老博客。

最后一篇文章写于 2018 年 5 月,好巧不巧,写的竟是 pgen 解析器,正是他在新文中无情地吐槽的、说将要替换掉的 pgen。在这篇旧文里,Guido 回忆了他创造 pgen 时的一些考量,在当时看来,创造一个新的解析器无疑是明智的,只不过时过境迁,现在有了更好的选择罢了。

前不久,我们聊过 Python 中 GIL的移除计划内置电池的“手术”计划 以及 print的演变故事,如今,它的解析器也要迎来改造了。Python 这门语言快 30 岁了,难得地保持着活力四射。就让我们一起祝福它吧,愿未来更加美好。


原题 | The origins of pgen

作者 | Guido van Rossum(Python之父)

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

原文 | https://python-history.blogspot.com/2018/05/the-origins-of-pgen.html

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

David Beazley 在 US PyCon 2018 上的演讲,关于语法分析生成器(parser generators),提醒了我应该写一下关于它的历史。这是一个简短的脑转储(也许我今后会解释它)。

(译注:我大胆揣测一下“脑转储”吧,应该说的是,把个人的记忆以及 Python 的历史细节,转化成文字,这是个存储固化的过程,方便传承。而我做的翻译工作,就是把这份文档财富,普及给更多的 Python 爱好者。

实际上,有两个 pgen,一个是最初的,用 C 语言写的,还有一个则是用 Python 重写的,在 lib2to3/pgen2 下面。

两个都是我写的。最早那个实际上是我为 Python 编写的第一份代码。尽管从技术上讲,我必须首先编写词法分析程序(lexer)(pgen 和 Python 共用词法分析程序,但 pgen 对大多数标记符不起作用)。

之所以我要写自己的语法分析生成器,原因是当时这玩意(我熟悉的)相当稀少——基本上就是用 Yacc(有个 GNU 的重写版,叫作 Bison(译注:美洲野牛),但我不确定那时的自己是否知道);或者是自己手写一个(这是大多数人所做的)。

我曾在大学里用过 Yacc,从“龙书”中熟悉了它的工作原理,但是出于某些原因,我并不喜欢它;IIRC 关于 LALR(1) 语法的局限性,我很难解释清楚。

(译注:1、龙书,原文是 Dragon book,指代《Compilers: Principles, Techniques, and Tools》,这是一本讲编译原理的书,属于编译原理界的殿堂级存在。另外还有两本经典著作,称号分别是“虎书”、“鲸书”,三者常常一起出现。2、IIRC,If I Remember Correctly,如果我没记错。

集齐三书,可以召唤神龙?

我也熟悉 LL(1) 解析器,并已认真地编写过一些递归下降的 LL(1) 解析器——我很喜欢它,而且还熟悉 LL(1) 解析器的生成技术(同样是因为龙书),所以我有了一个改进念头想要试验下:使用正则表达式(某种程度的)而不是标准的 BNF 格式。

龙书还教会了我如何将正则表达式转换成 DFA,所以我把所有这些东西一结合,pgen 就诞生了。【更新:请参阅下文,对于这个理由,有个略微不同的版本。】

我曾不熟悉更高级的技术,或者曾认为它们效率太低。(在当时,我觉得工作在解析器上的大多数人都是这样。)

至于词法分析器(lexer),我决定不使用生成器——我对 Lex 的评价要比 Yacc 低得多,因为在尝试扫描超过 255 个字节的标记符时,我所熟悉的 Lex 版本会发生段错误(真实的!)。此外,我认为缩进格式很难教给词法分析器生成器。

(译注:1、这里的生成器并非 Python 语法中的生成器,而是指用来生成分析器的工具。Lex 是“LEXical compiler”的简称,用来生成词法分析器;Yacc 是“Yet another compiler compiler”的简称,用来生成语法分析器。2、段错误,原文是 segfault,全称是segmentation fault,指的是因为越界访问内存空间而导致的报错。

pgen2 的故事则完全不同。

我曾受雇于 San Mateo 的一家创业公司(即 Elemental Security,倒闭于 2007,之后我离开并加入了 Google),在那我有一项设计定制语言的任务(目标是作关于系统配置的安全性判定),并拥有相当大的自主权。

我决定设计一些稍微像 Python 的东西,用 Python 来实现,并且决定要重用 pgen,但是后端要基于 Python,使用 tokenize.py 作为词法分析器。所以我用 Python 重写了 pgen 里的那些算法,然后继续构建了剩余的部分。

管理层觉得把工具开源是有意义的,因此他们很快就批准了,而在不久之后(我当时很可能已经转移到 Google 了?),这工具对于 2to3 也是有意义的。(因为输入格式跟原始的 pgen 相同,用它来生成一个 Python 解析器很容易——我只需将语法文件喂给工具。:-)

更新:创建 pgen 的原因,还有更多故事

我不完全记得为什么要这样做了,但我刚偷看了https://en.wikipedia.org/wiki/LL_parser#Conflicts,我可能觉得这是一种新的(对我而言)不通过添加帮助性的规则而解决冲突的方式。

例如,该网页所称的的左分解(将 A -> X | X Y Z 替换成 A -> X B; B -> Y Z | <empty\>),我会重写成 A -> X [Y Z]。

如果我没记错,通过“正则表达式 -> NFA -> DFA”的转换过程,解析引擎(该网页中前面的 syntacticAnalysis 函数)依然可以工作在由这些规则所派生的解析表上;我认为这里需要有不出现空白产物的诉求。(译注:“空白产物”,原文是 empty productions,对应的是前文的 <empty\>,指的是不必要出现 empty。

我还想起一点,由解析引擎生成的解析树节点可能有很多子节点,例如,对于上面的规则 A -> X [Y Z],节点 A 可能有 1 个子节点(X)或者 3 个(X Y Z)。代码生成器中就需要有一个简单的检查,来确定它遇到的是哪一种可能的情况。(这已经被证明是一把双刃剑,后来我们添加了一个由单独的生成器所驱动的“解析树 -> AST”步骤,以简化字节码生成器。)

所以我使用正则表达式的原因,很可能是为了使语法更易于阅读:在使用了必要的重写以解决冲突之后,我发现语法不是那么可读(此处应插入《Python 之禅》的说法 :-) ,而正则表达式则更符合我对于经典语言的语法的看法(除了起着奇怪名字的帮助规则、[optional] 部分以及 * 号重复的部分)。

正则表达式没有提高 LL(1) 的能力,更没有降低它的能力。当然了,所谓“正则表达式”,我想说的其实是 EBNF ——我不确定 “EBNF” 在当时是否是一个被明确定义了的符号,它可能就指对 BNF 的任意扩展。

假如将 EBNF 转换为 BNF,再去使用它,将会导致尴尬的多解析树节点问题,所以我不认为这会是一种改进。

如果让我重做一遍,我可能会选择一个更强大的解析引擎,可能是 LALR(1) 的某个版本(例如 Yacc/Bison)。LALR(1) 的某些地方要比 LL(1) 更给力,也更加有用,例如,关键字参数。

在 LL(1) 中,规则 “arg: [NAME =] expr” 无效,因为 NAME 出现在了表达式的第一组里(FIRST-set),而 LL(1) 算法没法处理这样的写法。

如果我没记错,LALR(1) 则可以处理它。但是,在我写完 pgen 的第一个版本的好些年之后,关键字参数写法才出现,那时候我已不想重做解析器了。

2019 年 3 月更新:Python 3.8 将删除 pgen 的 C 版本,转而使用重写的 pgen2 版本。参阅 https://github.com/python/cpython/pull/11814

(译注:感觉可以帮 Guido 再加一条“更新”了,目前他正在研究 PEG 解析器,将会作为 pgen 的替代。详情请看《Python之父新发文,将替换现有解析器》)


文章分享完了,最后是随机荐书环节。我会根据文章内容,提出一个关键词(这篇是“编译原理”)来搜索,随机选择一本技术书推荐给大家,如果你感兴趣的话,可以点击链接进行了解。希望能给大家带来不经意的收获~~

我翻译了不少文章,猜你想看

1

Python 之父退位后,最高决策权花落谁家?

2

[译] PEP 255--简单的生成器

3

[译]PEP 342--增强型生成器:协程

4

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

告诉朋友们,我在看

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存