image

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

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

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

原題 | PEG Parsers

作者 | Guido van Rossum（Python之父）

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

原文 | https://medium.com/@gvanrossum_83706/peg-parsers-7ed72462f97c

聲明 | 翻譯是出于交流學習的目的，歡迎轉載，但請保留本文出處，請勿用于商業或非法用途。

幾年前，有人問 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_statement
expr: expr '+' term | expr '-' term | term
term: term '*' atom | term '/' atom | atom
atom: NAME | NUMBER | '(' expr ')'
assignment: target '=' expr
target: NAME
if_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_statement
assignment_or_expr: expr ['=' expr]

          
        

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

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

          
            call: atom '(' arguments ')'
arguments: arg (',' arg)*
arg: posarg | kwarg
posarg: expr
kwarg: 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 解析以及我的具體實現，但是要等我整理好代碼后，在后續的文章中再去寫了。

image

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