Python 之父的解析器系列之七：PEG 解析器的元語法

• 2019 年 10 月 3 日
• 筆記

原題 | A Meta-Grammar for PEG Parsers

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（「Python貓」公眾號作者）

聲明 | 本翻譯是出於交流學習的目的，基於 CC BY-NC-SA 4.0 授權協議。為便於閱讀，內容略有改動。本系列的譯文已在 Github 開源，項目地址：https://github.com/chinesehuazhou/guido_blog_translation

本周我們使解析器生成器完成「自託管」（self-hosted），也就是讓它自己生成解析器。

首先我們有了一個解析器生成器，其中一部分是語法解析器。我們可以稱之為元解析器（meta-parser）。該元解析器與要生成的解析器類似：GrammarParser 繼承自Parser ，它使用相同的 mark()/reset()/expect() 機制。然而，它是手寫的。但是，只能是手寫么？

在編譯器設計中有一個傳統，即編譯器使用它要編譯的語言編寫。我深切地記得在我初學編程時，當時用的 Pascal 編譯器是用 Pascal 本身編寫的，GCC 是用 C 編寫的，Rust 編譯器當然是用 Rust 編寫的。

這是怎麼做到的呢？有一個輔助過程（bootstrap，引導程序，通常譯作「自舉」）：對於一種語言的子集或早期版本，它的編譯器是用其它的語言編寫的。（我記得最初的 Pascal 編譯器是用 FORTRAN 編寫的！）然後用編譯後的語言編寫一個新的編譯器，並用輔助的編譯器來編譯它。一旦新的編譯器運行得足夠好，輔助的編譯器就會被廢棄，並且該語言或新編譯器的每個新版本，都會受到先前版本的編譯器的編譯能力的約束。

讓我們的元解析器如法炮製。我們將為語法編寫一個語法（元語法），然後我們將從中生成一個新的元解析器。幸運的是我從一開始就計划了，所以這是一個非常簡單的練習。我們在上一篇文章中添加的動作是必不可少的因素，因為我們不希望被迫去更改生成器——因此我們需要能夠生成一個可兼容的數據結構。

這是一個不加動作的元語法的簡化版：

start: rules ENDMARKER  rules: rule rules | rule  rule: NAME ":" alts NEWLINE  alts: alt "|" alts | alt  alt: items  items: item items | item  item: NAME | STRING

我將自下而上地展示如何添加動作。參照第 3 篇，我們有了一些帶 name 和 alts 屬性的 Rule 對象。最初，alts 只是一個包含字符串列表的列表（外層列表代表備選項，內層列表代表備選項的條目），但為了添加動作，我更改了一些內容，備選項由具有 items 和 action 屬性的 Alt 對象來表示。條目仍然由純字符串表示。對於 item 規則，我們有：

item: NAME { name.string } | STRING { string.string }

這需要一些解釋：當解析器處理一個標識符時，它返回一個 TokenInfo 對象，該對象具有 type、string 及其它屬性。我們不希望生成器來處理 TokenInfo 對象，因此這裡加了動作，它會從標識符中提取出字符串。請注意，對於像 NAME 這樣的全大寫標識符，生成的解析器會使用小寫版本（此處為 name ）作為變量名。

接下來是 items 規則，它必須返回一個字符串列表：

items: item items { [item] + items } | item { [item] }

我在這裡使用右遞歸規則，所以我們不依賴於第 5 篇中添加的左遞歸處理。（為什麼不呢？保持事情儘可能簡單總是一個好主意，這個語法使用左遞歸的話，不是很清晰。）請注意，單個的 item 已被分層，但遞歸的 items 沒有，因為它已經是一個列表。

alt 規則用於構建 Alt 對象：

alt: items { Alt(items) }

我就不介紹 rules 和 start 規則了，因為它們遵循相同的模式。

但是，有兩個未解決的問題。首先，生成的代碼如何知道去哪裡找到 Rule 和 Alt 類呢？為了實現這個目的，我們需要為生成的代碼添加一些 import 語句。最簡單的方法是給生成器傳遞一個標誌，該標誌表示「這是元語法」，然後讓生成器在生成的程序頂部引入額外的 import 語句。但是既然我們已經有了動作，許多其它解析器也會想要自定義它們的導入，所以為什麼我們不試試看，能否添加一個更通用的功能呢。

