亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python 之父再發(fā)文:構(gòu)建一個 PEG 解析器

系統(tǒng) 2128 0

Python 之父再發(fā)文:構(gòu)建一個 PEG 解析器_第1張圖片

花下貓語: Python 之父在 Medium 上開了博客,現(xiàn)在寫了兩篇文章,本文是第二篇的譯文。前一篇的譯文 在此 ,宣布了將要用 PEG 解析器來替換當(dāng)前的 pgen 解析器。

本文主要介紹了構(gòu)建一個 PEG 解析器的大體思路,并介紹了一些基本的語法規(guī)則。根據(jù) Python 之父的描述,這個 PEG 解析器還是一個很籠統(tǒng)的實驗品,而他也預(yù)告了,將會在以后的系列文章中豐富這個解析器。

閱讀這篇文章就像在讀一篇教程,雖然很難看懂,但是感覺很奇妙:我們竟然可以見證 Python 之父如何考慮問題、如何作設(shè)計、如何一點(diǎn)一點(diǎn)地豐富功能、并且傳授出來。這種機(jī)會非常難得啊!

我會持續(xù)跟進(jìn)后續(xù)文章的翻譯,由于能力有限,可能翻譯中有不到位之處,懇請讀者們批評指正。

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

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


原題 | Building a PEG Parser

作者 | Guido van Rossum(Python之父)

譯者 | 豌豆花下貓(“Python貓”公眾號作者)

原文 | https://medium.com/@gvanrossum_83706/building-a-peg-parser-d4869b5958fb

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

僅僅理解了 PEG 解析器的小部分,我就受到了啟發(fā),決定自己構(gòu)建一個。結(jié)果可能不是一個很棒的通用型的 PEG 解析器生成器——這類生成器已經(jīng)有很多了(例如 TatSu,寫于 Python,生成 Python 代碼)——但這是一個學(xué)習(xí) PEG 的好辦法,推進(jìn)了我的目標(biāo),即用由 PEG 語法構(gòu)建的解析器替換 CPython 的解析器。

在本文中, 通過展示一個簡單的手寫解析器,我為如何理解解析器的工作原理奠定了基礎(chǔ)。

(順便說一句,作為一個實驗,我不會在文中到處放參考鏈接。如果你有什么不明白的東西,請 Google 之 :-)

最常見的 PEG 解析方式是使用可以無限回溯的遞歸下降解析器。

以上周文章中的玩具語言為例:

          
            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
          
        

這種語言中超級抽象的遞歸下降解析器將為每個符號定義一個函數(shù),該函數(shù)會嘗試調(diào)用與備選項相對應(yīng)的函數(shù)。

例如,對于 statement ,我們有如下函數(shù):

          
            def statement():
    if assignment():
        return True
   if expr():
        return True
    if if_statement():
        return True
    return False
          
        

當(dāng)然這是極其簡化的版本:沒有考慮解析器中必要的輸入及輸出。

我們就從輸入端開始講吧。

經(jīng)典解析器使用單獨(dú)的標(biāo)記生成器,來將輸入(文本文件或字符串)分解成一系列的標(biāo)記,例如關(guān)鍵字、標(biāo)識符(名稱)、數(shù)字與運(yùn)算符。

(譯注:標(biāo)記生成器,即 tokenizer,用于生成標(biāo)記 token。以下簡稱為“標(biāo)記器”)

PEG 解析器(像其它現(xiàn)代解析器,如 ANTLR)通常會把標(biāo)記與解析過程統(tǒng)一。但是對于我的項目,我選擇保留單獨(dú)的標(biāo)記器。

對 Python 做標(biāo)記太復(fù)雜了,我不想拘泥于 PEG 的形式來重新實現(xiàn)。

例如,你必須得記錄縮進(jìn)(這需要在標(biāo)記器內(nèi)使用堆棧),而且在 Python 中處理換行很有趣(它們很重要,除了在匹配的括號內(nèi))。字符串的多種引號也會增加復(fù)雜性。

簡而言之,我不抱怨 Python 現(xiàn)有的標(biāo)記器,所以我想保留它。(CPython 有兩個標(biāo)記器,一個是解析器在內(nèi)部使用的,寫于 C,另一個在標(biāo)準(zhǔn)庫中,用純 Python 重寫。它對我的項目很有幫助。)

