導語：Guido van Rossum 是 Python 的創造者，雖然他現在放棄了“終身仁慈獨裁者”的職位，但卻成為了指導委員會的五位成員之一，其一舉一動依然備受矚目。近日，他開通了 Medium 賬號，并發表了第一篇文章，透露出要替換 Python 的核心部件（解析器）的想法。這篇文章分析了當前的 pgen 解析器的諸多缺陷，并介紹了 PEG 解析器的優點，令人振奮。這項改造工作仍在進行中，Guido 說他還會寫更多相關的文章。

幾年前，有人問 Python 是否會轉換用 PEG 解析器（或者是 PEG 語法，我不記得確切內容、誰說的、什么時候說的）。我稍微看過這個主題，但沒有頭緒，就放棄了。

最近，我學了很多關于 PEG（Parsing Expression Grammars）的知識，如今我認為它是個有趣的替代品，正好替換掉我在 30 年前剛開始創造 Python 時自制的（home-grown）語法分析生成器（parser generator）（那個語法分析生成器，被稱為“pgen”，是我為 Python 寫下的第一段代碼）。

我現在感興趣于 PEG，原因是對 pgen 的局限性感到有些惱火了。

它使用了我自己寫的 LL(1) 解析的變種——我不喜歡可以產生空字符串的語法規則，所以我禁用了它，進而稍微地簡化了生成解析表的算法。

同時，我還發明了一套類似 EBNF 的語法符號（譯注：Extended Backus-Naur Form，BNF 的擴展，是一種形式化符號，用于描述給定語言中的語法），至今仍非常喜歡。

以下是 pgen 令我感到煩惱的一些問題。

LL(1) 名字中的 “1” 表明它只使用單一的前向標記符（a single token lookahead），而這限制了我們編寫漂亮的語法規則的能力。例如，一個 Python 語句（statement）既可以是表達式（expression），又可以是賦值（assignment）（或者是其它東西，但那些都以 if 或 def 這類專用的關鍵字開頭）。

我們希望使用 pgen 表示法來編寫如下的語法。（請注意，這個示例描述了一種玩具語言（toy language），它是 Python 的一個微小的子集，就像傳統中的語言設計一樣。）

statement:assignment|expr|if_statementexpr:expr'+'term|expr'-'term|termterm:term'*'atom|term'/'atom|atomatom:NAME|NUMBER|'('expr')'assignment:target'='exprtarget:NAMEif_statement:'if'expr':'statement

關于這些符號，解釋幾句：NAME和NUMBER是標記符（token），預定義在語法之外。引號中的字符串如 '+' 或 'if' 也是標記符。（我以后會講講標記符。）語法規則以其名稱開頭，跟在后面的是:號，再后面則是一個或多個以|符號分隔的可選內容（alternatives）。

但問題是，如果你這樣寫語法，解析器不會起作用，pgen 將會罷工。

其中一個原因是某些規則（如expr和term）是左遞歸的，而 pgen 還不足以聰明地解析。這通常需要通過重寫規則來解決，例如（在保持其它規則不變的情況下）：

expr:term('+'term|'-'term)*term:atom('*'atom|'/'atom)*

這就揭示了 pgen 的一部分 EBNF 能力：你可以在括號內嵌套可選內容，并且可以在括號后放*來創建重復，所以這里的expr規則就意味著：它是一個術語（term），跟著零個或多個語句塊，語句塊內是加號跟術語，或者是減號跟術語。

這個語法兼容了第一個版本的語言，但它并沒有反映出語言設計者的本意——尤其是它并沒有表明運算符是左綁定的，而這在你嘗試生成代碼時非常重要。

但是在這種玩具語言（以及在 Python）中，還有另一個煩人的問題。

由于前向的單一標記符，解析器無法確定它查看的是一個表達式的開頭，還是一個賦值。在一個語句的開頭，解析器需要根據它看到的第一個標記符，來決定它要查看的statement的可選內容。（為什么呢？pgen 的自動解析器就是這樣工作的。）

假設我們的程序是這樣的：

answer=42

這句程序會被解析成三個標記符：NAME（值是answer），‘=’ 和NUMBER（值為 42）。在程序開始時，我們擁有的唯一的前向標記符是NAME。此時，我們試圖滿足的規則是statement（這個語法的起始標志）。此規則有三個可選內容：expr、assignment以及if_statement。我們可以排除if_statement，因為前向標記符不是 “if”。

但是expr與assignment都能以NAME標記符開頭，因此就會引起歧義（ambiguous），pgen 會拒絕我們的語法。

（這也不完全正確，因為語法在技術上并不會導致歧義；但我們先不管它，因為我想不到更好的詞來表達。那么 pgen 是如何做決定的呢？它會為每條語法規則計算出一個叫做FIRST組的東西，如果在給定的點上，FIRST 組出現了重疊選項，它就會抱怨）（譯注：抱怨？應該指的是解析不下去，前文譯作了罷工）。

那么，我們能否為解析器提供一個更大的前向緩沖區，來解決這個煩惱呢？

對于我們的玩具語言，第二個前向標記符就足夠了，因為在這個語法中，assignment 的第二個標記符必須是 “=”。

但是在 Python 這種更現實的語言中，你可能需要一個無限的前向緩沖，因為在 “=” 標記符左側的東西可能極其復雜，例如：

