練習(xí) 33：解析器

原文：Exercise 33: Parsers

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

想象一下，你將獲得一個(gè)巨大的數(shù)字列表，你必須將其輸入到電子表格中崖疤。一開(kāi)始用爪，這個(gè)巨大的列表只是一個(gè)空格分隔的原始數(shù)據(jù)流。你的大腦會(huì)自動(dòng)在空格處拆分?jǐn)?shù)字流并創(chuàng)建數(shù)字。你的大腦像掃描器一樣哑诊。然后撒璧，你將獲取每個(gè)數(shù)字透葛，并將其輸入到具有含義的行和列中。你的大腦像一個(gè)解析器卿樱，通過(guò)獲取扁平的數(shù)字（記號(hào)）僚害，并將它們變成一個(gè)更有意義的行和列的二維網(wǎng)格。你遵循的規(guī)則繁调，什么數(shù)字進(jìn)入什么行什么列萨蚕，是你的“語(yǔ)法”靶草，解析器的工作就是像你對(duì)于電子表格那樣使用語(yǔ)法。

我們?cè)賮?lái)看一下練習(xí) 32 中的微型 Python 代碼岳遥，再?gòu)娜齻€(gè)不同的角度討論解析器：

def hello(x, y):
    print(x + y)

hello(10, 20)

當(dāng)你查看這個(gè)代碼時(shí)奕翔，你看到什么？我看到一棵樹浩蓉，類似于我們之前創(chuàng)建的BSTree或TSTree派继。你看到樹了嗎？我們從這個(gè)文件的最上方開(kāi)始捻艳，學(xué)習(xí)如何將字符轉(zhuǎn)換為樹驾窟。

首先，當(dāng)我們加載一個(gè).py文件時(shí)认轨，它只是一個(gè)“字符”流 - 實(shí)際上是字節(jié)绅络，但 Python 使用Unicode，所以必須處理字符好渠。這些字符在一行中昨稼，毫無(wú)結(jié)構(gòu)，掃描器的任務(wù)是增加第一層次的意義拳锚。掃描器通過(guò)使用正則表達(dá)式假栓，從字符串流中提取意義，創(chuàng)建記號(hào)列表霍掺。我們已經(jīng)將一個(gè)字符列表轉(zhuǎn)換為一個(gè)記號(hào)列表匾荆，但看看def hello(x,y):函數(shù)。這是一個(gè)函數(shù)杆烁，里面有代碼塊牙丽。這意味著某種形式的“包含”或“東西里面的東西”的結(jié)構(gòu)。

一個(gè)很容易表示包含的方式是用一棵樹兔魂。我們可以使用表格烤芦，像你的電子表格一樣，但它并不像樹那么容易析校。接下來(lái)看看hello(x, y)部分构罗。我們有一個(gè)NAME(hello)記號(hào)，但是我們要抓取(...)部分的內(nèi)容智玻，并且知道它在括號(hào)內(nèi)遂唧。再次，我們可以使用一個(gè)樹吊奢，我們將(...)部分中的x, y部分“嵌套” 為樹的子節(jié)點(diǎn)或分支盖彭。最終，我們就擁有了一棵樹，從這個(gè) Python 代碼的根開(kāi)始召边，并且每個(gè)代碼塊铺呵，print，函數(shù)定義和函數(shù)調(diào)用都是根的分支掌实，它們也有子分支陪蜻，以此類推。

為什么我們這樣做贱鼻？我們需要基于其語(yǔ)法宴卖，知道 Python 代碼的結(jié)構(gòu)，以便我們稍后分析邻悬。如果我們不將記號(hào)的線性列表轉(zhuǎn)換成樹結(jié)構(gòu)症昏，那么我們不知道函數(shù)，代碼塊父丰，分支或表達(dá)式的邊界在哪里肝谭。我們必須以“直線”方式在飛行中確定邊界，這不容易使其可靠蛾扇。很多早期的糟糕語(yǔ)言是直線語(yǔ)言攘烛，我們現(xiàn)在知道了他們不必須是這樣。我們可以使用解析器構(gòu)建樹結(jié)構(gòu)镀首。

