練習(xí) 34：分析器

原文：Exercise 34: Analyzers

譯者：飛龍

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

自豪地采用谷歌翻譯

你現(xiàn)在有了一個(gè)解析器，它應(yīng)該生成一個(gè)語法產(chǎn)生式對(duì)象樹厦画。我會(huì)將其稱為“解析樹”井仰，這意味著你可以從“解析樹的頂部開始进泼，然后“遍歷”它监憎，直到你訪問每個(gè)節(jié)點(diǎn)來分析整個(gè)程序渔期。當(dāng)你了解BSTree和TSTree數(shù)據(jù)結(jié)構(gòu)時(shí)镊叁，你已經(jīng)做了這樣的事情柠辞。你從頂部開始訪問了每個(gè)節(jié)點(diǎn)团秽，并且你訪問的順序（深度優(yōu)先，廣度優(yōu)先叭首，順序遍歷等）確定了節(jié)點(diǎn)的處理方式习勤。你的解析樹具有相同的功能，編寫微型 Python 解釋器的下一步是遍歷樹并分析它焙格。

分析器的任務(wù)是图毕，在你的語法中找到語義錯(cuò)誤，并修復(fù)或添加下一階段需要的信息眷唉。語義錯(cuò)誤是錯(cuò)誤予颤，雖然語法正確，但并不適合 Python 程序冬阳。這可以是一個(gè)尚未定義的遍歷蛤虐，也可以是不符合邏輯的代碼，它根本沒有意義肝陪。一些語言語法是如此松散笆焰，分析器必須做更多的工作來修復(fù)解析樹。其他語言很容易解析和處理见坑，甚至不需要分析器的步驟嚷掠。

為了編寫分析器，你需要一種方法來訪問解析樹中的每個(gè)節(jié)點(diǎn)荞驴，分析錯(cuò)誤不皆，并修復(fù)任何缺少的信息。有三種通用方法可以用于實(shí)現(xiàn)它：

• 你創(chuàng)建一個(gè)分析器熊楼，它知道如何更新每個(gè)語法產(chǎn)生式霹娄。它將以和解析器相似的方式遍歷解析樹，對(duì)每種生產(chǎn)式類型都擁有一個(gè)函數(shù)鲫骗，但他的任務(wù)是更改犬耻，更新和檢查產(chǎn)生式。
• 你改變你的語法產(chǎn)生式执泰，讓他們知道如何分析自己的狀態(tài)枕磁。那么你的分析器就僅僅是一個(gè)引擎，它遍歷解析樹术吝，調(diào)用每個(gè)產(chǎn)生式的analyze()方法计济。使用這種風(fēng)格茸苇，你將需要一些狀態(tài)，它們會(huì)傳遞給每個(gè)語法產(chǎn)生式類沦寂，這個(gè)類應(yīng)該是第三個(gè)類学密。
• 你創(chuàng)建一組單獨(dú)的類來實(shí)現(xiàn)最終分析后的樹，你可以將其傳遞給解釋器传藏。通過許多方式腻暮，你將使用一組新的類來映射語法分析器的語法產(chǎn)生式，這些新的類接受全局狀態(tài)毯侦，語法產(chǎn)生式哭靖，并配置其__init__，使其為分析后的結(jié)果叫惊。

我建議你現(xiàn)在使用 #2 或 #3 來完成挑戰(zhàn)練習(xí)款青。

訪客模式

“訪問者模式”是面向?qū)ο笳Z言中非常常見的技術(shù)做修，其中你可以創(chuàng)建一些類霍狰，它們知道被“訪問”時(shí)應(yīng)該做什么。這可以讓你將處理某個(gè)類的代碼集成到這個(gè)類饰及。這樣做的優(yōu)點(diǎn)是蔗坯，你不需要大型的if語句來檢查類上的類型，來了解該做什么燎含。相反宾濒，你只需創(chuàng)建一個(gè)類似于這個(gè)的類：

class Foo(object):
    def visit(self, data):
        # do stuff to self for foo

一旦你擁有了這個(gè)類（visit可以叫任何東西），你可以遍歷列表來調(diào)用它屏箍。

for action in list_of_actions:
    action.visit(data)

你將使用這種模式用于 #2 或 #3 風(fēng)格的分析器绘梦；唯一的區(qū)別是：

• 如果你決定背零，你的語法產(chǎn)生式也將是分析結(jié)果握截，那么你的analyze()函數(shù)（也就是我們的visit()）只會(huì)將該數(shù)據(jù)存儲(chǔ)在產(chǎn)生式類，或者在提供給它的狀態(tài)中庐船。
• 如果你決定颖御，你的語法產(chǎn)生式將為解釋器生成另一組類（請(qǐng)參閱練習(xí) 35）榄棵，那么每次analyze的調(diào)用都將返回一個(gè)新對(duì)象，該對(duì)象將放入列表中以供以后使用潘拱，或?qū)⑵渥鳛樽訕涓郊拥疆?dāng)前對(duì)象疹鳄。