經(jīng)典的標(biāo)記器通常具有一個簡單的接口,供你作函數(shù)調(diào)用,例如 get_token() ,它返回輸入內(nèi)容中的下一個標(biāo)記,每次消費(fèi)掉幾個字符。

tokenize 模塊對它作了進(jìn)一步簡化:它的基礎(chǔ) API 是一個生成器,每次生成(yield)一個標(biāo)記。

每個標(biāo)記都是一個 TypeInfo 對象,它有幾個字段,其中最重要之一表示的是標(biāo)記的類型(例如 NAME NUMBER STRING ),還有一個很重要的是字符串值,表示該標(biāo)記所包含的字符(例如 abc 42 或者 "hello world" )。還有的字段會指明每個標(biāo)記出現(xiàn)在輸入文件中的坐標(biāo),這對于報告錯誤很有用。

有一個特殊的標(biāo)記類型是 ENDMARKER ,它表示的是抵達(dá)了輸入文件的末尾。如果你忽略它,并嘗試獲取下一個標(biāo)記,則生成器會終結(jié)。

離題了,回歸正題。 我們?nèi)绾螌崿F(xiàn)無限回溯呢?

回溯要求你能記住源碼中的位置,并且能夠從該處重新解析。標(biāo)記器的 API 不允許我們重置它的輸入指針,但相對容易的是,將標(biāo)記流裝入一個數(shù)組中,并在那里做指針重置,所以我們就這樣做。(你同樣可以使用 itertools.tee() 來做,但是根據(jù)文檔中的警告,在我們這種情況下,效率可能較低。)

我猜你可能會先將整個輸入內(nèi)容標(biāo)記到一個 Python 列表里,將其作為解析器的輸入,但這意味著如果在文件末尾處存在著無效的標(biāo)記(例如一個字符串缺少結(jié)束的引號),而在文件前面還有語法錯誤,那你首先會收到的是關(guān)于標(biāo)記錯誤的信息。

我覺得這是種糟糕的用戶體驗,因為這個語法錯誤有可能是導(dǎo)致字符串殘缺的根本原因。

所以我的設(shè)計是按需標(biāo)記,所用的列表是惰性列表。

基礎(chǔ) API 非常簡單。 Tokenizer 對象封裝了一個數(shù)組,存放標(biāo)記及其位置信息。

它有三個基本方法:

  • get_token() 返回下一個標(biāo)記,并推進(jìn)數(shù)組的索引(如果到了數(shù)組末尾,則從源碼中讀取另一個標(biāo)記)
  • mark() 返回數(shù)組的當(dāng)前索引
  • reset(pos) 設(shè)置數(shù)組的索引(參數(shù)必須從 mark() 方法中得到)

我們再補(bǔ)充一個便利方法 peek_token() ,它返回下一個標(biāo)記且不推進(jìn)索引。

然后,這就成了 Tokenizer 類的核心代碼:

          
            class Tokenizer:
    def __init__(self, tokengen):
        """Call with tokenize.generate_tokens(...)."""
        self.tokengen = tokengen
        self.tokens = []
        self.pos = 0
    def mark(self):
        return self.pos
    def reset(self, pos):
        self.pos = pos
    def get_token(self):
        token = self.peek_token()
        self.pos += 1
        return token
    def peek_token(self):
        if self.pos == len(self.tokens):
            self.tokens.append(next(self.tokengen))
        return self.tokens[self.pos]
          
        

現(xiàn)在,仍然缺失著很多東西(而且方法和實例變量的名稱應(yīng)該以下劃線開頭),但這作為 Tokenizer API 的初稿已經(jīng)夠了。

解析器也需要變成一個類,以便可以擁有 statement()、expr() 和其它方法。

標(biāo)記器則變成一個實例變量,不過我們不希望解析方法(parsing methods)直接調(diào)用 get_token()——相反,我們給 Parser 類一個 expect() 方法,它可以像解析類方法一樣,表示執(zhí)行成功或失敗。

expect() 的參數(shù)是一個預(yù)期的標(biāo)記——一個字符串(像“+”)或者一個標(biāo)記類型(像 NAME )。

討論完了解析器的輸出,我繼續(xù)講返回類型(return type)。

