導(dǎo)語:Guido van Rossum 是 Python 的創(chuàng)造者,雖然他現(xiàn)在放棄了“終身仁慈獨裁者”的職位,但卻成為了指導(dǎo)委員會的五位成員之一,其一舉一動依然備受矚目。近日,他開通了 Medium 賬號,并發(fā)表了第一篇文章,透露出要替換 Python 的核心部件(解析器)的想法。這篇文章分析了當(dāng)前的 pgen 解析器的諸多缺陷,并介紹了 PEG 解析器的優(yōu)點,令人振奮。這項改造工作仍在進(jìn)行中,Guido 說他還會寫更多相關(guān)的文章。
幾年前,有人問 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ī)則,所以我禁用了它,進(jìn)而稍微地簡化了生成解析表的算法。
同時,我還發(fā)明了一套類似 EBNF 的語法符號(譯注:Extended Backus-Naur Form,BNF 的擴展,是一種形式化符號,用于描述給定語言中的語法),至今仍非常喜歡。
以下是 pgen 令我感到煩惱的一些問題。
LL(1) 名字中的 “1” 表明它只使用單一的前向標(biāo)記符(a single token lookahead),而這限制了我們編寫漂亮的語法規(guī)則的能力。例如,一個 Python 語句(statement)既可以是表達(dá)式(expression),又可以是賦值(assignment)(或者是其它東西,但那些都以 if 或 def 這類專用的關(guān)鍵字開頭)。
我們希望使用 pgen 表示法來編寫如下的語法。(請注意,這個示例描述了一種玩具語言(toy language),它是 Python 的一個微小的子集,就像傳統(tǒng)中的語言設(shè)計一樣。)
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)于這些符號,解釋幾句: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)記符,解析器無法確定它查看的是一個表達(dá)式的開頭,還是一個賦值。在一個語句的開頭,解析器需要根據(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)致歧義;但我們先不管它,因為我想不到更好的詞來表達(dá)。那么 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_statementassignment_or_expr:expr['='expr]
(方括號表示了一個可選部分。)然后在隨后的編譯過程中(比如,在生成字節(jié)碼時),我們會檢查是否存在 “=”,如果存在,我們再檢查左側(cè)是否有target語法。
在調(diào)用函數(shù)時,關(guān)鍵字參數(shù)也有類似的麻煩。我們想要寫成這樣(同樣,這是 Python 的調(diào)用語法的簡化版本):
call:atom'('arguments')'arguments:arg(','arg)*arg:posarg|kwargposarg:exprkwarg: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ìn)展到這個地步,但已經(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ù)牧鞒?,可以防止語言不受控制地膨脹(主要是 PEP 流程,在非常嚴(yán)格的向后兼容性要求以及新的治理結(jié)構(gòu)的幫助下)。所以我并不擔(dān)心。
我還有很多內(nèi)容要寫,關(guān)于 PEG 解析以及我的具體實現(xiàn),但是要等我整理好代碼后,在后續(xù)的文章中再去寫了。
-
python
+關(guān)注
關(guān)注
56文章
4827瀏覽量
86719 -
語法
+關(guān)注
關(guān)注
0文章
44瀏覽量
10167
原文標(biāo)題:Python之父發(fā)文,將重構(gòu)現(xiàn)有核心解析器
文章出處:【微信號:rgznai100,微信公眾號:rgznai100】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
名單公布!【書籍評測活動NO.60】運算放大器參數(shù)解析與LTspice應(yīng)用仿真
國外物理服務(wù)器詳細(xì)解析
【教程】DNS域名解析服務(wù)systemd-resolved使用指南

評論