解析器的任務(wù)是從掃描器中獲取記號(hào)列表坟漱，并將其翻譯成更有意義的語(yǔ)法樹泛释。你可以認(rèn)為解析器是阵面，對(duì)記號(hào)流應(yīng)用另一個(gè)正則表達(dá)式。掃描器的正則表達(dá)式將大量字符放入記號(hào)中侍匙。解析器的“正則表達(dá)式”將這些記號(hào)放在盒子里面成翩，它里面有盒子觅捆，以此類推，直到記號(hào)不再是線性的麻敌。

解析器也為這些盒子添加了含義栅炒。解析器將簡(jiǎn)單地刪除()括號(hào)記號(hào)，并為可能的Function類創(chuàng)建一個(gè)特殊的parameters列表术羔。它會(huì)刪除冒號(hào)职辅，無(wú)用的空格，逗號(hào)聂示，任何沒(méi)有真正意義的記號(hào)，并將其轉(zhuǎn)換為更易于處理的嵌套結(jié)構(gòu)簇秒。最后的結(jié)果可能看起來(lái)像鱼喉，上面的示例代碼的偽造樹：

* root
  * Function
    - name = hello
    - parameters = x, y
    - code:
      * Call
        - name = print
        - parameters =
            * Expression
              - Add
                - a = x
                - b = y
  * Call
    - name = hello
    - parameters = 10, 20

遞歸下降解析

有幾種已建立的方法，可以為這種語(yǔ)法創(chuàng)建解析器，但最簡(jiǎn)單的方法稱為遞歸下降解析器（RDP）扛禽。我實(shí)際上在我《笨辦法學(xué) Python》練習(xí) 49 中講解了這個(gè)話題锋边。你創(chuàng)建了一個(gè)簡(jiǎn)單的 RDP 解析器來(lái)處理你的小游戲語(yǔ)言，你甚至不了解它编曼。在本練習(xí)中豆巨，我將對(duì)如何編寫 RDP 解析器進(jìn)行更正式的描述，然后讓你使用我們上面的 Python 小代碼片段來(lái)嘗試它掐场。

RDP 使用多個(gè)相互遞歸的函數(shù)調(diào)用往扔，它實(shí)現(xiàn)了給定語(yǔ)法的樹形結(jié)構(gòu)。RDP 解析器的代碼看起來(lái)像你正在處理的實(shí)際語(yǔ)法熊户，只要遵循一些規(guī)則萍膛，它們就很容易編寫。RDP 解析器的兩個(gè)缺點(diǎn)是：它們可能不是非常有效嚷堡，并且通常需要手動(dòng)編寫它們蝗罗，因此它們的錯(cuò)誤比生成的解析器更多。對(duì)于 RDP 解析器可以解析的東西蝌戒，還有一些理論上的限制串塑，但是由于你手動(dòng)編寫它們，你通潮惫叮可以解決很多限制桩匪。

為了編寫一個(gè) RDP 解析器，你需要使用三個(gè)主要操作粹淋，來(lái)處理掃描器的記號(hào)：

peek

如果下一個(gè)記號(hào)能夠匹配吸祟，返回它，但是不從流中移除桃移。

match

匹配下一個(gè)記號(hào)屋匕，并且從流中移除。

skip

由于不需要下個(gè)記號(hào)借杰，跳過(guò)它过吻，將其從流中移除。

你會(huì)注意到蔗衡，這些是我在練習(xí) 33 中讓你為掃描器創(chuàng)建的三個(gè)操作纤虽，這就是為什么。你需要他們來(lái)實(shí)現(xiàn)一個(gè) RDP 解析器绞惦。

