原題 | A Meta-Grammar for PEG Parsers

作者 | Guido van Rossum（Python之父）

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

聲明 | 本翻譯是出于交流學(xué)習(xí)的目的药有，基于 CC BY-NC-SA 4.0 授權(quán)協(xié)議。為便于閱讀沪铭，內(nèi)容略有改動复斥。本系列的譯文已在 Github 開源，項(xiàng)目地址：https://github.com/chinesehuazhou/guido_blog_translation

本周我們使解析器生成器完成“自托管”（self-hosted）贝室，也就是讓它自己生成解析器。

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

在編譯器設(shè)計(jì)中有一個傳統(tǒng)，即編譯器使用它要編譯的語言編寫税迷。我深切地記得在我初學(xué)編程時永丝，當(dāng)時用的 Pascal 編譯器是用 Pascal 本身編寫的，GCC 是用 C 編寫的箭养，Rust 編譯器當(dāng)然是用 Rust 編寫的慕嚷。

這是怎么做到的呢？有一個輔助過程（bootstrap毕泌，引導(dǎo)程序喝检，通常譯作“自舉”）：對于一種語言的子集或早期版本，它的編譯器是用其它的語言編寫的撼泛。（我記得最初的 Pascal 編譯器是用 FORTRAN 編寫的Ｄ铀怠）然后用編譯后的語言編寫一個新的編譯器，并用輔助的編譯器來編譯它坎弯。一旦新的編譯器運(yùn)行得足夠好纺涤，輔助的編譯器就會被廢棄，并且該語言或新編譯器的每個新版本抠忘，都會受到先前版本的編譯器的編譯能力的約束撩炊。

讓我們的元解析器如法炮制。我們將為語法編寫一個語法（元語法）崎脉，然后我們將從中生成一個新的元解析器拧咳。幸運(yùn)的是我從一開始就計(jì)劃了，所以這是一個非常簡單的練習(xí)囚灼。我們在上一篇文章中添加的動作是必不可少的因素骆膝，因?yàn)槲覀儾幌Ｍ黄热ジ纳善鳌虼宋覀冃枰軌蛏梢粋€可兼容的數(shù)據(jù)結(jié)構(gòu)。

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

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 只是一個包含字符串列表的列表（外層列表代表備選項(xiàng)政钟，內(nèi)層列表代表備選項(xiàng)的條目），但為了添加動作樟结，我更改了一些內(nèi)容养交，備選項(xiàng)由具有 items 和 action 屬性的 Alt 對象來表示。條目仍然由純字符串表示瓢宦。對于 item 規(guī)則碎连，我們有：

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

這需要一些解釋：當(dāng)解析器處理一個標(biāo)識符時，它返回一個 TokenInfo 對象驮履，該對象具有 type鱼辙、string 及其它屬性廉嚼。我們不希望生成器來處理 TokenInfo 對象，因此這里加了動作座每，它會從標(biāo)識符中提取出字符串前鹅。請注意，對于像 NAME 這樣的全大寫標(biāo)識符峭梳，生成的解析器會使用小寫版本（此處為 name ）作為變量名。

接下來是 items 規(guī)則蹂喻，它必須返回一個字符串列表：

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

我在這里使用右遞歸規(guī)則葱椭，所以我們不依賴于第 5 篇中添加的左遞歸處理。（為什么不呢口四？保持事情盡可能簡單總是一個好主意孵运，這個語法使用左遞歸的話，不是很清晰蔓彩。）請注意治笨，單個的 item 已被分層，但遞歸的 items 沒有赤嚼，因?yàn)樗呀?jīng)是一個列表旷赖。

alt 規(guī)則用于構(gòu)建 Alt 對象：

alt: items { Alt(items) }

我就不介紹 rules 和 start 規(guī)則了，因?yàn)樗鼈冏裱嗤哪Ｊ健?/p>

但是更卒，有兩個未解決的問題等孵。首先，生成的代碼如何知道去哪里找到 Rule 和 Alt 類呢蹂空？為了實(shí)現(xiàn)這個目的俯萌，我們需要為生成的代碼添加一些 import 語句。最簡單的方法是給生成器傳遞一個標(biāo)志上枕，該標(biāo)志表示“這是元語法”咐熙，然后讓生成器在生成的程序頂部引入額外的 import 語句。但是既然我們已經(jīng)有了動作辨萍，許多其它解析器也會想要自定義它們的導(dǎo)入棋恼，所以為什么我們不試試看，能否添加一個更通用的功能呢分瘦。

有很多方法可以剝了這只貓的皮（譯注：skin this cat蘸泻，解決這個難題）。一個簡單而通用的機(jī)制是在語法的頂部添加一部分“變量定義”嘲玫，并讓生成器使用這些變量悦施，來控制生成的代碼的各個方面。我選擇使用 @ 字符來開始一個變量定義去团，在它之后是變量名（一個 NAME）和值（一個 STRING）抡诞。例如穷蛹，我們可以將以下內(nèi)容放在元語法的頂部：

@subheader "from grammar import Rule, Alt"

標(biāo)準(zhǔn)的導(dǎo)入總是會打印（例如昼汗，去導(dǎo)入 memoize）肴熏，在那之后，解析器生成器會打印 subheader 變量的值顷窒。如果需要多個 import蛙吏，可以在變量聲明中使用三引號字符串，例如：

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

這很容易添加到元語法中鞋吉，我們用這個替換 start 規(guī)則：

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

（我不記得為什么我會稱它們?yōu)椤癿etas”鸦做，但這是我在編寫代碼時選擇的名稱，我會堅(jiān)持這樣叫谓着。:-)