在我初稿的解析器中,解析函數(shù)只返回 True 或 False。那對于理論計算機(jī)科學(xué)來說是好的(解析器要解答的那類問題是“語言中的這個是否是有效的字符串?”),但是對于構(gòu)建解析器卻不是——相反,我們希望用解析器來創(chuàng)建一個 AST。

所以我們就這么辦,即讓每個解析方法在成功時返回 Node 對象,在失敗時返回 None

Node 類可以超級簡單:

          
            class Node:
    def __init__(self, type, children):
        self.type = type
        self.children = children
          
        

在這里,type 表示了該 AST 節(jié)點(diǎn)是什么類型(例如是個“add”節(jié)點(diǎn)或者“if”節(jié)點(diǎn)),children 表示了一些節(jié)點(diǎn)和標(biāo)記(TokenInfo 類的實例)。

盡管將來我可能會改變表示 AST 的方式,但這足以讓編譯器生成代碼或?qū)ζ渥鞣治隽耍?linting (譯注:不懂)或者是靜態(tài)類型檢查。

為了適應(yīng)這個方案,expect() 方法在成功時會返回一個 TokenInfo 對象,在失敗時返回 None。為了支持回溯,我還封裝了標(biāo)記器的 mark() 和 reset() 方法(不改變 API)。

這是 Parser 類的基礎(chǔ)結(jié)構(gòu):

          
            class Parser:
    def __init__(self, tokenizer):
        self.tokenizer = tokenizer
    def mark(self):
        return self.tokenizer.mark()
    def reset(self, pos):
        self.tokenizer.reset(pos)
    def expect(self, arg):
        token = self.tokenizer.peek_token()
        if token.type == arg or token.string == arg:
            return self.tokenizer.get_token()
        return None
          
        

同樣地,我放棄了某些細(xì)節(jié),但它可以工作。

在這里,我有必要介紹解析方法的一個重要的需求:一個解析方法要么返回一個 Node,并將標(biāo)記器定位到它能識別的語法規(guī)則的最后一個標(biāo)記之后;要么返回 None,然后保持標(biāo)記器的位置不變。

如果解析方法在讀取了多個標(biāo)記之后失敗了,則它必須重置標(biāo)記器的位置。這就是 mark() 與 reset() 的用途。請注意,expect() 也遵循此規(guī)則。

所以解析器的實際草稿如下。請注意,我使用了 Python 3.8 的海象運(yùn)算符(:=):

          
            class ToyParser(Parser):
    def statement(self):
        if a := self.assignment():
            return a
        if e := self.expr():
            return e
        if i := self.if_statement():
            return i
        return None
    def expr(self):
        if t := self.term():
            pos = self.mark()
            if op := self.expect("+"):
                if e := self.expr():
                    return Node("add", [t, e])
            self.reset(pos)
            if op := self.expect("-"):
                if e := self.expr():
                    return Node("sub", [t, e])
            self.reset(pos)
            return t
        return None
    def term(self):
        # Very similar...
    def atom(self):
        if token := self.expect(NAME):
            return token
        if token := self.expect(NUMBER):
            return token
        pos = self.mark()
        if self.expect("("):
            if e := self.expr():
                if self.expect(")"):
                    return e
        self.reset(pos)
        return None
          
        

我給讀者們留了一些解析方法作為練習(xí)(這實際上不僅僅是為了介紹解析器長什么樣子),最終我們將像這樣從語法中自動地生成代碼。

NAME 和 NUMBER 等常量可從標(biāo)準(zhǔn)庫的 token 庫中導(dǎo)入。(這能令我們快速地進(jìn)入 Python 的標(biāo)記過程;但如果想要構(gòu)建一個更加通用的 PEG 解析器,則應(yīng)該探索一些其它方法。)

我還作了個小弊: expr 是左遞歸的,但我的解析器用了右遞歸,因為遞歸下降解析器不適用于左遞歸的語法規(guī)則。

有一個解決方案,但它還只是一些學(xué)術(shù)研究上的課題,我想以后單獨(dú)介紹它。你們只需知道,修復(fù)的版本與這個玩具語法并非 100% 相符。