你可以使用這三個(gè)函數(shù)來(lái)編寫語(yǔ)法解析函數(shù)逼纸，從掃描器中獲取記號(hào)。這個(gè)練習(xí)的一個(gè)簡(jiǎn)短的例子是济蝉，解析這個(gè)簡(jiǎn)單的函數(shù)：

def function_definition(tokens):
    skip(tokens) # discard def
    name = match(tokens, 'NAME')
    match(tokens, 'LPAREN')
    params = parameters(tokens)
    match(tokens, 'RPAREN')
    match(tokens, 'COLON')
    return {'type': 'FUNCDEF', 'name': name, 'params': params}

你可以看到我只是接受記號(hào)并使用match和skip處理它們杰刽。你還會(huì)注意到我有一個(gè)parameters函數(shù)菠发，它是“遞歸下降解析器”的“遞歸”部分。當(dāng)它需要為函數(shù)解析參數(shù)時(shí)贺嫂，function_definition會(huì)調(diào)用parameters滓鸠。

BNF 語(yǔ)法

嘗試從頭開(kāi)始編寫一個(gè) RDP 解析器是沒(méi)有某種形式的語(yǔ)法規(guī)范的，有點(diǎn)棘手第喳。你還記得當(dāng)我要求你將單個(gè)正則表達(dá)式轉(zhuǎn)換成 FSM 嗎糜俗？這很難嗎？它需要更多的代碼曲饱，不只是正則表達(dá)式中的幾個(gè)字符悠抹。當(dāng)你為這個(gè)練習(xí)編寫 RDP 解析器時(shí)，你將會(huì)做類似的事情渔工，因此它有助于使用一種語(yǔ)言锌钮，它是“語(yǔ)法的正則表達(dá)式”。

最常見(jiàn)的“語(yǔ)法的正則表達(dá)式”被稱為 Backus–Naur Form（BNF）引矩，以創(chuàng)作者 John Backus 和 Peter Naur 命名梁丘。BNF 描述了所需的記號(hào)，以及這些記號(hào)如何重復(fù)來(lái)形成語(yǔ)言的語(yǔ)法旺韭。BNF 還使用與正則表達(dá)式相同的符號(hào)氛谜，所以*，+和?有相似的含義区端。

對(duì)于這個(gè)練習(xí)值漫，我將使用 https://tools.ietf.org/html/rfc5234 上面的 IETF 增強(qiáng) BNF 語(yǔ)法，來(lái)規(guī)定上面的微型 Python 代碼段的語(yǔ)法织盼。ABNF 運(yùn)算符大部分與正則表達(dá)式相同杨何，只是由于某種奇怪的原因，它們?cè)谝貜?fù)的東西之前放置重復(fù)符號(hào)沥邻。除此之外危虱，請(qǐng)閱讀規(guī)范，并嘗試弄清楚下面的意思：

root = *(funccal / funcdef)
funcdef = DEF name LPAREN params RPAREN COLON body
funccall = name LPAREN params RPAREN
params = expression *(COMMA expression)
expression = name / plus / integer
plus = expression PLUS expression
PLUS = "+"
LPAREN = "("
RPAREN = ")"
COLON = ":"
COMMA = ","
DEF = "def"

讓我們僅僅查看funcdef那一行唐全，并將其與function_definition Python 代碼比較埃跷，匹配每一個(gè)部分：

funcdef =

我們使用def function_definition(tokens)來(lái)復(fù)制，并且它是我們的語(yǔ)法的這個(gè)部分的開(kāi)始邮利。

DEF

它在語(yǔ)法中規(guī)定了DEF = "def"弥雹，并且在 Python 代碼中，我們使用skip(tokens)跳過(guò)了它延届。

name

我需要它剪勿，所以我使用name = match(tokens, 'NAME')匹配它。我使用 CAPITALS 的約定方庭，在 BNF 中表示我會(huì)跳過(guò)的東西窗宦。

LPAREN