我將介紹第一種情況，其中你的語法產(chǎn)生式也是你的分析器結(jié)果芦岂。這適用于我們簡單的微型 Python 腳本瘪弓，你應(yīng)該遵循這種風(fēng)格。如果你想嘗試其他的設(shè)計(jì)禽最，那么你可以之后嘗試杠茬。

簡短的微型 Python 分析器

警告

如果你想自己嘗試月褥，為你的語法產(chǎn)生式嘗試實(shí)現(xiàn)訪客模式，那么你應(yīng)該停在這里瓢喉。我將給出一個(gè)相當(dāng)完整但簡單的例子宁赤，它充滿了障礙。

訪客模式背后的概念似乎是奇怪的栓票，但它是完全有意義的决左。每個(gè)語法產(chǎn)生式都知道在不同階段應(yīng)該做什么，所以你可以把這個(gè)階段代碼放在需要的數(shù)據(jù)附近走贪。為了演示這個(gè)佛猛，我寫了一個(gè)小型的偽造的PunyPyAnalyzer，它僅僅使用訪客模式打印出解析坠狡。我只完成一個(gè)語法產(chǎn)生式的樣例继找，所以你可以理解這是如何完成的。我不想給你太多的線索逃沿。

我做的第一件事是婴渡，定義一個(gè)Production類，我的所有語法產(chǎn)生式都將繼承它凯亮。

class Production(object):
    def analyze(self, world):
        """Implement your analyzer here."""

它擁有我的初始的analyze()方法边臼，并接受我們隨后使用的PunyPyWorld。第一個(gè)語法產(chǎn)生式的示例使FuncCall產(chǎn)生式：

class FuncCall(Production):

    def __init__(self, name, params):
        self.name = name
        self.params = params

    def analyze(self, world):
        print("> FuncCall: ", self.name)
        self.params.analyze(world)

函數(shù)調(diào)用有名稱和params假消，它是一個(gè)Parameters產(chǎn)生式類柠并，用于函數(shù)調(diào)用的參數(shù)「晦郑看看analyze()方法臼予，你會(huì)看到第一個(gè)訪客函數(shù)。當(dāng)你訪問PunyPyAnalyzer時(shí)啃沪，你將看到如何運(yùn)行粘拾，但是請(qǐng)注意，此函數(shù)之后在每個(gè)函數(shù)的參數(shù)上調(diào)用param.analyze(world)：

class Parameters(Production):

    def __init__(self, expressions):
        self.expressions = expressions

    def analyze(self, world):
        print(">> Parameters: ")
        for expr in self.expressions:
            expr.analyze(world)

這就產(chǎn)生了Parameters類谅阿，它包含每個(gè)表達(dá)式半哟，它們組成函數(shù)的參數(shù)。Parameters.analyze僅僅遍歷它的表達(dá)式列表签餐，其中我們擁有兩個(gè)：

class Expr(Production): pass

class IntExpr(Expr):
    def __init__(self, integer):
        self.integer = integer

    def analyze(self, world):
        print(">>>> IntExpr: ", self.integer)

class AddExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def analyze(self, world):
        print(">>> AddExpr: ")
        self.left.analyze(world)
        self.right.analyze(world)

在這個(gè)例子中寓涨，我只添加了兩個(gè)數(shù)字，但是我創(chuàng)建一個(gè)基本的Expr類氯檐，然后創(chuàng)建IntExpr和AddExpr類戒良。每個(gè)都僅僅擁有analyze()方法，打印出其內(nèi)容冠摄。

因此糯崎，我們有用于分析樹的類几缭，我們可以做一些分析。我們需要的第一件事是一個(gè)世界沃呢，它可以跟蹤變量定義年栓、函數(shù)、以及我們的Production.analyze()方法所需的其他東西薄霜。

class PunyPyWorld(object):

    def __init__(self, variables):
        self.variables = variables
        self.functions = {}

當(dāng)調(diào)用任何Production.analyze()方法時(shí)某抓，PunyPyWorld對(duì)象被傳遞給它，因此analyze()方法知道世界的狀態(tài)惰瓜。它可以更新變量否副，尋找函數(shù)，并在世界中執(zhí)行任何所需的事情崎坊。

然后我們需要一個(gè)PunyPyAnalyzer备禀，它可以接受解析樹和世界，并使所有的語法產(chǎn)生式運(yùn)行：

class PunyPyAnalyzer(object):
    def __init__(self, parse_tree, world):
        self.parse_tree = parse_tree
        self.world = world

    def analyze(self):
        for node in self.parse_tree:
            node.analyze(self.world)

