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

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

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

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

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

---

原題 | The origins of pgen

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號作者）

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

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

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

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

實際上， 有兩個 pgen，一個是最初的，用 C 語言寫的，還有一個則是用 Python 重寫的，在 lib2to3/pgen2 下面。

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

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

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

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

我也熟悉 LL(1) 解析器，并已認真地編寫過一些遞歸下降的 LL(1) 解析器——我很喜歡它，而且還熟悉 LL(1) 解析器的生成技術(shù)（同樣是因為龍書），所以我有了一個改進念頭想要試驗下：使用正則表達式（某種程度的）而不是標準的 BNF 格式。

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

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

至于詞法分析器（lexer），我決定不使用生成器——我對 Lex 的評價要比 Yacc 低得多，因為在嘗試掃描超過 255 個字節(jié)的標記符時，我所熟悉的 Lex 版本會發(fā)生段錯誤（真實的！）。此外，我認為縮進格式很難教給詞法分析器生成器。

（譯注：1、這里的生成器并不是 Python 語法中的生成器，而是指用來生成分析器的工具。Lex 是“LEXical compiler”的簡稱，用來生成詞法分析器；Yacc 是“Yet another compiler compiler”的簡稱，用來生成語法分析器。2、段錯誤，原文是 segfault，全稱是 segmentation fault，指的是因為越界訪問內(nèi)存空間而導(dǎo)致的報錯。）

pgen2 的故事則完全不同。

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

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

管理層覺得把工具開源是有意義的，因此他們很快就批準了，而在不久之后（我當時很可能已經(jīng)轉(zhuǎn)移到 Google 了？），這工具對于 2to3 也是有意義的。（因為輸入格式跟原始的 pgen 相同，用它來生成一個 Python 解析器很容易——我只需將語法文件喂給工具。:-)

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

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

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

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

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

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

正則表達式?jīng)]有提高 LL(1) 的能力，更沒有降低它的能力。當然了，所謂“正則表達式”，我想說的其實是 EBNF ——我不確定 “EBNF” 在當時是否是一個被明確定義了的符號，它可能就指對 BNF 的任意擴展。

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

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

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

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

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

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

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