原題 | The of pgen
作者 | Guido van （之父）
譯者 | 豌豆花下貓
原文 |
David 在 US PyCon 2018 上的演講，關于語法分析生成器（ ），提醒了我應該寫一下關于它的歷史。這是一個簡短的腦轉儲（也許我今后會解釋它）。
（譯注：我大膽揣測一下“腦轉儲”吧，應該說的是，把個人的記憶以及 的歷史細節，轉化成文字，這是個存儲固化的過程，方便傳承。而我做的翻譯工作，就是把這份文檔財富，普及給更多的 愛好者。）
實際上，有兩個 pgen，一個是最初的，用 C 語言寫的，還有一個則是用 重寫的，在 /pgen2 下面。
兩個都是我寫的。最早那個實際上是我為 編寫的第一份代碼。盡管從技術上講，我必須首先編寫詞法分析程序（lexer）（pgen 和 共用詞法分析程序，但 pgen 對大多數標記符不起作用）。
之所以我要寫自己的語法分析生成器，原因是當時這玩意（我熟悉的）相當稀少——基本上就是用 Yacc（有個 GNU 的重寫版，叫作 Bison（譯注：美洲野牛），但我不確定那時的自己是否知道）；或者是自己手寫一個（這是大多數人所做的）。
我曾在大學里用過 Yacc，從“龍書”中熟悉了它的工作原理，但是出于某些原因，我并不喜歡它；IIRC 關于 LALR(1) 語法的局限性，我很難解釋清楚。
（譯注：1、龍書，原文是 book，指代《: , , and Tools》，這是一本講編譯原理的書，屬于編譯原理界的殿堂級存在。另外還有兩本經典著作，稱號分別是“虎書”、“鯨書”，三者常常一起出現。2、IIRC，If I ，如果我沒記錯。）
集齊三書，可以召喚神龍？
我也熟悉 LL(1) 解析器，并已認真地編寫過一些遞歸下降的 LL(1) 解析器——我很喜歡它，而且還熟悉 LL(1) 解析器的生成技術（同樣是因為龍書），所以我有了一個改進念頭想要試驗下：使用正則表達式（某種程度的）而不是標準的 BNF 格式。
龍書還教會了我如何將正則表達式轉換成 DFA，所以我把所有這些東西一結合，pgen 就誕生了。【更新：請參閱下文，對于這個理由，有個略微不同的版本?！?/p>
我曾不熟悉更高級的技術，或者曾認為它們效率太低。（在當時，我覺得工作在解析器上的大多數人都是這樣。）
至于詞法分析器（lexer），我決定不使用生成器——我對 Lex 的評價要比 Yacc 低得多詞法分析器輸入的是，因為在嘗試掃描超過 255 個字節的標記符時，我所熟悉的 Lex 版本會發生段錯誤（真實的?。?。此外，我認為縮進格式很難教給詞法分析器生成器。
（譯注：1、這里的生成器并非 語法中的生成器，而是指用來生成分析器的工具。Lex 是“ ”的簡稱，用來生成詞法分析器；Yacc 是“Yet ”的簡稱，用來生成語法分析器。2、段錯誤，原文是 ，全稱是 fault，指的是因為越界訪問內存空間而導致的報錯。）
pgen2 的故事則完全不同。
我曾受雇于 San Mateo 的一家創業公司（即 ，倒閉于 2007，之后我離開并加入了 ），在那我有一項設計定制語言的任務（目標是作關于系統配置的安全性判定），并擁有相當大的自主權。
我決定設計一些稍微像 的東西，用 來實現，并且決定要重用 pgen，但是后端要基于 ，使用 .py 作為詞法分析器。所以我用 重寫了 pgen 里的那些算法，然后繼續構建了剩余的部分。
管理層覺得把工具開源是有意義的，因此他們很快就批準了，而在不久之后（我當時很可能已經轉移到 了？），這工具對于 2to3 也是有意義的。（因為輸入格式跟原始的 pgen 相同，用它來生成一個 解析器很容易——我只需將語法文件喂給工具。:-)
更新：創建 pgen 的原因，還有更多故事
我不完全記得為什么要這樣做了，但我剛偷看了#，我可能覺得這是一種新的（對我而言）不通過添加幫助性的規則而解決沖突的方式。
例如，該網頁所稱的的左分解（將 A -> X | X Y Z 替換成 A -> X B; B -> Y Z | ），我會重寫成 A -> X [Y Z]。
如果我沒記錯，通過“正則表達式 -> NFA -> DFA”的轉換過程，解析引擎（該網頁中前面的 函數）依然可以工作在由這些規則所派生的解析表上；我認為這里需要有不出現空白產物的訴求。（譯注：“空白產物”，原文是 empty ，對應的是前文的 ，指的是不必要出現 empty。）
我還想起一點，由解析引擎生成的解析樹節點可能有很多子節點，例如，對于上面的規則 A -> X [Y Z]，節點 A 可能有 1 個子節點（X）或者 3 個（X Y Z）。代碼生成器中就需要有一個簡單的檢查，來確定它遇到的是哪一種可能的情況。（這已經被證明是一把雙刃劍，后來我們添加了一個由單獨的生成器所驅動的“解析樹 -> AST”步驟，以簡化字節碼生成器。）
所以我使用正則表達式的原因，很可能是為了使語法更易于閱讀：在使用了必要的重寫以解決沖突之后，我發現語法不是那么可讀（此處應插入《 之禪》的說法 :-) ，而正則表達式則更符合我對于經典語言的語法的看法（除了起著奇怪名字的幫助規則、[] 部分以及 * 號重復的部分）。
正則表達式沒有提高 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 月更新： 3.8 將刪除 pgen 的 C 版本詞法分析器輸入的是，轉而使用重寫的 pgen2 版本。參閱
（譯注：感覺可以幫 Guido 再加一條“更新”了，目前他正在研究 PEG 解析器，將會作為 pgen 的替代。）
▼ 點擊成為社區注冊會員 「在看」一下，一起PY！
