原題 | Generating a PEG Parser

作者 | Guido van Rossum（Python之父）

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

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

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

我已經在本系列第二篇文章中簡述了解析器的基礎結構，并展示了一個簡單的手寫解析器，根據承諾，我們將轉向從語法中生成解析器。我還將展示如何使用 @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進階系列、好書推薦系列、技術寫作、優質英文推薦與翻譯等等，歡迎關注哦。