我們還必須將它添加到輔助的元解析器中泼诱。既然語法不僅僅是一系列的規(guī)則，那么讓我們添加一個 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 規(guī)則的動作！原因是這里面有些混亂阿纤。但我不能再無視它了句灌，上代碼吧：

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 代碼，以及允許配對的大括號嵌套在其中欠拾。為此胰锌，我們使用了特殊標(biāo)識符 OP，標(biāo)記生成器用它生成可被 Python 識別的所有標(biāo)點(diǎn)符號（返回一個類型為 OP 標(biāo)識符藐窄，用于多字符運(yùn)算符资昧，如 <= 或 ** ）。在 Python 表達(dá)式中可以合法地出現(xiàn)的唯一其它標(biāo)識符是名稱荆忍、數(shù)字和字符串格带。因此，在動作的最外側(cè)花括號之間的“東西”似乎是一組循環(huán)的 NAME | NUMBER | STRING | OP 刹枉。

嗚呼叽唱，這沒用，因?yàn)?OP 也匹配花括號微宝，但由于 PEG 解析器是貪婪的棺亭，它會吞掉結(jié)束括號，我們就永遠(yuǎn)看不到動作的結(jié)束蟋软。因此镶摘，我們要對生成的解析器添加一些調(diào)整嗽桩，允許動作通過返回 None 來使備選項(xiàng)失效。我不知道這是否是其它 PEG 解析器的標(biāo)準(zhǔn)配置——當(dāng)我考慮如何解決右括號（甚至嵌套的符號）的識別問題時凄敢，立馬就想到了這個方法碌冶。它似乎運(yùn)作良好，我認(rèn)為這符合 PEG 解析的一般哲學(xué)涝缝。它可以被視為一種特殊形式的前瞻（我將在下面介紹）扑庞。

使用這個小調(diào)整，當(dāng)出現(xiàn)花括號時拒逮，我們可以使 OP 上的匹配失效嫩挤，它可以通過 stuff 和 action 進(jìn)行匹配。

有了這些東西消恍，元語法可以由輔助的元解析器解析，并且生成器可以將它轉(zhuǎn)換為新的元解析器以现，由此解析自己狠怨。更重要的是，新的元解析器仍然可以解析相同的元語法邑遏。如果我們使用新的元編譯器編譯元語法佣赖，則輸出是相同的：這證明生成的元解析器正常工作。

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

@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 }

現(xiàn)在我們已經(jīng)有了一個能工作的元語法，可以準(zhǔn)備做一些改進(jìn)了纪吮。

但首先俩檬，還有一個小麻煩要處理：空行！事實(shí)證明碾盟，標(biāo)準(zhǔn)庫的 tokenize 會生成額外的標(biāo)識符來跟蹤非重要的換行符和注釋棚辽。對于前者，它生成一個 NL 標(biāo)識符冰肴，對于后者屈藐，則是一個 COMMENT 標(biāo)識符。以其將它們吸收進(jìn)語法中（我已經(jīng)嘗試過熙尉，但并不容易Ａ摺），我們可以在 tokenizer 類中添加一段非常簡單的代碼检痰，來過濾掉這些標(biāo)識符包归。這是改進(jìn)的 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 標(biāo)識符，因此在語法中不再需要擔(dān)心它們攀细。

最后讓我們對元語法進(jìn)行改進(jìn)箫踩！我想做的事情純粹是美容性的：我不喜歡被迫將所有備選項(xiàng)放在同一行上爱态。我上面展示的元語法實(shí)際上并沒有解析自己，因?yàn)橛羞@樣的情況：

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

這是因?yàn)闃?biāo)識符生成器（tokenizer）在第一行的末尾產(chǎn)生了一個 NEWLINE 標(biāo)識符境钟，此時元解析器會認(rèn)為這是該規(guī)則的結(jié)束锦担。此外，NEWLINE 之后會出現(xiàn)一個 INDENT 標(biāo)識符慨削，因?yàn)橄乱恍惺强s進(jìn)的洞渔。在下一個規(guī)則開始之前，還會有一個 DEDENT 標(biāo)識符缚态。

下面是解決辦法磁椒。為了理解 tokenize 模塊的行為，我們可以將 tokenize 模塊作為腳本運(yùn)行玫芦，并為其提供一些文本浆熔，以此來查看對于縮進(jìn)塊，會生成什么樣的標(biāo)識符序列：

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

我們發(fā)現(xiàn)它會產(chǎn)生以下的標(biāo)識符序列（我已經(jīng)簡化了上面運(yùn)行的輸出）：

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

這意味著一組縮進(jìn)的代碼行會被 INDENT 和 DEDENT 標(biāo)記符所描繪∏欧現(xiàn)在医增，我們可以重新編寫元語法規(guī)則的 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 }

（我跨行地拆分了動作，以便它們適應(yīng) Medium 網(wǎng)站的窄頁——這是可行的老虫，因?yàn)闃?biāo)識符生成器會忽略已配對的括號內(nèi)的換行符叶骨。）

這樣做的好處是我們甚至不需要更改生成器：這種改進(jìn)的元語法生成的數(shù)據(jù)結(jié)構(gòu)跟以前相同。同樣注意 rule 的第三個備選項(xiàng)祈匙，對此讓我們寫：

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

有些人會覺得這比我之前展示的版本更干凈忽刽。很容易允許兩種形式共存，所以我們不必爭論風(fēng)格夺欲。

在下一篇文章中跪帝，我將展示如何實(shí)現(xiàn)各種 PEG 功能，如可選條目洁闰、重復(fù)和前瞻歉甚。（說句公道話，我本打算把那放在這篇里扑眉，但是這篇已寫太長了纸泄，所以我要把它分成兩部分。）

本文內(nèi)容與示例代碼的授權(quán)協(xié)議：CC BY-NC-SA 4.0

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