Python 之父的解析器系列之三：生成一個 PEG 解析器

原題 | Generating a PEG Parser

作者 | Guido van Rossum（Python之父）

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

聲明 | 本翻譯是出於交流學習的目的，基於 CC BY-NC-SA 4.0 授權協議。為便於閱讀，內容略有改動。

首發地址：https://mp.weixin.qq.com/s/ojSq6u9FC0xlBDncuoKczw

我已經在本系列第二篇文章中簡述瞭解析器的基礎結構，並展示了一個簡單的手寫解析器，根據承諾，我們將轉向從語法中生成解析器。我還將展示如何使用@memoize裝飾器，以實現packrat 解析。

【這是 PEG 系列第 3 篇。參見第1篇、第2篇 】

上篇文章我們以一個手寫的解析器結束。給語法加上一些限制的話，我們很容易從語法中自動生成這樣的解析器。（我們稍後會解除那些限制。）

我們需要兩個東西：一個東西讀取語法，並構造一個表現語法規則的數據結構；還有一個東西則用該數據結構來生成解析器。我們還需要無聊的膠水，我就不提啦。

所以我們在這創造的是一個簡單的編譯器編譯器（compiler-compiler）。我將語法符號簡化了一些，僅保留規則與備選項；這其實對於我在本系列的前面所用的玩具語法來說，已經足夠了。

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

使用完整的符號，我們可以為語法文件寫出語法：

grammar: rule+ ENDMARKER
rule: NAME ':' alternative ('|' alternative)* NEWLINE
alternative: item+
item: NAME | STRING

用個花哨的叫法，這是我們的第一個元語法（語法的語法），而我們的解析器生成器將是一個元編譯器（編譯器是一個程式，將其它程式從一種語言轉譯為另一種語言；元編譯器是一種編譯器，其輸入是一套語法，而輸出是一個解析器 ）。

有個簡單地表示元語法的方法，主要是使用內置的數據類型：一條規則的右側只是由一系列的條目組成的列表，且這些條目只能是字元串。（Hack：通過檢查第一個字元是否為引號，我們可以區分出NAME和STRING）

至於規則，我用了一個簡單的 Rule 類，所以整個語法就是一些 Rule 對象。

這就是 Rule 類，省略了 __repr__ 與__eq__ ：

class Rule:
    def __init__(self, name, alts):
        self.name = name
        self.alts = alts

調用它的是這個GrammarParser類（關於基類Parser ，請參閱我之前的帖子）：

class GrammarParser(Parser):
    def grammar(self):
        pos = self.mark()
        if rule := self.rule():
            rules = [rule]
            while rule := self.rule():
                rules.append(rule)
            if self.expect(ENDMARKER):
                return rules    # <------------- final result
        self.reset(pos)
        return None
    def rule(self):
        pos = self.mark()
        if name := self.expect(NAME):
            if self.expect(":"):
                if alt := self.alternative():
                    alts = [alt]
                    apos = self.mark()
                    while (self.expect("|")
                           and (alt := self.alternative())):
                        alts.append(alt)
                        apos = self.mark()
                    self.reset(apos)
                    if self.expect(NEWLINE):
                        return Rule(name.string, alts)
        self.reset(pos)
        return None
    def alternative(self):
        items = []
        while item := self.item():
            items.append(item)
        return items
    def item(self):
        if name := self.expect(NAME):
            return name.string
        if string := self.expect(STRING):
            return string.string
        return None

註意 ENDMARKER ，它用來確保在最後一條規則後沒有遺漏任何東西（如果語法中出現拼寫錯誤，可能會導致這種情況）。

我放了一個簡單的箭頭，指向了 grammar() 方法的返回值位置，返回結果是一個存儲 Rule 的列表。

其餘部分跟上篇文章中的 ToyParser 類很相似，所以我不作解釋。

只需留意，item() 返回一個字元串，alternative() 返回一個字元串列表，而 rule() 中的 alts 變數，則是一個由字元串列表組成的列表。

然後，rule() 方法將規則名稱（一個字元串）與 alts 結合，放入 Rule 對象。

如果把這份代碼用到包含了我們的玩具語法的文件上，則 grammar() 方法會返回以下的由 Rule 對象組成的列表：

[
  Rule('statement', [['assignment'], ['expr'], ['if_statement']]),
  Rule('expr', [['term', "'+'", 'expr'],
                ['term', "'-'", 'term'],
                ['term']]),
  Rule('term', [['atom', "'*'", 'term'],
                ['atom', "'/'", 'atom'],
                ['atom']]),
  Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]),
  Rule('assignment', [['target', "'='", 'expr']]),
  Rule('target', [['NAME']]),
  Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]),
]

既然我們已經有了元編譯器的解析部分，那就創建代碼生成器吧。

把這些聚合起來，就形成了一個基本的元編譯器：

def generate_parser_class(rules):
    print(f"class ToyParser(Parser):")
    for rule in rules:
        print()
        print(f"    @memoize")
        print(f"    def {rule.name}(self):")
        print(f"        pos = self.mark()")
        for alt in rule.alts:
            items = []
            print(f"        if (True")
            for item in alt:
                if item[0] in ('"', "'"):
                    print(f"            and self.expect({item})")
                else:
                    var = item.lower()
                    if var in items:
                        var += str(len(items))
                    items.append(var)
                    if item.isupper():
                        print("            " +
                              f"and ({var} := self.expect({item}))")
                    else:
                        print(f"            " +
                              f"and ({var} := self.{item}())")
            print(f"        ):")
            print(f"            " +
              f"return Node({rule.name!r}, [{', '.join(items)}])")
            print(f"        self.reset(pos)")
        print(f"        return None")