函數(shù)的簡單調(diào)用hello(10 + 20)的配置相當(dāng)簡單奈揍。

variables = {}
world = PunyPyWorld(variables)
# simulate hello(10 + 20)
script = [FuncCall("hello",
            Parameters(
                [AddExpr(IntExpr(10), IntExpr(20))])
            )]
analyzer = PunyPyAnalyzer(script, world)
analyzer.analyze()

要確保你理解了我構(gòu)造script的方式曲尸。注意到第一個(gè)參數(shù)是一個(gè)列表了嘛？

解析器與分析器

在這個(gè)例子中打月，我假設(shè)PunyPyParser已將NUMBER記號(hào)轉(zhuǎn)換為整數(shù)队腐。在其他語言中蚕捉，你可能只擁有記號(hào)奏篙，并讓PunyPyAnalyzer進(jìn)行轉(zhuǎn)換。這一切都取決于迫淹，你想讓錯(cuò)誤發(fā)生在哪里秘通，以及哪里可以做最有用的分析。如果你將工作放在解析器中敛熬，那么你可以馬上給出格式化方面的早期錯(cuò)誤肺稀。如果將其放在分析器中，那么你可以給出錯(cuò)誤应民，使用整個(gè)解析文件來有所幫助话原。

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

所有這些analyze()方法的要點(diǎn)不僅僅是打印出來，而是改變每個(gè)Production子類的內(nèi)部狀態(tài)诲锹，以便解釋器可以像腳本一樣運(yùn)行它繁仁。你在這個(gè)練習(xí)中的任務(wù)是，接受你的語法產(chǎn)生式類（可能與我的不同）并進(jìn)行分析归园。

隨意借鑒我的出發(fā)點(diǎn)黄虱。如果需要，可以使用我的分析器和我的世界庸诱，但是你應(yīng)該嘗試首先編寫自己的分析器捻浦。你還應(yīng)該將練習(xí) 33 中的產(chǎn)生式類與我的比較晤揣。你的更好嗎？它們能支持這種設(shè)計(jì)嗎朱灿？如果他們不能則改變它們昧识。

你的分析器需要做一些事情才能使解釋器正常工作：

• 跟蹤變量定義。在一個(gè)實(shí)際的語言中盗扒，這將需要一些非常復(fù)雜的嵌套表滞诺，但是對(duì)于微型 Python 來說，只需假設(shè)有一個(gè)巨大的表（TSTree或dict）环疼，所有變量都在這里习霹。這意味著hello(x, y)函數(shù)的x和y參數(shù)實(shí)際上是全局變量。
• 跟蹤函數(shù)的位置炫隶，以便以后運(yùn)行它們淋叶。我們的微型 Python 只有簡單的函數(shù)，但是當(dāng)Interpreter運(yùn)行時(shí)伪阶，它需要“跳轉(zhuǎn)”到并運(yùn)行它們煞檩。最好的辦法保留它們，便于之后使用栅贴。
• 檢查你可以想到的任何錯(cuò)誤斟湃，例如使用中缺少的變量。這是棘手的檐薯，因?yàn)?Python 這樣的語言凝赛，在解釋器階段中進(jìn)行更多的錯(cuò)誤檢查。你應(yīng)該決定在分析過程中坛缕，可能出現(xiàn)哪些錯(cuò)誤并實(shí)現(xiàn)它們墓猎。例如，如果我嘗試使用未定義的變量赚楚，會(huì)發(fā)生什么毙沾？
• 如果你正確地實(shí)現(xiàn)了 Python INDENT語法，那么你的FuncCall產(chǎn)生式應(yīng)該有額外的代碼宠页。解釋器將需要它來運(yùn)行它左胞，所以確保有一個(gè)實(shí)現(xiàn)它的方式。

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

• 這個(gè)練習(xí)已經(jīng)很難了举户，但是如何創(chuàng)建一個(gè)更好的方式烤宙，來存儲(chǔ)變量，至少實(shí)現(xiàn)一個(gè)額外的作用域?qū)蛹?jí)敛摘？記得“作用域”的概念是门烂，hello(x, y)中的x, y不影響hello函數(shù)之外的你定義x和y。
• 在Scanner，Parser和Analyzer中實(shí)現(xiàn)賦值屯远。這意味著我應(yīng)該可以執(zhí)行x = 10 + 14蔓姚，你可以處理它。

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

研究“基于表達(dá)式”和“基于語句”的編程語言之間的區(qū)別慨丐。較短版本是一些只有表達(dá)式的語言坡脐，所以任何東西都有與之相關(guān)的某種（返回）值。其他語言的表達(dá)式擁有值房揭，語句沒有备闲，因此把它們賦給變量會(huì)失敗。Python 是哪種語言捅暴？