我假設(shè)我收到了一個(gè)def赦颇，但是現(xiàn)在我打算確保有一個(gè)(，所以我要匹配它赴涵。但是我使用match(tokens, 'LPAREN')來(lái)忽略結(jié)果。它就像“需要但是忽略”订讼。

params

在 BNF 中我將params定義為了新的“語(yǔ)法產(chǎn)生式”髓窜，或者“語(yǔ)法規(guī)則”。意思是在我的 Python 代碼中欺殿，我需要一個(gè)新的函數(shù)寄纵。這個(gè)函數(shù)中，我可以使用params = parameters(tokens)來(lái)調(diào)用那個(gè)函數(shù)脖苏。之后我定義了parameters函數(shù)來(lái)為函數(shù)處理逗號(hào)分隔的參數(shù)程拭。

RPAREN

同樣我需要但是去掉了它，使用match(tokens, 'RPAREN')棍潘。

COLON

同樣恃鞋，我去掉了匹配match(tokens, 'COLON')。

body

我這里實(shí)際上跳過(guò)了函數(shù)體亦歉，因?yàn)?Python 的縮進(jìn)語(yǔ)法對(duì)于這個(gè)例子太難了恤浪。你不需要在練習(xí)中處理這個(gè)例子，除非你喜歡它肴楷。

這基本上是水由，你如何讀取 ABNF 規(guī)范，并將其系統(tǒng)地轉(zhuǎn)換為代碼赛蔫。你從根開(kāi)始砂客，將每個(gè)語(yǔ)法產(chǎn)生式實(shí)現(xiàn)為一個(gè)函數(shù)，并讓掃描器處理簡(jiǎn)單的記號(hào)（我用CAPITAL（大寫）字母表示）呵恢。

簡(jiǎn)單的示例黑魔法解析器

這是我快速 Hack 出來(lái)的 RDP 解析器鞠值，你可以使用它，作為你的更正式和簡(jiǎn)潔的解析器的基礎(chǔ)瑰剃。

from scanner import *
from pprint import pprint

def root(tokens):
    """root = *(funccal / funcdef)"""
    first = peek(tokens)

    if first == 'DEF':
        return function_definition(tokens)
    elif first == 'NAME':
        name = match(tokens, 'NAME')
        second = peek(tokens)

        if second == 'LPAREN':
            return function_call(tokens, name)
        else:
            assert False, "Not a FUNCDEF or FUNCCALL"

def function_definition(tokens):
    """
    funcdef = DEF name LPAREN params RPAREN COLON body
    I ignore body for this example 'cause that's hard.
    I mean, so you can learn how to do it.
    """
    skip(tokens) # discard def
    name = match(tokens, 'NAME')
    match(tokens, 'LPAREN')
    params = parameters(tokens)
    match(tokens, 'RPAREN')
    match(tokens, 'COLON')
    return {'type': 'FUNCDEF', 'name': name, 'params': params}

def parameters(tokens):
    """params = expression *(COMMA expression)"""
    params = []
    start = peek(tokens)
    while start != 'RPAREN':
        params.append(expression(tokens))
        start = peek(tokens)
        if start != 'RPAREN':
            assert match(tokens, 'COMMA')
    return params

def function_call(tokens, name):
    """funccall = name LPAREN params RPAREN"""
    match(tokens, 'LPAREN')
    params = parameters(tokens)
    match(tokens, 'RPAREN')
    return {'type': 'FUNCCALL', 'name': name, 'params': params}

def expression(tokens):
    """expression = name / plus / integer"""
    start = peek(tokens)

    if start == 'NAME':
        name = match(tokens, 'NAME')
        if peek(tokens) == 'PLUS':
            return plus(tokens, name)
        else:
            return name
    elif start == 'INTEGER':
        number = match(tokens, 'INTEGER')
        if peek(tokens) == 'PLUS':
            return plus(tokens, number)
        else:
            return number
    else:
        assert False, "Syntax error %r" % start