這段代碼非常難看，但它管用（某種程度上），不管怎樣，我打算將來重寫它。

在"for alt in rule.alts"迴圈中，有些代碼細節可能需要作出解釋：對於備選項中的每個條目，我們有三種選擇的可能：

• 如果該條目是字元串字面量，例如'+' ，我們生成self.expect('+')
• 如果該條目全部是大寫，例如NAME ，我們生成(name := self.expect(NAME))
  
• 其它情況，例如該條目是expr，我們生成 (expr := self.expr())

如果在單個備選項中出現多個相同名稱的條目（例如term '-' term），我們會在第二個條目後附加一個數字。這裡還有個小小的 bug，我會在以後的內容中修複。

這隻是它的一部分輸出（完整的類非常無聊）。不用擔心那些零散的、冗長的 if (True and … ) 語句，我使用它們，以便每個生成的條件都能夠以and 開頭。Python 的位元組碼編譯器會優化它。

class ToyParser(Parser):
    @memoize
    def statement(self):
        pos = self.mark()
        if (True
            and (assignment := self.assignment())
        ):
            return Node('statement', [assignment])
        self.reset(pos)
        if (True
            and (expr := self.expr())
        ):
            return Node('statement', [expr])
        self.reset(pos)
        if (True
            and (if_statement := self.if_statement())
        ):
            return Node('statement', [if_statement])
        self.reset(pos)
        return None
    ...

註意@memoize 裝飾器：我“偷運”（smuggle）它進來，以便轉向另一個主題：使用記憶法（memoization）來加速生成的解析器。

這是實現該裝飾器的 memoize() 函數：

def memoize(func):
    def memoize_wrapper(self, *args):
        pos = self.mark()
        memo = self.memos.get(pos)
        if memo is None:
            memo = self.memos[pos] = {}
        key = (func, args)
        if key in memo:
            res, endpos = memo[key]
            self.reset(endpos)
        else:
            res = func(self, *args)
            endpos = self.mark()
            memo[key] = res, endpos
        return res
return memoize_wrapper

對於典型的裝飾器來說，它的嵌套函數（nested function）會替換（或包裝）被裝飾的函數（decorated function），例如 memoize_wrapper() 會包裝 ToyParser 類的 statement() 方法。

因為被包裝的函數（wrapped function）是一個方法，所以包裝器實際上也是一個方法：它的第一個參數是 self ，指向 ToyParser 實例，後者會調用被裝飾的函數。

包裝器會緩存每次調用解析方法後的結果——這就是為什麼它會被稱為“口袋老鼠解析”（packrat parsing）！

這緩存是一個字典，元素是存儲在 Parser 實例上的那些字典。

外部字典的 key 是輸入的位置；我將 self.memos = {} 添加到 Parser.__init__() ，以初始化它。

內部字典按需添加，它們的 key 由方法及其參數組成。（在當前的設計中沒有參數，但我們應該記得 expect()，它恰好有一個參數，而且給它新增通用性，幾乎不需要成本。 ）

一個解析方法的結果被表示成一個元組，因為它正好有兩個結果：一個顯式的返回值（對於我們生成的解析器，它是一個 Node，表示所匹配的規則），以及我們從 self.mark() 中獲得的一個新的輸入位置。

在調用解析方法後，我們會在內部的記憶字典中同時存儲它的返回值（res）以及新的輸入位置（endpos）。

再次調用相同的解析方法時（在相同的位置，使用相同的參數），我們會從緩存中取出那兩個結果，並用 self.reset() 來向前移動輸入位置，最後返回那緩存中的返回值。

緩存負數的結果也很重要——實際上大多數對解析方法的調用都是負數的結果。在此情況下，返回值為 None，而輸入位置不會變。你可以加一個assert 斷言來檢查它。

註意：Python 中常用的記憶法是在 memoize() 函數中將緩存定義成一個局部變數。但我們不這麼做：因為我在一個最後時刻的調試會話中發現，每個 Parser 實例都必須擁有自己的緩存。然而，你可以用(pos, func, args) 作為 key，以擺脫嵌套字典的設計。

下周我將統覽代碼，演示在解析示常式序時，所有這些模塊實際是如何配合工作的。

我仍然在抓頭髮中（譯註：極度發愁），如何以最佳的方式將協同工作的標記生成器緩衝、解析器和記憶緩存作出可視化。或許我會設法生成動畫的 ASCII 作品，而不僅僅是跟蹤日誌的輸出。（譯註：感覺他像是在開玩笑，但很難譯出這句話的原味。建議閱讀原文。）

本文及示例代碼的授權協議： CC BY-NC-SA 4.0

英文原文： https://medium.com/@gvanrossum_83706/generating-a-peg-parser-520057d642a9

作者簡介： Guido van Rossum，是 Python 的創造者，一直是“終身仁慈獨裁者”，直到2018年7月12日退位。目前，他是新的最高決策層的五位成員之一，依然活躍在社區中。

譯者簡介： 豌豆花下貓，生於廣東畢業於武大，現為蘇漂程式員，有一些極客思維，也有一些人文情懷，有一些溫度，還有一些態度。公眾號：「Python貓」（python_cat）。

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