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

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

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

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

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

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

以下是 pgen 令我感到煩惱的一些問(wèn)題。

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

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

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

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

但問(wèn)題是，如果你這樣寫語(yǔ)法，解析器不會(huì)起作用，pgen 將會(huì)罷工。

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

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

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

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

但是在這種玩具語(yǔ)言（以及在 Python）中，還有另一個(gè)煩人的問(wèn)題。

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

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

answer=42

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

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

（這也不完全正確，因?yàn)檎Z(yǔ)法在技術(shù)上并不會(huì)導(dǎo)致歧義；但我們先不管它，因?yàn)槲蚁氩坏礁玫脑~來(lái)表達(dá)。那么 pgen 是如何做決定的呢？它會(huì)為每條語(yǔ)法規(guī)則計(jì)算出一個(gè)叫做FIRST組的東西，如果在給定的點(diǎn)上，F(xiàn)IRST 組出現(xiàn)了重疊選項(xiàng)，它就會(huì)抱怨）（譯注：抱怨？應(yīng)該指的是解析不下去，前文譯作了罷工）。

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

對(duì)于我們的玩具語(yǔ)言，第二個(gè)前向標(biāo)記符就足夠了，因?yàn)樵谶@個(gè)語(yǔ)法中，assignment 的第二個(gè)標(biāo)記符必須是 “=”。

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

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

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

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

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

（方括號(hào)表示了一個(gè)可選部分。）然后在隨后的編譯過(guò)程中（比如，在生成字節(jié)碼時(shí)），我們會(huì)檢查是否存在 “=”，如果存在，我們?cè)贆z查左側(cè)是否有target語(yǔ)法。

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

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

但是前向的單一標(biāo)記符無(wú)法告訴解析器，一個(gè)參數(shù)的開頭中的NAME到底是posarg的開頭（因?yàn)閑xpr可能以NAME開頭）還是kwarg的開頭。

同樣地，Python 當(dāng)前的解析器在解決這個(gè)問(wèn)題時(shí)，是通過(guò)特別聲明：

arg:expr['='expr]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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