def plus(tokens, left):
    """plus = expression PLUS expression"""
    match(tokens, 'PLUS')
    right = expression(tokens)
    return {'type': 'PLUS', 'left': left, 'right': right}


def main(tokens):
    results = []
    while tokens:
        results.append(root(tokens))
    return results

parsed = main(scan(code))
pprint(parsed)

你會(huì)注意到齿诉，我正在使用我寫的scanner模塊，擁有我的match晌姚，peek粤剧，skip和scan函數(shù)。我使用from scanner import *挥唠，僅使這個(gè)例子更容易理解抵恋。你應(yīng)該使用你的Scanner類。

你會(huì)注意到宝磨，我把這個(gè)小解析器的 ABNF 放在每個(gè)函數(shù)的文檔注釋中弧关。這有助于我編寫每個(gè)解析器代碼盅安，稍后可以用于錯(cuò)誤報(bào)告。在嘗試挑戰(zhàn)練習(xí)之前世囊，你應(yīng)該研究此解析器别瞭，甚至可能作為“代碼大師副本”。

挑戰(zhàn)練習(xí)

你的下一個(gè)挑戰(zhàn)是株憾，將你的 Scanner類與新編寫的Parser類組合在一起蝙寨，你可以派生并重新實(shí)現(xiàn)使我這里的簡(jiǎn)單的解析器。你的基礎(chǔ)Parser類應(yīng)該能夠：

• 接受一個(gè)Scanner對(duì)象并執(zhí)行自身嗤瞎。你可以假設(shè)任何默認(rèn)函數(shù)是語(yǔ)法的起始墙歪。
• 擁有錯(cuò)誤處理代碼，比我簡(jiǎn)單的assert用法更好贝奇。

你應(yīng)該實(shí)現(xiàn)PunyPythonPython虹菲，它可以解析這個(gè)微小的 Python 語(yǔ)言，并執(zhí)行以下操作：

• 不是僅僅產(chǎn)生dicts的列表掉瞳，你應(yīng)該為每個(gè)語(yǔ)法生產(chǎn)式的結(jié)果創(chuàng)建類毕源。這些類之后成為列表中的對(duì)象。
• 這些類只需要存儲(chǔ)被解析的記號(hào)菠赚，但是要準(zhǔn)備做更多事情脑豹。
• 你只需要解析這個(gè)微小的語(yǔ)言，但你應(yīng)該嘗試解決“Python 縮進(jìn)”問(wèn)題衡查。你可能需要秀阿貴掃描器瘩欺，使其更智能，才能在行的開(kāi)頭匹配INDENT空白字符拌牲，并在其他位置忽略它俱饿。你還需要跟蹤如何多少縮進(jìn)了多少，同時(shí)也記錄零縮進(jìn)塌忽，所以你可以“壓縮”代碼塊拍埠。

一個(gè)泛用的測(cè)試套件涉及到，將這個(gè)微小的 python 的更多樣本交給解析器土居，但現(xiàn)在只需要得到一個(gè)小文件來(lái)解析枣购。嘗試在測(cè)試中獲得良好的覆蓋率，并盡可能多地發(fā)現(xiàn)錯(cuò)誤擦耀。

研究性學(xué)習(xí)

這個(gè)練習(xí)相當(dāng)龐大棉圈，所以只需要完成【祢眩花點(diǎn)時(shí)間分瘾，一次做一點(diǎn)點(diǎn)。我強(qiáng)烈建議學(xué)習(xí)我這里的小型樣本吁系，直到你完全弄清楚德召，并打印正在處理的關(guān)鍵位置的記號(hào)白魂。

深入學(xué)習(xí)

查看 David Beazley 的 SLY 解析器生成器，以便讓你的計(jì)算機(jī)為你生成你的解析器和掃描器（也稱為分詞器）上岗。隨意嘗試用 SLY 重復(fù)此練習(xí)來(lái)進(jìn)行比較福荸。