有很多方法可以剝了這隻貓的皮（譯註：skin this cat，解決這個難題）。一個簡單而通用的機制是在語法的頂部添加一部分「變量定義」，並讓生成器使用這些變量，來控制生成的代碼的各個方面。我選擇使用 @ 字符來開始一個變量定義，在它之後是變量名（一個 NAME）和值（一個 STRING）。例如，我們可以將以下內容放在元語法的頂部：

@subheader "from grammar import Rule, Alt"

標準的導入總是會打印（例如，去導入 memoize），在那之後，解析器生成器會打印 subheader 變量的值。如果需要多個 import，可以在變量聲明中使用三引號字符串，例如：

@subheader """  from token import OP  from grammar import Rule, Alt  """

這很容易添加到元語法中，我們用這個替換 start 規則：

start: metas rules ENDMARKER | rules ENDMARKER  metas: meta metas | meta  meta: "@" NAME STRING NEWLINE

（我不記得為什麼我會稱它們為「metas」，但這是我在編寫代碼時選擇的名稱，我會堅持這樣叫。:-)

我們還必須將它添加到輔助的元解析器中。既然語法不僅僅是一系列的規則，那麼讓我們添加一個 Grammar 對象，其中包含屬性 metas 和 rules。我們可以放入如下的動作：

start: metas rules ENDMARKER { Grammar(rules, metas) }       | rules ENDMARKER { Grammar(rules, []) }  metas: meta metas { [meta] + metas }       | meta { [meta] }  meta: "@" NAME STRING { (name.string, eval(string.string)) }

（注意 meta 返回一個元組，並注意它使用 eval() 來處理字符串引號。）

說到動作，我漏講了 alt 規則的動作！原因是這裏面有些混亂。但我不能再無視它了，上代碼吧：

alt: items action { Alt(items, action) }     | items { Alt(items, None) }  action: "{" stuffs "}" { stuffs }  stuffs: stuff stuffs { stuff + " " + stuffs }        | stuff { stuff }  stuff: "{" stuffs "}" { "{" + stuffs + "}" }       | NAME { name.string }       | NUMBER { number.string }       | STRING { string.string }       | OP { None if op.string in ("{", "}") else op.string }

這個混亂是由於我希望在描繪動作的花括號之間允許任意 Python 代碼，以及允許配對的大括號嵌套在其中。為此，我們使用了特殊標識符 OP，標記生成器用它生成可被 Python 識別的所有標點符號（返回一個類型為 OP 標識符，用於多字符運算符，如 <= 或 ** ）。在 Python 表達式中可以合法地出現的唯一其它標識符是名稱、數字和字符串。因此，在動作的最外側花括號之間的「東西」似乎是一組循環的 NAME | NUMBER | STRING | OP 。

嗚呼，這沒用，因為 OP 也匹配花括號，但由於 PEG 解析器是貪婪的，它會吞掉結束括號，我們就永遠看不到動作的結束。因此，我們要對生成的解析器添加一些調整，允許動作通過返回 None 來使備選項失效。我不知道這是否是其它 PEG 解析器的標準配置——當我考慮如何解決右括號（甚至嵌套的符號）的識別問題時，立馬就想到了這個方法。它似乎運作良好，我認為這符合 PEG 解析的一般哲學。它可以被視為一種特殊形式的前瞻（我將在下面介紹）。

使用這個小調整，當出現花括號時，我們可以使 OP 上的匹配失效，它可以通過 stuff 和 action 進行匹配。

有了這些東西，元語法可以由輔助的元解析器解析，並且生成器可以將它轉換為新的元解析器，由此解析自己。更重要的是，新的元解析器仍然可以解析相同的元語法。如果我們使用新的元編譯器編譯元語法，則輸出是相同的：這證明生成的元解析器正常工作。

這是帶有動作的完整元語法。只要你把解析過程串起來，它就可以解析自己：