我希望你們得到的關(guān)鍵信息是:

  • 語法規(guī)則相當(dāng)于解析器方法,當(dāng)一條語法規(guī)則引用另一條語法規(guī)則時,它的解析方法會調(diào)用另一條規(guī)則的解析方法
  • 當(dāng)多個條目構(gòu)成備選項時,解析方法會一個接一個地調(diào)用相應(yīng)的方法
  • 當(dāng)一條語法規(guī)則引用一個標(biāo)記時,其解析方法會調(diào)用 expect()
  • 當(dāng)一個解析方法在給定的輸入位置成功地識別了它的語法規(guī)則時,它返回相應(yīng)的 AST 節(jié)點(diǎn);當(dāng)識別失敗時,它返回 None
  • 一個解析方法在消費(fèi)(consum)一個或多個標(biāo)記(直接或間接地,通過調(diào)用另一個成功的解析方法)后放棄解析時,必須顯式地重置標(biāo)記器的位置。這適用于放棄一個備選項而嘗試下一個,也適用于完全地放棄解析

如果所有的解析方法都遵守這些規(guī)則,則不必在單個解析方法中使用 mark() 和 reset()。你可以用歸納法證明這一點(diǎn)。

順便提醒,雖然使用上下文管理器和 with 語句來替代顯式地調(diào)用 mark() 與 reset() 很有誘惑力,但這不管用:在成功時不應(yīng)調(diào)用 reset()!

為了修復(fù)它,你可以在控制流中使用異常,這樣上下文管理器就知道是否該重置標(biāo)記器(我認(rèn)為 TatSu 做了類似的東西)。

舉例,你可以這樣做:

          
                def statement(self):
        with self.alt():
            return self.assignment()
        with self.alt():
            return self.expr()
        with self.alt():
            return self.if_statement()
        raise ParsingFailure
          
        

特別地, atom() 中用來識別帶括號的表達(dá)式的 if-語句,可以變成:

          
                    with self.alt():
            self.expect("(")
            e = self.expr()
            self.expect(")")
            return e
          
        

但我發(fā)現(xiàn)這太“神奇”了——在閱讀這些代碼時,你必須清醒地意識到每個解析方法(以及 expect())都可能會引發(fā)異常,而這個異常會被 with 語句的上下文管理器捕獲并忽略掉。

這相當(dāng)不尋常,盡管肯定會支持(通過從 __exit__ 返回 true)。

還有,我的最終目標(biāo)是生成 C,不是 Python,而在 C 里,沒有 with 語句來改變控制流。

不管怎樣,下面是未來的一些主題:

  • 根據(jù)語法生成解析代碼
  • packrat 解析(記憶法)
  • EBNF 的特性,如(x | y)、[x y ...]、x* 、x+
  • tracing (用于調(diào)試解析器或語法)
  • PEG 特性,如前瞻和“切割”
  • 如何處理左遞歸規(guī)則
  • 生成 C 代碼

相關(guān)鏈接:

1、PEG解析器(考慮替換現(xiàn)有解析器)

2、pgen解析器(現(xiàn)有解析器的由來)

Python 之父再發(fā)文:構(gòu)建一個 PEG 解析器_第2張圖片

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


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 韩日性视频| 波多野结衣免费免费视频一区 | 欧做爰xxxⅹ性欧美大片孕妇 | 亚洲国产精品不卡毛片a在线 | 青青久草在线 | 国产成在线观看免费视频成本人 | 四虎影音在线观看 | 亚洲综合在线成人一区 | 97久久人人爽人人爽人人 | 亚洲香蕉一区二区三区在线观看 | 男人搡女人视频免费看 | 国产玖玖在线 | 特级黄色视频毛片 | 伊人久久中文 | 女十八毛片 | 欧美人成在线 | 写真福利 第 页 在线视频 | 天天曰天天干天天操 | 高清在线一区二区三区亚洲综合 | 日本一级特黄毛片高清视频 | 色视频在线观看视频 | 久久精品视频免费看 | 国产精品99一区二区三区 | 美女视频黄的全i免费 | 亚洲五月综合网色九月色 | 国产人成精品免费视频 | 国产成人精品福利色多多 | 国产伦码精品一区二区 | 在线观看欧洲成人免费视频 | 香蕉视频黄色在线观看 | 亚洲精品麻豆 | 亚洲视频中文字幕 | 女人寂寞偷人视频a级 | 久久伊人网站 | 成年男女免费视频网站 | 久99频这里只精品23热 视频 | 538在线视频二三区视视频 | 夜夜夜夜夜夜夜工噜噜噜 | 久久亚洲国产精品 | 美国美女一级毛片免费全 | 久久天天丁香婷婷中文字幕 |