table[index+1].name.first='Steven'

在 “=” 標記符之前，它已經用了 10 個標記符，如果想挑戰的話，我還可以舉出任意長的例子。為了在 pgen 中解決它，我們的方法是修改語法，并增加一個額外的檢查，令它能接收一些非法的程序，但如果檢查到對左側的賦值是無效的，則會拋出一個SyntaxError。

對于我們的玩具語言，這可歸結成如下寫法：

statement:assignment_or_expr|if_statementassignment_or_expr:expr['='expr]

（方括號表示了一個可選部分。）然后在隨后的編譯過程中（比如，在生成字節碼時），我們會檢查是否存在 “=”，如果存在，我們再檢查左側是否有target語法。

在調用函數時，關鍵字參數也有類似的麻煩。我們想要寫成這樣（同樣，這是 Python 的調用語法的簡化版本）：

call:atom'('arguments')'arguments:arg(','arg)*arg:posarg|kwargposarg:exprkwarg:NAME'='expr

但是前向的單一標記符無法告訴解析器，一個參數的開頭中的NAME到底是posarg的開頭（因為expr可能以NAME開頭）還是kwarg的開頭。

同樣地，Python 當前的解析器在解決這個問題時，是通過特別聲明：

arg:expr['='expr]

然后在后續的編譯過程中再解決問題。（我們甚至出了點小錯，允許了像foo((a)=1)這樣的東西，給了它跟foo(a=1)相同的含義，直到 Python 3.8 時才修復掉。）

那么，PEG 解析器是如何解決這些煩惱的呢？

通過使用無限的前向緩沖！PEG 解析器的經典實現中使用了一個叫作“packrat parsing”（譯注：PackRat，口袋老鼠）的東西，它不僅會在解析之前將整個程序加載到內存中，而且還能允許解析器任意地回溯。

雖然 PEG 這個術語主要指的是語法符號，但是以 PEG 語法生成的解析器是可以無限回溯的遞歸下降（recursive-descent）解析器，“packrat parsing”通過記憶每個位置所匹配的規則，來使之生效。

這使一切變得簡單，然而當然也有成本：內存。

三十年前，我有充分的理由來使用單一前向標記符的解析技術：內存很昂貴。LL(1) 解析（以及其它技術像 LALR(1)，因 YACC 而著名）使用狀態機和堆棧（一種“下推自動機”）來有效地構造解析樹。

幸運的是，運行 CPython 的計算機比 30 年前有了更多的內存，將整個文件存在內存中確實已不再是一個負擔。例如，我能在標準庫中找到的最大的非測試文件是_pydecimal.py，它大約有 223 千字節（譯注：kilobytes，即 KB）。在一個 GB 級的世界里，這基本不算什么。

這就是令我再次研究解析技術的原因。

但是，當前 CPython 中的解析器還有另一個 bug 我的東西。

編譯器都是復雜的，CPython 也不例外：雖然 pgen-驅動的解析器輸出的是一個解析樹，但是這個解析樹并不直接用作代碼生成器的輸入：它首先會被轉換成抽象語法樹（AST），然后再被編譯成字節碼。（還有更多細節，但在這我不關注。）

為什么不直接從解析樹編譯呢？這其實正是它最早的工作方式，但是大約在 15 年前，我們發現編譯器因為解析樹的結構而變得復雜了，所以我們引入了一個單獨的 AST，還引入了一個將解析樹翻譯成 AST 的環節。隨著 Python 的發展，AST 比解析樹更穩定，這減少了編譯器出錯的可能。

AST 對于那些想要檢查（inspect）Python 代碼的第三方代碼，也更加容易，它還通過被大眾歡迎的ast模塊而公開。這個模塊還允許你從頭構建 AST 節點，或是修改現有的 AST 節點，然后你可以將新的節點編譯成字節碼。

后一項能力支撐起了一整個為 Python 語言添加擴展的家庭手工業（譯注：ast 模塊為 Python 的三方擴展提供了便利）。（借助parser模塊，解析樹同樣能面向 Python 的用戶開放，但它使用起來太麻煩了，因此相比于ast模塊，它就過時了。）

綜上所述，我現在的想法是看看能否為 CPython 創造一個新的解析器，在解析時，使用 PEG 與 packrat parsing 來直接構建 AST，從而跳過中間解析樹結構，并盡可能地節省內存，盡管它會使用無限的前向緩沖。

我還沒進展到這個地步，但已經有了一個原型，可以將一個 Python 的子集編譯成一個 AST，其速度與當前 CPython 的解析器大致相當。只不過，它占用的內存更多，所以我預計在將它擴展到整個語言時，將會降低 PEG 解析器的速度。

但是，我還沒去優化它，所以還是挺有希望的。

轉換成 PEG 的最后一個好處是它為語言的未來演化提供了更大的靈活性。

過去有人曾說，pgen 的 LL(1) 缺陷幫助了 Python 保持語法的簡單。這很有道理，但我們還有很多適當的流程，可以防止語言不受控制地膨脹（主要是 PEP 流程，在非常嚴格的向后兼容性要求以及新的治理結構的幫助下）。所以我并不擔心。

我還有很多內容要寫，關于 PEG 解析以及我的具體實現，但是要等我整理好代碼后，在后續的文章中再去寫了。