image

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

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

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

本文原創并首發于公眾號【 Python貓 】，未經授權，請勿轉載。

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

原題 | 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 | ），我會重寫成 A -> X [Y Z]。

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

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

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

image

正則表達式沒有提高 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之父新發文，將替換現有解析器》）

image

公眾號【 Python貓 】， 本號連載優質的系列文章，有喵星哲學貓系列、Python進階系列、好書推薦系列、技術寫作、優質英文推薦與翻譯等等，歡迎關注哦。