Python 之父新發文,將替換現有解析器

語言: CN / TW / HK

幾年前,有人問 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 流程,在非常嚴格的向後相容性要求以及新的治理結構的幫助下)。所以我並不擔心。

以上就是本次分享的所有內容,想要了解更多 python 知識歡迎前往公眾號:Python 程式設計學習圈 ,傳送 “J” 即可免費獲取,每日干貨分享