image

花下貓語(yǔ)： 近日，Python 之父在 Medium 上開(kāi)通了博客，并發(fā)布了一篇關(guān)于 PEG 解析器的文章（參見(jiàn)我翻的 全文譯文）。據(jù)我所知，他有自己的博客，為什么還會(huì)跑去 Medium 上寫(xiě)文呢？好奇之下，我就打開(kāi)了他的老博客。

最后一篇文章寫(xiě)于 2018 年 5 月，好巧不巧，寫(xiě)的竟是 pgen 解析器，正是他在新文中無(wú)情地吐槽的、說(shuō)將要替換掉的 pgen 。在這篇舊文里，Guido 回憶了他創(chuàng)造 pgen 時(shí)的一些考量，在當(dāng)時(shí)看來(lái)，創(chuàng)造一個(gè)新的解析器無(wú)疑是明智的，只不過(guò)時(shí)過(guò)境遷，現(xiàn)在有了更好的選擇罷了。

前不久，我們聊過(guò) Python 中 GIL 的移除計(jì)劃、內(nèi)置電池的“手術(shù)”計(jì)劃 以及 print 的演變故事，如今，它的解析器也要迎來(lái)改造了。Python 這門(mén)語(yǔ)言快 30 歲了，還難得地保持著活力四射。就讓我們一起祝福它吧，愿未來(lái)更加美好。

本文原創(chuàng)并首發(fā)于公眾號(hào)【 Python貓 】，未經(jīng)授權(quán)，請(qǐng)勿轉(zhuǎn)載。

原文地址：https://mp.weixin.qq.com/s/ovIiw7ZmXJM4qUSTGDk7kQ

原題 | The origins of pgen

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號(hào)作者）

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

聲明 | 翻譯是出于交流學(xué)習(xí)的目的，歡迎轉(zhuǎn)載，但請(qǐng)保留本文出處，請(qǐng)勿用于商業(yè)或非法用途。

David Beazley 在 US PyCon 2018 上的演講，關(guān)于語(yǔ)法分析生成器（parser generators），提醒了我應(yīng)該寫(xiě)一下關(guān)于它的歷史。這是一個(gè)簡(jiǎn)短的腦轉(zhuǎn)儲(chǔ)（也許我今后會(huì)解釋它）。

（譯注：我大膽揣測(cè)一下“腦轉(zhuǎn)儲(chǔ)”吧，應(yīng)該說(shuō)的是，把個(gè)人的記憶以及 Python 的歷史細(xì)節(jié)，轉(zhuǎn)化成文字，這是個(gè)存儲(chǔ)固化的過(guò)程，方便傳承。而我做的翻譯工作，就是把這份文檔財(cái)富，普及給更多的 Python 愛(ài)好者。）

實(shí)際上， 有兩個(gè) pgen，一個(gè)是最初的，用 C 語(yǔ)言寫(xiě)的，還有一個(gè)則是用 Python 重寫(xiě)的，在 lib2to3/pgen2 下面。

兩個(gè)都是我寫(xiě)的。最早那個(gè)實(shí)際上是我為 Python 編寫(xiě)的第一份代碼。盡管從技術(shù)上講，我必須首先編寫(xiě)詞法分析程序（lexer）（pgen 和 Python 共用詞法分析程序，但 pgen 對(duì)大多數(shù)標(biāo)記符不起作用）。

之所以我要寫(xiě)自己的語(yǔ)法分析生成器，原因是當(dāng)時(shí)這玩意（我熟悉的）相當(dāng)稀少——基本上就是用 Yacc（有個(gè) GNU 的重寫(xiě)版，叫作 Bison（譯注：美洲野牛），但我不確定那時(shí)的自己是否知道）；或者是自己手寫(xiě)一個(gè)（這是大多數(shù)人所做的）。

我曾在大學(xué)里用過(guò) Yacc，從“龍書(shū)”中熟悉了它的工作原理，但是出于某些原因，我并不喜歡它；IIRC 關(guān)于 LALR(1) 語(yǔ)法的局限性，我很難解釋清楚。

（譯注：1、龍書(shū)，原文是 Dragon book，指代《Compilers: Principles, Techniques, and Tools》，這是一本講編譯原理的書(shū)，屬于編譯原理界的殿堂級(jí)存在。另外還有兩本經(jīng)典著作，稱(chēng)號(hào)分別是“虎書(shū)”、“鯨書(shū)”，三者常常一起出現(xiàn)。2、IIRC，If I Remember Correctly，如果我沒(méi)記錯(cuò)。）

