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

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

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

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

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

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

---

原題 | Building a PEG Parser

作者 | Guido van Rossum（Python之父）

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

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

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

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

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

（順便說(shuō)一句，作為一個(gè)實(shí)驗(yàn)，我不會(huì)在文中到處放參考鏈接。如果你有什么不明白的東西，請(qǐng) Google 之 :-）

最常見(jiàn)的 PEG 解析方式是使用可以無(wú)限回溯的遞歸下降解析器。

以上周文章中的玩具語(yǔ)言為例：

          
            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
          
        

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

例如，對(duì)于 statement ，我們有如下函數(shù)：

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

當(dāng)然這是極其簡(jiǎn)化的版本：沒(méi)有考慮解析器中必要的輸入及輸出。

我們就從輸入端開(kāi)始講吧。

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

（譯注：標(biāo)記生成器，即 tokenizer，用于生成標(biāo)記 token。以下簡(jiǎn)稱為“標(biāo)記器”）

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

對(duì) Python 做標(biāo)記太復(fù)雜了，我不想拘泥于 PEG 的形式來(lái)重新實(shí)現(xiàn)。

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

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

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

tokenize 模塊對(duì)它作了進(jìn)一步簡(jiǎn)化：它的基礎(chǔ) API 是一個(gè)生成器，每次生成（yield）一個(gè)標(biāo)記。

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

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

離題了，回歸正題。 我們?nèi)绾螌?shí)現(xiàn)無(wú)限回溯呢？

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

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

我覺(jué)得這是種糟糕的用戶體驗(yàn)，因?yàn)檫@個(gè)語(yǔ)法錯(cuò)誤有可能是導(dǎo)致字符串殘缺的根本原因。

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

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

它有三個(gè)基本方法：

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

我們?cè)傺a(bǔ)充一個(gè)便利方法 peek_token() ，它返回下一個(gè)標(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)在，仍然缺失著很多東西（而且方法和實(shí)例變量的名稱應(yīng)該以下劃線開(kāi)頭），但這作為 Tokenizer API 的初稿已經(jīng)夠了。

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

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

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

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

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

所以我們就這么辦，即讓每個(gè)解析方法在成功時(shí)返回 Node 對(duì)象，在失敗時(shí)返回 None 。

該 Node 類可以超級(jí)簡(jiǎn)單：

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

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

盡管將來(lái)我可能會(huì)改變表示 AST 的方式，但這足以讓編譯器生成代碼或?qū)ζ渥鞣治隽?，例?linting （譯注：不懂）或者是靜態(tài)類型檢查。

為了適應(yīng)這個(gè)方案，expect() 方法在成功時(shí)會(huì)返回一個(gè) TokenInfo 對(duì)象，在失敗時(shí)返回 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é)，但它可以工作。

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

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

所以解析器的實(shí)際草稿如下。請(qǐng)注意，我使用了 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í)（這實(shí)際上不僅僅是為了介紹解析器長(zhǎng)什么樣子），最終我們將像這樣從語(yǔ)法中自動(dòng)地生成代碼。

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

我還作了個(gè)小弊： expr 是左遞歸的，但我的解析器用了右遞歸，因?yàn)檫f歸下降解析器不適用于左遞歸的語(yǔ)法規(guī)則。

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

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

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

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

順便提醒，雖然使用上下文管理器和 with 語(yǔ)句來(lái)替代顯式地調(diào)用 mark() 與 reset() 很有誘惑力，但這不管用：在成功時(shí)不應(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() 中用來(lái)識(shí)別帶括號(hào)的表達(dá)式的 if-語(yǔ)句，可以變成：

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

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

這相當(dāng)不尋常，盡管肯定會(huì)支持（通過(guò)從 __exit__ 返回 true）。

還有，我的最終目標(biāo)是生成 C，不是 Python，而在 C 里，沒(méi)有 with 語(yǔ)句來(lái)改變控制流。

不管怎樣，下面是未來(lái)的一些主題：

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

相關(guān)鏈接：

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

2、pgen解析器（現(xiàn)有解析器的由來(lái)）

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