@subheader """  from grammar import Grammar, Rule, Alt  from token import OP  """  start: metas rules ENDMARKER { Grammar(rules, metas) }       | rules ENDMARKER { Grammar(rules, []) }  metas: meta metas { [meta] + metas }       | meta { [meta] }  meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) }  rules: rule rules { [rule] + rules }       | rule { [rule] }  rule: NAME ":" alts NEWLINE { Rule(name.string, alts) }  alts: alt "|" alts { [alt] + alts }      | alt { [alt] }  alt: items action { Alt(items, action) }     | items { Alt(items, None) }  items: item items { [item] + items }       | item { [item] }  item: NAME { name.string }      | STRING { string.string }  action: "{" stuffs "}" { stuffs }  stuffs: stuff stuffs { stuff + " " + stuffs }        | stuff { stuff }  stuff: "{" stuffs "}" { "{" + stuffs + "}" }       | NAME { name.string }       | NUMBER { number.string }       | STRING { string.string }       | OP { None if op.string in ("{", "}") else op.string }

現在我們已經有了一個能工作的元語法，可以準備做一些改進了。

但首先，還有一個小麻煩要處理：空行！事實證明，標準庫的 tokenize 會生成額外的標識符來跟蹤非重要的換行符和注釋。對於前者，它生成一個 NL 標識符，對於後者，則是一個 COMMENT 標識符。以其將它們吸收進語法中（我已經嘗試過，但並不容易！），我們可以在 tokenizer 類中添加一段非常簡單的代碼，來過濾掉這些標識符。這是改進的 peek_token 方法：

def peek_token(self):          if self.pos == len(self.tokens):              while True:                  token = next(self.tokengen)                  if token.type in (NL, COMMENT):                      continue                  break              self.tokens.append(token)              self.report()          return self.tokens[self.pos]

這樣就完全過濾掉了 NL 和 COMMENT 標識符，因此在語法中不再需要擔心它們。

最後讓我們對元語法進行改進！我想做的事情純粹是美容性的：我不喜歡被迫將所有備選項放在同一行上。我上面展示的元語法實際上並沒有解析自己，因為有這樣的情況：

start: metas rules ENDMARKER { Grammar(rules, metas) }       | rules ENDMARKER { Grammar(rules, []) }

這是因為標識符生成器（tokenizer）在第一行的末尾產生了一個 NEWLINE 標識符，此時元解析器會認為這是該規則的結束。此外，NEWLINE 之後會出現一個 INDENT 標識符，因為下一行是縮進的。在下一個規則開始之前，還會有一個 DEDENT 標識符。

下面是解決辦法。為了理解 tokenize 模塊的行為，我們可以將 tokenize 模塊作為腳本運行，並為其提供一些文本，以此來查看對於縮進塊，會生成什麼樣的標識符序列：

$ python -m tokenize  foo bar      baz      dah  dum  ^D

我們發現它會產生以下的標識符序列（我已經簡化了上面運行的輸出）：

NAME     'foo'  NAME     'bar'  NEWLINE  INDENT  NAME     'baz'  NEWLINE  NAME     'dah'  NEWLINE  DEDENT  NAME     'dum'  NEWLINE

這意味着一組縮進的代碼行會被 INDENT 和 DEDENT 標記符所描繪。現在，我們可以重新編寫元語法規則的 rule 如下：

rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT {          Rule(name.string, alts + more_alts) }      | NAME ":" alts NEWLINE { Rule(name.string, alts) }      | NAME ":" NEWLINE INDENT more_alts DEDENT {          Rule(name.string, more_alts) }  more_alts: "|" alts NEWLINE more_alts { alts + more_alts }           | "|" alts NEWLINE { alts }

（我跨行地拆分了動作，以便它們適應 Medium 網站的窄頁——這是可行的，因為標識符生成器會忽略已配對的括號內的換行符。）

這樣做的好處是我們甚至不需要更改生成器：這種改進的元語法生成的數據結構跟以前相同。同樣注意 rule 的第三個備選項，對此讓我們寫：

start:      | metas rules ENDMARKER { Grammar(rules, metas) }      | rules ENDMARKER { Grammar(rules, []) }

有些人會覺得這比我之前展示的版本更乾淨。很容易允許兩種形式共存，所以我們不必爭論風格。

在下一篇文章中，我將展示如何實現各種 PEG 功能，如可選條目、重複和前瞻。（說句公道話，我本打算把那放在這篇里，但是這篇已寫太長了，所以我要把它分成兩部分。）

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

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