集齊三書(shū)，可以召喚神龍？

我也熟悉 LL(1) 解析器，并已認(rèn)真地編寫(xiě)過(guò)一些遞歸下降的 LL(1) 解析器——我很喜歡它，而且還熟悉 LL(1) 解析器的生成技術(shù)（同樣是因?yàn)辇垥?shū)），所以我有了一個(gè)改進(jìn)念頭想要試驗(yàn)下：使用正則表達(dá)式（某種程度的）而不是標(biāo)準(zhǔn)的 BNF 格式。

龍書(shū)還教會(huì)了我如何將正則表達(dá)式轉(zhuǎn)換成 DFA，所以我把所有這些東西一結(jié)合，pgen 就誕生了。【更新：請(qǐng)參閱下文，對(duì)于這個(gè)理由，有個(gè)略微不同的版本。】

我曾不熟悉更高級(jí)的技術(shù)，或者曾認(rèn)為它們效率太低。（在當(dāng)時(shí)，我覺(jué)得工作在解析器上的大多數(shù)人都是這樣。）

至于詞法分析器（lexer），我決定不使用生成器——我對(duì) Lex 的評(píng)價(jià)要比 Yacc 低得多，因?yàn)樵趪L試掃描超過(guò) 255 個(gè)字節(jié)的標(biāo)記符時(shí)，我所熟悉的 Lex 版本會(huì)發(fā)生段錯(cuò)誤（真實(shí)的！）。此外，我認(rèn)為縮進(jìn)格式很難教給詞法分析器生成器。

（譯注：1、這里的生成器并不是 Python 語(yǔ)法中的生成器，而是指用來(lái)生成分析器的工具。Lex 是“LEXical compiler”的簡(jiǎn)稱(chēng)，用來(lái)生成詞法分析器；Yacc 是“Yet another compiler compiler”的簡(jiǎn)稱(chēng)，用來(lái)生成語(yǔ)法分析器。2、段錯(cuò)誤，原文是 segfault，全稱(chēng)是 segmentation fault，指的是因?yàn)樵浇缭L(fǎng)問(wèn)內(nèi)存空間而導(dǎo)致的報(bào)錯(cuò)。）

pgen2 的故事則完全不同。

我曾受雇于 San Mateo 的一家創(chuàng)業(yè)公司（即 Elemental Security，倒閉于 2007，之后我離開(kāi)并加入了 Google），在那我有一項(xiàng)設(shè)計(jì)定制語(yǔ)言的任務(wù)（目標(biāo)是作關(guān)于系統(tǒng)配置的安全性判定），并擁有相當(dāng)大的自主權(quán)。

我決定設(shè)計(jì)一些稍微像 Python 的東西，用 Python 來(lái)實(shí)現(xiàn)，并且決定要重用 pgen，但是后端要基于 Python，使用 tokenize.py 作為詞法分析器。所以我用 Python 重寫(xiě)了 pgen 里的那些算法，然后繼續(xù)構(gòu)建了剩余的部分。

管理層覺(jué)得把工具開(kāi)源是有意義的，因此他們很快就批準(zhǔn)了，而在不久之后（我當(dāng)時(shí)很可能已經(jīng)轉(zhuǎn)移到 Google 了？），這工具對(duì)于 2to3 也是有意義的。（因?yàn)檩斎敫袷礁嫉?pgen 相同，用它來(lái)生成一個(gè) Python 解析器很容易——我只需將語(yǔ)法文件喂給工具。:-)

更新：創(chuàng)建 pgen 的原因，還有更多故事

我不完全記得為什么要這樣做了，但我剛剛偷看了https://en.wikipedia.org/wiki/LL_parser#Conflicts，我可能覺(jué)得這是一種新的（對(duì)我而言）不通過(guò)添加幫助性的規(guī)則而解決沖突的方式。

例如，該網(wǎng)頁(yè)所稱(chēng)的的左分解（將 A -> X | X Y Z 替換成 A -> X B; B -> Y Z | ），我會(huì)重寫(xiě)成 A -> X [Y Z]。

