image

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

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

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

原題 | PEG Parsers

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號(hào)作者）

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

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

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

最近，我學(xué)了很多關(guān)于 PEG（Parsing Expression Grammars）的知識(shí)，如今我認(rèn)為它是個(gè)有趣的替代品，正好替換掉我在 30 年前剛開(kāi)始創(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)鍵字開(kāi)頭）。

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

          
            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)于這些符號(hào)，解釋幾句： NAME 和 NUMBER 是標(biāo)記符（token），預(yù)定義在語(yǔ)法之外。引號(hào)中的字符串如 '+' 或 'if' 也是標(biāo)記符。（我以后會(huì)講講標(biāo)記符。）語(yǔ)法規(guī)則以其名稱開(kāi)頭，跟在后面的是 : 號(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ǔ)言，但它并沒(méi)有反映出語(yǔ)言設(shè)計(jì)者的本意——尤其是它并沒(méi)有表明運(yùn)算符是左綁定的，而這在你嘗試生成代碼時(shí)非常重要。

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

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

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

          
            answer = 42

          
        

這句程序會(huì)被解析成三個(gè)標(biāo)記符： NAME （值是 answer ），‘=’ 和 NUMBER （值為 42）。在程序開(kāi)始時(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)記符開(kāi)頭，因此就會(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_statement
assignment_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 | kwarg
posarg: expr
kwarg: NAME '=' expr

          
        

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

同樣地，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)造解析樹(shù)。

幸運(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è)解析樹(shù)，但是這個(gè)解析樹(shù)并不直接用作代碼生成器的輸入：它首先會(huì)被轉(zhuǎn)換成抽象語(yǔ)法樹(shù)（AST），然后再被編譯成字節(jié)碼。（還有更多細(xì)節(jié)，但在這我不關(guān)注。）

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

AST 對(duì)于那些想要檢查（inspect）Python 代碼的第三方代碼，也更加容易，它還通過(guò)被大眾歡迎的 ast 模塊而公開(kāi)。這個(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 模塊，解析樹(shù)同樣能面向 Python 的用戶開(kāi)放，但它使用起來(lái)太麻煩了，因此相比于 ast 模塊，它就過(guò)時(shí)了。）

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

我還沒(méi)進(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 解析器的速度。

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

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

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

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

image

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