chinese直男口爆体育生外卖, 99久久er热在这里只有精品99, 又色又爽又黄18禁美女裸身无遮挡, gogogo高清免费观看日本电视,私密按摩师高清版在线,人妻视频毛茸茸,91论坛 兴趣闲谈,欧美 亚洲 精品 8区,国产精品久久久久精品免费

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

pgen解析器的諸多缺陷,并介紹了PEG解析器的優(yōu)點

WpOh_rgznai100 ? 來源:lq ? 2019-08-02 09:19 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

導(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ù)的文章中再去寫了。

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 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)載請注明出處。

收藏 人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評論

    相關(guān)推薦
    熱點推薦

    名單公布!【書籍評測活動NO.60】運算放大器參數(shù)解析與LTspice應(yīng)用仿真

    和電路分析方法。 第2章:參考實際放大器的數(shù)據(jù)手冊,使用超大篇幅解析全部參數(shù)的意義、注意事項,配合精典案例和仿真電路,幫助讀者全面理解參數(shù)的意義與運用。 第3章:介紹儀表放大器、跨
    發(fā)表于 04-21 16:18

    CAN報文流程解析

    CAN報文流程解析,直流充電樁上的CAN通訊解析過程
    發(fā)表于 03-24 14:03 ?1次下載

    國外物理服務(wù)詳細(xì)解析

    國外物理服務(wù)是指位于國外數(shù)據(jù)中心的物理設(shè)備,用于提供互聯(lián)網(wǎng)服務(wù)。以下是對國外物理服務(wù)的詳細(xì)解析,主機推薦小編為您整理發(fā)布國外物理服務(wù)詳細(xì)解析
    的頭像 發(fā)表于 02-07 09:36 ?405次閱讀

    【教程】DNS域名解析服務(wù)systemd-resolved使用指南

    客戶端?DNS服務(wù)?域名對應(yīng)的IP地址DNS解析大致過程:?用戶在應(yīng)用程序中使用域名?應(yīng)用程序調(diào)用DNS客戶端申請域名解析?DNS客戶端向DNS服務(wù)發(fā)送待
    的頭像 發(fā)表于 01-09 19:34 ?1019次閱讀
    【教程】DNS域名<b class='flag-5'>解析</b>服務(wù)systemd-resolved使用指南

    淺談SQL優(yōu)化小技巧

    存儲在緩存中的數(shù)據(jù); (3)未命中緩存后,MySQL通過關(guān)鍵字將SQL語句進(jìn)行解析,生成一顆對應(yīng)的解析樹,MySQL解析器將使用MySQL語法進(jìn)行驗證和
    的頭像 發(fā)表于 12-25 09:59 ?857次閱讀

    自動化創(chuàng)建UI解析數(shù)據(jù)

    *附件:32960_auto.rar備注:Main.vi是ui自動化2.1.vi,配置文件為32960.B.ini。 目前可以實現(xiàn)根據(jù)配置文件自動化創(chuàng)建控件布局,且可以自動解析接收到的數(shù)據(jù)內(nèi)容寫入
    發(fā)表于 12-10 08:41

    編碼邏輯功能解析與實現(xiàn)

    在現(xiàn)代電子技術(shù)與自動化控制系統(tǒng)中,編碼作為一種關(guān)鍵性傳感,扮演著舉足輕重的角色。它通過將機械位移或旋轉(zhuǎn)轉(zhuǎn)換成數(shù)字信號,為各種設(shè)備提供精確的位置、速度和方向信息。本文將深入探討編碼
    的頭像 發(fā)表于 11-30 14:35 ?1149次閱讀

    自動化創(chuàng)建UI解析數(shù)據(jù)

    布局,且可以自動解析接收到的數(shù)據(jù)內(nèi)容寫入到創(chuàng)建的控件。 待優(yōu)化點: 1.協(xié)議內(nèi)容較多時候配置文件編寫較為繁瑣; 2.創(chuàng)建UI時會存在失敗的情況,導(dǎo)致“輸入框.vi”無法關(guān)閉; 3.控件創(chuàng)建可能會漏缺
    發(fā)表于 11-29 11:26

    raksmart洛杉磯云服務(wù)全面解析

    RAKsmart洛杉磯云服務(wù)是一種高性能的云計算解決方案,專為滿足不同業(yè)務(wù)需求而設(shè)計。以下是對RAKsmart洛杉磯云服務(wù)的具體介紹,rak小編為您整理發(fā)布raksmart洛杉磯云服務(wù)
    的頭像 發(fā)表于 09-14 09:36 ?534次閱讀

    自動售貨機MDB協(xié)議中文解析(七)MDB-RS232控制紙幣的詳細(xì)流程和解析

    自動售貨機MDB協(xié)議中文解析(七)MDB-RS232控制紙幣的詳細(xì)流程和解析
    的頭像 發(fā)表于 09-09 10:04 ?1385次閱讀

    自動售貨機MDB協(xié)議中文解析(六)MDB-RS232控制硬幣的流程和解析

    自動售貨機MDB協(xié)議中文解析(六)MDB-RS232控制硬幣的流程和解析
    的頭像 發(fā)表于 08-19 15:53 ?1266次閱讀
    自動售貨機MDB協(xié)議中文<b class='flag-5'>解析</b>(六)MDB-RS232控制硬幣<b class='flag-5'>器</b>的流程和<b class='flag-5'>解析</b>

    深入解析 MEMS 可編程 LVPECL/LVDS 振蕩 SiT9120 系列

    深入解析 MEMS 可編程 LVPECL/LVDS 振蕩 SiT9120 系列
    的頭像 發(fā)表于 08-13 16:23 ?809次閱讀
    深入<b class='flag-5'>解析</b> MEMS 可編程 LVPECL/LVDS 振蕩<b class='flag-5'>器</b> SiT9120 系列

    解析石英 CMOS 振蕩 PA7050 系列(1 to 200 MHz)的卓越性能

    解析石英 CMOS 振蕩 PA7050 系列(1 to 200 MHz)的卓越性能
    的頭像 發(fā)表于 08-08 13:45 ?686次閱讀
    <b class='flag-5'>解析</b>石英 CMOS 振蕩<b class='flag-5'>器</b> PA7050 系列(1 to 200 MHz)的卓越性能

    解析 MEMS 車載與高溫振蕩 SiT8920 系列 1 to 110 MHz 的卓越特性

    解析 MEMS 車載與高溫振蕩 SiT8920 系列(1 to 110 MHz)的卓越特性
    的頭像 發(fā)表于 07-22 09:52 ?685次閱讀

    DNS客戶端無法支持多個名稱服務(wù)怎么處理?

    在我的環(huán)境中,DHCPD 提供兩個解析器(192.159.10.2、8.8.8.8)。第一個是封閉的解析器,它為 Internet 提供權(quán)威的名稱服務(wù)視圖,為本地客戶端提供
    發(fā)表于 07-18 07:44