摘要：近日，他開通了賬號，并發(fā)表了第一篇文章，透露出要替換的核心部件解析器的想法。這篇文章分析了當(dāng)前的解析器的諸多缺陷，并介紹了解析器的優(yōu)點，令人振奮。但問題是，如果你這樣寫語法，解析器不會起作用，將會罷工。

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

本文原創(chuàng)并首發(fā)于公眾號【Python貓】，未經(jīng)授權(quán)，請勿轉(zhuǎn)載。

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

原題 | PEG Parsers

作者 | Guido van Rossum（Python之父）

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

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

聲明 | 翻譯是出于交流學(xué)習(xí)的目的，歡迎轉(zhuǎn)載，但請保留本文出處，請勿用于商業(yè)或非法用途。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

假設(shè)我們的程序是這樣的：

answer = 42

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

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

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

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

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

但是在 Python 這種更現(xiàn)實的語言中，你可能需要一個無限的前向緩沖，因為在 “=” 標(biāo)記符左側(cè)的東西可能極其復(fù)雜，例如：

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

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

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

statement: assignment_or_expr | if_statement
assignment_or_expr: expr ["=" expr]

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

在調(diào)用函數(shù)時，關(guān)鍵字參數(shù)也有類似的麻煩。我們想要寫成這樣（同樣，這是 Python 的調(diào)用語法的簡化版本）：

call: atom "(" arguments ")"
arguments: arg ("," arg)*
arg: posarg | kwarg
posarg: expr
kwarg: NAME "=" expr

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

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

arg: expr ["=" expr]

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

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

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

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

這使一切變得簡單，然而當(dāng)然也有成本：內(nèi)存。

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

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

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

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

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

為什么不直接從解析樹編譯呢？這其實正是它最早的工作方式，但是大約在 15 年前，我們發(fā)現(xiàn)編譯器因為解析樹的結(jié)構(gòu)而變得復(fù)雜了，所以我們引入了一個多帶帶的 AST，還引入了一個將解析樹翻譯成 AST 的環(huán)節(jié)。隨著 Python 的發(fā)展，AST 比解析樹更穩(wěn)定，這減少了編譯器出錯的可能。

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

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

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

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

但是，我還沒去優(yōu)化它，所以還是挺有希望的。

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

過去有人曾說，pgen 的 LL(1) 缺陷幫助了 Python 保持語法的簡單。這很有道理，但我們還有很多適當(dāng)?shù)牧鞒蹋梢苑乐拐Z言不受控制地膨脹（主要是 PEP 流程，在非常嚴(yán)格的向后兼容性要求以及新的治理結(jié)構(gòu)的幫助下）。所以我并不擔(dān)心。

我還有很多內(nèi)容要寫，關(guān)于 PEG 解析以及我的具體實現(xiàn)，但是要等我整理好代碼后，在后續(xù)的文章中再去寫了。

公眾號【Python貓】， 本號連載優(yōu)質(zhì)的系列文章，有喵星哲學(xué)貓系列、Python進階系列、好書推薦系列、技術(shù)寫作、優(yōu)質(zhì)英文推薦與翻譯等等，歡迎關(guān)注哦。