Python 之父再發文：構建一個 PEG 解析器

image

花下貓語： Python 之父在 Medium 上開了博客，現在寫了兩篇文章，本文是第二篇的譯文。前一篇的譯文 在此 ，宣布了將要用 PEG 解析器來替換當前的 pgen 解析器。

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

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

我會持續跟進后續文章的翻譯，由于能力有限，可能翻譯中有不到位之處，懇請讀者們批評指正。

本文原創并首發于公眾號【 Python貓 】，未經授權，請勿轉載。

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

原題 | Building a PEG Parser

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號作者）

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

聲明 | 翻譯是出于交流學習的目的，歡迎轉載，但請保留本文出處，請勿用于商業或非法用途。

僅僅理解了 PEG 解析器的小部分，我就受到了啟發，決定自己構建一個。結果可能不是一個很棒的通用型的 PEG 解析器生成器——這類生成器已經有很多了（例如 TatSu，寫于 Python，生成 Python 代碼）——但這是一個學習 PEG 的好辦法，推進了我的目標，即用由 PEG 語法構建的解析器替換 CPython 的解析器。

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

（順便說一句，作為一個實驗，我不會在文中到處放參考鏈接。如果你有什么不明白的東西，請 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

          
        

這種語言中超級抽象的遞歸下降解析器將為每個符號定義一個函數，該函數會嘗試調用與備選項相對應的函數。

例如，對于 statement ，我們有如下函數：

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

          
        

當然這是極其簡化的版本：沒有考慮解析器中必要的輸入及輸出。

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

經典解析器使用單獨的標記生成器，來將輸入（文本文件或字符串）分解成一系列的標記，例如關鍵字、標識符（名稱）、數字與運算符。

（譯注：標記生成器，即 tokenizer，用于生成標記 token。以下簡稱為“標記器”）

PEG 解析器（像其它現代解析器，如 ANTLR）通常會把標記與解析過程統一。但是對于我的項目，我選擇保留單獨的標記器。

對 Python 做標記太復雜了，我不想拘泥于 PEG 的形式來重新實現。

例如，你必須得記錄縮進（這需要在標記器內使用堆棧），而且在 Python 中處理換行很有趣（它們很重要，除了在匹配的括號內）。字符串的多種引號也會增加復雜性。

簡而言之，我不抱怨 Python 現有的標記器，所以我想保留它。（CPython 有兩個標記器，一個是解析器在內部使用的，寫于 C，另一個在標準庫中，用純 Python 重寫。它對我的項目很有幫助。）

經典的標記器通常具有一個簡單的接口，供你作函數調用，例如 get_token() ，它返回輸入內容中的下一個標記，每次消費掉幾個字符。

tokenize 模塊對它作了進一步簡化：它的基礎 API 是一個生成器，每次生成（yield）一個標記。

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

有一個特殊的標記類型是 ENDMARKER ，它表示的是抵達了輸入文件的末尾。如果你忽略它，并嘗試獲取下一個標記，則生成器會終結。

離題了，回歸正題。 我們如何實現無限回溯呢？

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

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

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

所以我的設計是按需標記，所用的列表是惰性列表。

基礎 API 非常簡單。 Tokenizer 對象封裝了一個數組，存放標記及其位置信息。

它有三個基本方法：

• get_token() 返回下一個標記，并推進數組的索引（如果到了數組末尾，則從源碼中讀取另一個標記）
• mark() 返回數組的當前索引
• reset(pos) 設置數組的索引（參數必須從 mark() 方法中得到）

我們再補充一個便利方法 peek_token() ，它返回下一個標記且不推進索引。

然后，這就成了 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]

          
        

現在，仍然缺失著很多東西（而且方法和實例變量的名稱應該以下劃線開頭），但這作為 Tokenizer API 的初稿已經夠了。

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

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

expect() 的參數是一個預期的標記——一個字符串（像“+”）或者一個標記類型（像 NAME ）。

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

在我初稿的解析器中，解析函數只返回 True 或 False。那對于理論計算機科學來說是好的（解析器要解答的那類問題是“語言中的這個是否是有效的字符串？”），但是對于構建解析器卻不是——相反，我們希望用解析器來創建一個 AST。

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

該 Node 類可以超級簡單：

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

          
        

在這里，type 表示了該 AST 節點是什么類型（例如是個“add”節點或者“if”節點），children 表示了一些節點和標記（TokenInfo 類的實例）。

盡管將來我可能會改變表示 AST 的方式，但這足以讓編譯器生成代碼或對其作分析了，例如 linting （譯注：不懂）或者是靜態類型檢查。

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

這是 Parser 類的基礎結構：

          
            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

          
        

同樣地，我放棄了某些細節，但它可以工作。

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

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

所以解析器的實際草稿如下。請注意，我使用了 Python 3.8 的海象運算符（:=）：

          
            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

          
        

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

NAME 和 NUMBER 等常量可從標準庫的 token 庫中導入。（這能令我們快速地進入 Python 的標記過程；但如果想要構建一個更加通用的 PEG 解析器，則應該探索一些其它方法。）

我還作了個小弊： expr 是左遞歸的，但我的解析器用了右遞歸，因為遞歸下降解析器不適用于左遞歸的語法規則。

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

**我希望你們得到的關鍵信息是： **

• 語法規則相當于解析器方法，當一條語法規則引用另一條語法規則時，它的解析方法會調用另一條規則的解析方法
• 當多個條目構成備選項時，解析方法會一個接一個地調用相應的方法
• 當一條語法規則引用一個標記時，其解析方法會調用 expect()
• 當一個解析方法在給定的輸入位置成功地識別了它的語法規則時，它返回相應的 AST 節點；當識別失敗時，它返回 None
• 一個解析方法在消費（consum）一個或多個標記（直接或間接地，通過調用另一個成功的解析方法）后放棄解析時，必須顯式地重置標記器的位置。這適用于放棄一個備選項而嘗試下一個，也適用于完全地放棄解析

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

順便提醒，雖然使用上下文管理器和 with 語句來替代顯式地調用 mark() 與 reset() 很有誘惑力，但這不管用：在成功時不應調用 reset()！

為了修復它，你可以在控制流中使用異常，這樣上下文管理器就知道是否該重置標記器（我認為 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() 中用來識別帶括號的表達式的 if-語句，可以變成：

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

          
        

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

這相當不尋常，盡管肯定會支持（通過從 __exit__ 返回 true）。

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

不管怎樣，下面是未來的一些主題：

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

相關鏈接：

1、PEG解析器（考慮替換現有解析器）

2、pgen解析器（現有解析器的由來）

image

公眾號【 Python貓 】， 本號連載優質的系列文章，有喵星哲學貓系列、Python進階系列、好書推薦系列、技術寫作、優質英文推薦與翻譯等等，歡迎關注哦。