如果我沒(méi)記錯(cuò)，通過(guò)“正則表達(dá)式 -> NFA -> DFA”的轉(zhuǎn)換過(guò)程，解析引擎（該網(wǎng)頁(yè)中前面的 syntacticAnalysis 函數(shù)）依然可以工作在由這些規(guī)則所派生的解析表上；我認(rèn)為這里需要有不出現(xiàn)空白產(chǎn)物的訴求。（譯注：“空白產(chǎn)物”，原文是 empty productions，對(duì)應(yīng)的是前文的 ，指的是不必要出現(xiàn) empty。）

我還想起一點(diǎn)，由解析引擎生成的解析樹(shù)節(jié)點(diǎn)可能有很多子節(jié)點(diǎn)，例如，對(duì)于上面的規(guī)則 A -> X [Y Z]，節(jié)點(diǎn) A 可能有 1 個(gè)子節(jié)點(diǎn)（X）或者 3 個(gè)（X Y Z）。代碼生成器中就需要有一個(gè)簡(jiǎn)單的檢查，來(lái)確定它遇到的是哪一種可能的情況。（這已經(jīng)被證明是一把雙刃劍，后來(lái)我們添加了一個(gè)由單獨(dú)的生成器所驅(qū)動(dòng)的“解析樹(shù) -> AST”步驟，以簡(jiǎn)化字節(jié)碼生成器。）

所以我使用正則表達(dá)式的原因，很可能是為了使語(yǔ)法更易于閱讀：在使用了必要的重寫(xiě)以解決沖突之后，我發(fā)現(xiàn)語(yǔ)法不是那么可讀（此處應(yīng)插入《Python 之禪》的說(shuō)法 :-) ，而正則表達(dá)式則更符合我對(duì)于經(jīng)典語(yǔ)言的語(yǔ)法的看法（除了起著奇怪名字的幫助規(guī)則、[optional] 部分以及 * 號(hào)重復(fù)的部分）。

image

正則表達(dá)式?jīng)]有提高 LL(1) 的能力，更沒(méi)有降低它的能力。當(dāng)然了，所謂“正則表達(dá)式”，我想說(shuō)的其實(shí)是 EBNF ——我不確定 “EBNF” 在當(dāng)時(shí)是否是一個(gè)被明確定義了的符號(hào)，它可能就指對(duì) BNF 的任意擴(kuò)展。

假如將 EBNF 轉(zhuǎn)換為 BNF，再去使用它，將會(huì)導(dǎo)致尷尬的多解析樹(shù)節(jié)點(diǎn)問(wèn)題，所以我不認(rèn)為這會(huì)是一種改進(jìn)。

如果讓我重做一遍，我可能會(huì)選擇一個(gè)更強(qiáng)大的解析引擎，可能是 LALR(1) 的某個(gè)版本（例如 Yacc/Bison）。LALR(1) 的某些地方要比 LL(1) 更給力，也更加有用，例如，關(guān)鍵字參數(shù)。

在 LL(1) 中，規(guī)則 “arg: [NAME =] expr” 無(wú)效，因?yàn)?NAME 出現(xiàn)在了表達(dá)式的第一組里（FIRST-set），而 LL(1) 算法沒(méi)法處理這樣的寫(xiě)法。

如果我沒(méi)記錯(cuò)，LALR(1) 則可以處理它。但是，在我寫(xiě)完 pgen 的第一個(gè)版本的好些年之后，關(guān)鍵字參數(shù)寫(xiě)法才出現(xiàn)，那時(shí)候我已不想重做解析器了。

2019 年 3 月更新： Python 3.8 將刪除 pgen 的 C 版本，轉(zhuǎn)而使用重寫(xiě)的 pgen2 版本。請(qǐng)參閱 https://github.com/python/cpython/pull/11814

（譯注：感覺(jué)可以幫 Guido 再加一條“更新”了，目前他正在研究 PEG 解析器，將會(huì)作為 pgen 的替代。詳情請(qǐng)看《Python之父新發(fā)文，將替換現(xiàn)有解析器》）

image

公眾號(hào)【 Python貓 】， 本號(hào)連載優(yōu)質(zhì)的系列文章，有喵星哲學(xué)貓系列、Python進(jìn)階系列、好書(shū)推薦系列、技術(shù)寫(xiě)作、優(yōu)質(zhì)英文推薦與翻譯等等，歡迎關(guān)注哦。