【编译原理】构建一个简单的解释器（Let’s Build A Simple Interpreter. Part 7.）（笔记）解释器 interpreter 解析器 parser 抽象语法树AST
【編譯原理】讓我們來構(gòu)建一個(gè)簡單的解釋器（Let’s Build A Simple Interpreter. Part 7.）
文章目錄
- python代碼
- 插——后序遍歷
- C語言代碼（有錯(cuò)誤)
- C語言代碼（修改優(yōu)化后）
- 總結(jié)
正如我上次向您保證的那樣，今天我將討論我們將在本系列的其余部分中使用的中心數(shù)據(jù)結(jié)構(gòu)之一，所以系好安全帶，讓我們開始吧。
到目前為止，我們將解釋器（interpreter ）和解析器（parser ）代碼混合在一起，一旦解析器識(shí)別出某種語言結(jié)構(gòu)，如加法、減法、乘法或除法，解釋器就會(huì)對(duì)表達(dá)式求值。這種解釋器被稱為語法導(dǎo)向解釋器。它們通常對(duì)輸入進(jìn)行一次傳遞，適用于基本語言應(yīng)用程序。為了分析更復(fù)雜的 Pascal 編程語言結(jié)構(gòu)，我們需要構(gòu)建一個(gè)中間表示( IR )。我們的解析器將負(fù)責(zé)構(gòu)建一個(gè) IR，我們的解釋器將使用它來解釋表示為IR的輸入。
事實(shí)證明，樹是非常適合IR 的數(shù)據(jù)結(jié)構(gòu)。
讓我們快速討論一下樹術(shù)語。
- 一個(gè)樹是一種數(shù)據(jù)結(jié)構(gòu)，由組織成一個(gè)層次中的一個(gè)或多個(gè)節(jié)點(diǎn)。
- 這棵樹有一個(gè)根，它是頂部節(jié)點(diǎn)。
- 除了根節(jié)點(diǎn)之外的所有節(jié)點(diǎn)都有一個(gè)唯一的parent。
- 下圖中標(biāo)有*的節(jié)點(diǎn)是父節(jié)點(diǎn)。標(biāo)記為2和7 的節(jié)點(diǎn)是它的子節(jié)點(diǎn)；孩子們是從左到右排列的。
沒有子 節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。 - 具有一個(gè)或多個(gè)子節(jié)點(diǎn)且不是根的 節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn)。
- 子樹也可以是完整的子樹。在下圖中，+節(jié)點(diǎn)的左子節(jié)點(diǎn)（標(biāo)記為*） 是一個(gè)完整的子樹，帶有自己的子節(jié)點(diǎn)。
- 在計(jì)算機(jī)科學(xué)中，我們從頂部的根節(jié)點(diǎn)和向下生長的分支開始倒置繪制樹。
- 這是表達(dá)式 2 * 7 + 3 的樹，并附有說明：
我們將在整個(gè)系列中使用的IR稱為抽象語法樹( AST )。但在我們深入研究 AST 之前，讓我們先簡單地談?wù)劷馕鰳洹１M管我們不會(huì)在解釋器和編譯器中使用解析樹，但它們可以通過可視化解析器的執(zhí)行跟蹤來幫助您了解解析器如何解釋輸入。我們還將它們與 AST 進(jìn)行比較，以了解為什么 AST 比解析樹更適合用于中間表示。
那么，什么是解析樹？一個(gè)解析樹（有時(shí)稱為具體語法樹）是表示根據(jù)我們的語法定義語言結(jié)構(gòu)的句法結(jié)構(gòu)樹。它基本上顯示了您的解析器如何識(shí)別語言結(jié)構(gòu)，或者換句話說，它顯示了您的語法的起始符號(hào)如何派生出編程語言中的某個(gè)字符串。
解析器的調(diào)用堆棧隱式地表示一個(gè)解析樹，它會(huì)在您的解析器嘗試識(shí)別特定語言結(jié)構(gòu)時(shí)自動(dòng)構(gòu)建在內(nèi)存中。
讓我們看一下表達(dá)式 2 * 7 + 3 的解析樹：
在上圖中，您可以看到：（expr加減 -> term乘除 -> factor數(shù)）
- 解析樹記錄了解析器用于識(shí)別輸入的一系列規(guī)則。
- 解析樹的根用文法開??始符號(hào)標(biāo)記。
- 每個(gè)內(nèi)部節(jié)點(diǎn)代表一個(gè)非終結(jié)符，即它代表一個(gè)文法規(guī)則應(yīng)用，如我們的例子中的expr、term或factor。
- 每個(gè)葉節(jié)點(diǎn)代表一個(gè)標(biāo)記。
正如我已經(jīng)提到的，我們不會(huì)手動(dòng)構(gòu)建解析器樹并將它們用于我們的解釋器，但是解析樹可以通過可視化解析器調(diào)用序列來幫助您理解解析器如何解釋輸入。
您可以通過試用一個(gè)名為genptdot.py的小實(shí)用程序來了解不同算術(shù)表達(dá)式的解析樹的外觀，我很快編寫了該實(shí)用程序來幫助您將它們可視化。要使用該實(shí)用程序，您首先需要安裝Graphviz包，在運(yùn)行以下命令后，您可以打開生成的圖像文件 parsetree.png 并查看作為命令行參數(shù)傳遞的表達(dá)式的解析樹：（用不了不知咋回事，導(dǎo)不了包）
這是為表達(dá)式 14 + 2 * 3 - 6 / 2 生成的圖像 parsetree.png：
通過向它傳遞不同的算術(shù)表達(dá)式來稍微玩一下該實(shí)用程序，并查看特定表達(dá)式的解析樹是什么樣的。
現(xiàn)在，讓我們談?wù)劤橄笳Z法樹( AST )。這是我們將在本系列的其余部分大量使用的中間表示( IR )。它是我們解釋器和未來編譯器項(xiàng)目的核心數(shù)據(jù)結(jié)構(gòu)之一。
讓我們通過查看表達(dá)式 2 * 7 + 3的AST和解析樹來開始我們的討論：
從上圖可以看出，AST在變小的同時(shí)捕捉到了輸入的本質(zhì)。
以下是 AST 和解析樹之間的主要區(qū)別：
- AST 使用操作符/操作作為根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)，并使用操作數(shù)作為它們的子節(jié)點(diǎn)。
- 與解析樹不同，AST 不使用內(nèi)部節(jié)點(diǎn)來表示語法規(guī)則。
- AST 并不代表真實(shí)語法中的每一個(gè)細(xì)節(jié)（這就是為什么它們被稱為abstract）——例如，沒有規(guī)則節(jié)點(diǎn)和括號(hào)。
- 與相同語言構(gòu)造的解析樹相比，AST 是密集的。
那么，什么是抽象語法樹呢？一個(gè)抽象語法樹（AST）是表示一個(gè)語言結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)和根節(jié)點(diǎn)表示操作者的抽象句法結(jié)構(gòu)的樹，并且節(jié)點(diǎn)的子節(jié)點(diǎn)表示操作者的操作數(shù)。
我已經(jīng)提到 AST 比解析樹更緊湊。讓我們看一下表達(dá)式 7 + ((2 + 3))的AST和解析樹?？梢钥吹较旅娴腁ST比解析樹小很多，但還是抓住了輸入的本質(zhì)：
到目前為止一切順利，但是您如何在AST 中編碼運(yùn)算符優(yōu)先級(jí)？為了在AST 中對(duì)運(yùn)算符優(yōu)先級(jí)進(jìn)行編碼，即表示“X 發(fā)生在 Y 之前”，您只需將 X 在樹中放在比 Y 低的位置。您已經(jīng)在前面的圖片中看到了這一點(diǎn)。
讓我們再看一些例子。
在下圖中的左側(cè)，您可以看到表達(dá)式 2 * 7 + 3的AST。讓我們通過將 7 + 3 放在括號(hào)內(nèi)來更改優(yōu)先級(jí)。您可以在右側(cè)看到修改后的表達(dá)式 2 * (7 + 3)的AST是什么樣的：
這是表達(dá)式 1 + 2 + 3 + 4 + 5的AST：
從上面的圖片中，您可以看到優(yōu)先級(jí)較高的運(yùn)算符在樹中的位置較低。
好的，讓我們編寫一些代碼來實(shí)現(xiàn)不同的AST節(jié)點(diǎn)類型并修改我們的解析器以生成由這些節(jié)點(diǎn)組成的AST樹。
首先，我們將創(chuàng)建一個(gè)名為AST的基節(jié)點(diǎn)類，其他類將從該類繼承：
class AST(object):pass實(shí)際上沒有多少。回想一下，AST 表示操作符-操作數(shù)模型。到目前為止，我們有四個(gè)運(yùn)算符和整數(shù)操作數(shù)。運(yùn)算符是加法、減法、乘法和除法。我們可以創(chuàng)建一個(gè)單獨(dú)的類來表示每個(gè)運(yùn)算符，例如 AddNode、SubNode、MulNode 和 DivNode，但是我們將只用一個(gè)BinOp類來表示所有四個(gè)二元運(yùn)算符（二元運(yùn)算符是對(duì)兩個(gè)運(yùn)算符進(jìn)行運(yùn)算的運(yùn)算符）操作數(shù)）：
class BinOp(AST):def __init__(self, left, op, right):self.left = leftself.token = self.op = opself.right = right構(gòu)造函數(shù)的參數(shù)是left、op和right，其中l(wèi)eft和right 分別指向左操作數(shù)的節(jié)點(diǎn)和右操作數(shù)的節(jié)點(diǎn)。Op持有運(yùn)算符本身的標(biāo)記： Token( PLUS , ‘+’) 表示加號(hào)運(yùn)算符， Token( MINUS , ‘-’) 表示減號(hào)運(yùn)算符，依此類推。
為了在我們的AST 中表示整數(shù)，我們將定義一個(gè)Num類，該類將保存一個(gè)INTEGER標(biāo)記和標(biāo)記的值：
class Num(AST):def __init__(self, token):self.token = tokenself.value = token.value正如您所注意到的，所有節(jié)點(diǎn)都存儲(chǔ)用于創(chuàng)建節(jié)點(diǎn)的標(biāo)記。這主要是為了方便，將來會(huì)派上用場。
回憶一下表達(dá)式 2 * 7 + 3的AST。我們將在該表達(dá)式的代碼中手動(dòng)創(chuàng)建它：
>>> from spi import Token, MUL, PLUS, INTEGER, Num, BinOp >>> >>> mul_token = Token(MUL, '*') >>> plus_token = Token(PLUS, '+') >>> mul_node = BinOp( ... left=Num(Token(INTEGER, 2)), ... op=mul_token, ... right=Num(Token(INTEGER, 7)) ... ) >>> add_node = BinOp( ... left=mul_node, ... op=plus_token, ... right=Num(Token(INTEGER, 3)) ... )以下是定義了我們的新節(jié)點(diǎn)類后AST 的外觀。下圖也沿用了上面的手工構(gòu)建過程：
這是我們修改后的解析器代碼，它構(gòu)建并返回一個(gè)AST作為識(shí)別輸入（算術(shù)表達(dá)式）的結(jié)果：
讓我們回顧一下一些算術(shù)表達(dá)式的AST構(gòu)造過程。
如果你看一下解析器代碼上面你可以看到它的方式構(gòu)建了一個(gè)節(jié)點(diǎn)AST是每個(gè)BinOp節(jié)點(diǎn)采用的當(dāng)前值節(jié)點(diǎn)變量作為它的左子和呼叫到一個(gè)結(jié)果項(xiàng)或因素作為其右孩子，所以它有效地將節(jié)點(diǎn)向左下推，下面的表達(dá)式 1 +2 + 3 + 4 + 5 的樹就是一個(gè)很好的例子。這是解析器如何逐漸為表達(dá)式 1 + 2 + 3 + 4 + 5構(gòu)建AST的直觀表示：
為了幫助您可視化不同算術(shù)表達(dá)式的 AST，我編寫了一個(gè)小實(shí)用程序，它將算術(shù)表達(dá)式作為其第一個(gè)參數(shù)，并生成一個(gè)DOT文件，然后由dot實(shí)用程序處理該文件以實(shí)際為您繪制AST（dot是運(yùn)行dot命令需要安裝的Graphviz包）。這是一個(gè)命令和為表達(dá)式 7 + 3 * (10 / (12 / (3 + 1) - 1))生成的AST圖像：
編寫一些算術(shù)表達(dá)式，手動(dòng)繪制表達(dá)式的 AST，然后通過使用genastdot.py工具為相同的表達(dá)式生成AST圖像來驗(yàn)證它們是值得的。這將幫助您更好地理解解析器如何為不同的算術(shù)表達(dá)式構(gòu)造 AST。
好的，這是表達(dá)式 2 * 7 + 3的AST：
您如何遍歷樹以正確評(píng)估該樹表示的表達(dá)式？您可以通過使用后序遍歷（深度優(yōu)先遍歷的一種特殊情況）來實(shí)現(xiàn)這一點(diǎn)，它從根節(jié)點(diǎn)開始并從左到右遞歸訪問每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)。后序遍歷盡可能快地訪問遠(yuǎn)離根的節(jié)點(diǎn)。
這是后序遍歷的偽代碼，其中<>是BinOp節(jié)點(diǎn)的加法、減法、乘法或除法等操作的占位符，或者是返回Num 節(jié)點(diǎn)的整數(shù)值等更簡單的操作：
我們要為解釋器使用后序遍歷的原因是，首先，我們需要評(píng)估樹中較低的內(nèi)部節(jié)點(diǎn)，因?yàn)樗鼈兇砭哂懈邇?yōu)先級(jí)的運(yùn)算符；其次，我們需要在應(yīng)用運(yùn)算符之前評(píng)估運(yùn)算符的操作數(shù)到那些操作數(shù)。在下圖中，您可以看到，通過后序遍歷，我們首先評(píng)估表達(dá)式 2 * 7，然后才評(píng)估 14 + 3，這給出了正確的結(jié)果，17：
為了完整起見，我將提到深度優(yōu)先遍歷的三種類型：前序遍歷、中序遍歷和后序遍歷。遍歷方法的名字來自你在訪問代碼中放置動(dòng)作的地方：
有時(shí)您可能必須在所有這些點(diǎn)（前序、中序和后序）執(zhí)行某些操作。您將在本文的源代碼存儲(chǔ)庫中看到一些示例。
好的，讓我們編寫一些代碼來訪問和解釋由我們的解析器構(gòu)建的抽象語法樹，好嗎？
這是實(shí)現(xiàn)訪問者模式的源代碼：
class NodeVisitor(object):def visit(self, node):method_name = 'visit_' + type(node).__name__visitor = getattr(self, method_name, self.generic_visit)return visitor(node)def generic_visit(self, node):raise Exception('No visit_{} method'.format(type(node).__name__))這是我們的Interpreter類的源代碼，它繼承自NodeVisitor類并實(shí)現(xiàn)了不同的方法，這些方法的形式為visit_NodeType，其中NodeType被替換為節(jié)點(diǎn)的類名，如BinOp、Num等：
class Interpreter(NodeVisitor):def __init__(self, parser):self.parser = parserdef visit_BinOp(self, node):if node.op.type == PLUS:return self.visit(node.left) + self.visit(node.right)elif node.op.type == MINUS:return self.visit(node.left) - self.visit(node.right)elif node.op.type == MUL:return self.visit(node.left) * self.visit(node.right)elif node.op.type == DIV:return self.visit(node.left) / self.visit(node.right)def visit_Num(self, node):return node.value這段代碼有兩個(gè)有趣的地方值得一提：首先，操作AST節(jié)點(diǎn)的訪問者代碼與AST節(jié)點(diǎn)本身是解耦的。您可以看到任何AST節(jié)點(diǎn)類（BinOp 和 Num）都沒有提供任何代碼來操作存儲(chǔ)在這些節(jié)點(diǎn)中的數(shù)據(jù)。該邏輯封裝在實(shí)現(xiàn)NodeVisitor 類的Interpreter類中。
其次，而不是像這樣在 NodeVisitor 的訪問方法中使用一個(gè)巨大的if語句：
def visit(node):node_type = type(node).__name__if node_type == 'BinOp':return self.visit_BinOp(node)elif node_type == 'Num':return self.visit_Num(node)elif ...# ...或者像這樣：
def visit(node):if isinstance(node, BinOp):return self.visit_BinOp(node)elif isinstance(node, Num):return self.visit_Num(node)elif ...NodeVisitor 的訪問方法非常通用，它根據(jù)傳遞給它的節(jié)點(diǎn)類型將調(diào)用分派到適當(dāng)?shù)姆椒?。正如我之前提到?#xff0c;為了使用它，我們的解釋器從NodeVisitor類繼承并實(shí)現(xiàn)了必要的方法。所以如果傳遞給visit方法的節(jié)點(diǎn)類型是BinOp，那么visit方法會(huì)將調(diào)用分派到visit_BinOp方法；如果節(jié)點(diǎn)類型是Num，那么visit方法會(huì)將調(diào)用分派到visit_Num方法， 等等。
花一些時(shí)間研究這種方法（標(biāo)準(zhǔn) Python 模塊ast使用相同的節(jié)點(diǎn)遍歷機(jī)制），因?yàn)閷砦覀儗⑹褂迷S多新的visit_NodeType方法擴(kuò)展我們的解釋器。
該generic_visit方法是拋出一個(gè)異常，表明它遇到的實(shí)現(xiàn)類沒有相應(yīng)的節(jié)點(diǎn)的后備visit_NodeType方法。
現(xiàn)在，讓我們?yōu)楸磉_(dá)式 2 * 7 + 3手動(dòng)構(gòu)建一個(gè)AST，并將其傳遞給我們的解釋器，以查看訪問方法的作用，以評(píng)估表達(dá)式。以下是從 Python shell 執(zhí)行此操作的方法：
>>> from spi import Token, MUL, PLUS, INTEGER, Num, BinOp >>> >>> mul_token = Token(MUL, '*') >>> plus_token = Token(PLUS, '+') >>> mul_node = BinOp( ... left=Num(Token(INTEGER, 2)), ... op=mul_token, ... right=Num(Token(INTEGER, 7)) ... ) >>> add_node = BinOp( ... left=mul_node, ... op=plus_token, ... right=Num(Token(INTEGER, 3)) ... ) >>> from spi import Interpreter >>> inter = Interpreter(None) >>> inter.visit(add_node) 17如您所見，我將表達(dá)式樹的根傳遞給了訪問方法，并通過將調(diào)用分派到解釋器類的正確方法（visit_BinOp和visit_Num）并生成結(jié)果來觸發(fā)樹的遍歷。
好的，為了您的方便，這是我們新解釋器的完整代碼：
python代碼
運(yùn)行結(jié)果：
""" SPI - Simple Pascal Interpreter """############################################################################### # # # LEXER # # # ################################################################################ Token types # # EOF (end-of-file) token is used to indicate that # there is no more input left for lexical analysis INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = ('INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF' )class Token(object):def __init__(self, type, value):self.type = typeself.value = valuedef __str__(self):"""String representation of the class instance.Examples:Token(INTEGER, 3)Token(PLUS, '+')Token(MUL, '*')"""return 'Token({type}, {value})'.format(type=self.type,value=repr(self.value))def __repr__(self):return self.__str__()class Lexer(object):def __init__(self, text):# client string input, e.g. "4 + 2 * 3 - 6 / 2"self.text = text# self.pos is an index into self.textself.pos = 0self.current_char = self.text[self.pos]def error(self):raise Exception('Invalid character')def advance(self):"""Advance the `pos` pointer and set the `current_char` variable."""self.pos += 1if self.pos > len(self.text) - 1:self.current_char = None # Indicates end of inputelse:self.current_char = self.text[self.pos]def skip_whitespace(self):while self.current_char is not None and self.current_char.isspace():self.advance()def integer(self):"""Return a (multidigit) integer consumed from the input."""result = ''while self.current_char is not None and self.current_char.isdigit():result += self.current_charself.advance()return int(result)def get_next_token(self):"""Lexical analyzer (also known as scanner or tokenizer)This method is responsible for breaking a sentenceapart into tokens. One token at a time."""while self.current_char is not None:if self.current_char.isspace():self.skip_whitespace()continueif self.current_char.isdigit():return Token(INTEGER, self.integer())if self.current_char == '+':self.advance()return Token(PLUS, '+')if self.current_char == '-':self.advance()return Token(MINUS, '-')if self.current_char == '*':self.advance()return Token(MUL, '*')if self.current_char == '/':self.advance()return Token(DIV, '/')if self.current_char == '(':self.advance()return Token(LPAREN, '(')if self.current_char == ')':self.advance()return Token(RPAREN, ')')self.error()return Token(EOF, None)############################################################################### # # # PARSER # # # ###############################################################################class AST(object):passclass BinOp(AST):def __init__(self, left, op, right):self.left = leftself.token = self.op = opself.right = rightclass Num(AST):def __init__(self, token):self.token = tokenself.value = token.valueclass Parser(object):def __init__(self, lexer):self.lexer = lexer# set current token to the first token taken from the inputself.current_token = self.lexer.get_next_token()def error(self):raise Exception('Invalid syntax')def eat(self, token_type):# compare the current token type with the passed token# type and if they match then "eat" the current token# and assign the next token to the self.current_token,# otherwise raise an exception.if self.current_token.type == token_type:self.current_token = self.lexer.get_next_token()else:self.error()def factor(self):"""factor : INTEGER | LPAREN expr RPAREN"""token = self.current_tokenif token.type == INTEGER:self.eat(INTEGER)return Num(token)elif token.type == LPAREN:self.eat(LPAREN)node = self.expr()self.eat(RPAREN)return nodedef term(self):"""term : factor ((MUL | DIV) factor)*"""node = self.factor()while self.current_token.type in (MUL, DIV):token = self.current_tokenif token.type == MUL:self.eat(MUL)elif token.type == DIV:self.eat(DIV)node = BinOp(left=node, op=token, right=self.factor())return nodedef expr(self):"""expr : term ((PLUS | MINUS) term)*term : factor ((MUL | DIV) factor)*factor : INTEGER | LPAREN expr RPAREN"""node = self.term()while self.current_token.type in (PLUS, MINUS):token = self.current_tokenif token.type == PLUS:self.eat(PLUS)elif token.type == MINUS:self.eat(MINUS)node = BinOp(left=node, op=token, right=self.term())return nodedef parse(self):return self.expr()############################################################################### # # # INTERPRETER # # # ###############################################################################class NodeVisitor(object):def visit(self, node):method_name = 'visit_' + type(node).__name__visitor = getattr(self, method_name, self.generic_visit)return visitor(node)def generic_visit(self, node):raise Exception('No visit_{} method'.format(type(node).__name__))class Interpreter(NodeVisitor):def __init__(self, parser):self.parser = parserdef visit_BinOp(self, node):if node.op.type == PLUS:return self.visit(node.left) + self.visit(node.right)elif node.op.type == MINUS:return self.visit(node.left) - self.visit(node.right)elif node.op.type == MUL:return self.visit(node.left) * self.visit(node.right)elif node.op.type == DIV:return self.visit(node.left) / self.visit(node.right)def visit_Num(self, node):return node.valuedef interpret(self):tree = self.parser.parse()return self.visit(tree)def main():while True:try:try:# text = raw_input('spi> ')text = input('spi> ')except NameError: # Python3text = input('spi> ')except EOFError:breakif not text:continuelexer = Lexer(text)parser = Parser(lexer)interpreter = Interpreter(parser)result = interpreter.interpret()print(result)if __name__ == '__main__':main() C:\Users\Administrator.YC-20180625SBPF\AppData\Local\Programs\Python\Python39\python.exe C:/Users/Administrator.YC-20180625SBPF/Desktop/構(gòu)建編譯器/calc7.py spi> 3+5*(3-3 )/3+3 6.0 spi>插——后序遍歷
C語言代碼（有錯(cuò)誤)
#include <stdio.h> #include <stdlib.h> #include <memory.h> #include <string.h> #include<math.h>#define flag_integer 0 #define flag_plus 1 #define flag_minus 2 #define flag_multiply 3 #define flag_divide 4 #define flag_LPAREN 5 #define flag_RPAREN 6#define flag_EOF 7void error() {printf("程序不對(duì)勁！\n");exit(-1); }//給字符數(shù)組賦值 void StrAssign(char* T, const char* chars) {int i;for (i = 0; i < strlen(chars); i++)T[i] = *(chars + i);T[i] = '\0'; }struct Token {int type;int value; };//Token初始化函數(shù) struct Token* mallocToken(int type, int value) {struct Token* token = (Token*)malloc(sizeof(Token));if (NULL != token) {token->type = type;token->value = value;return token;}elseerror(); }//樹的節(jié)點(diǎn) struct BinOpOrNum {struct BinOpOrNum* left;struct Token* op_or_num;struct BinOpOrNum* right; };//樹結(jié)點(diǎn)初始化函數(shù) struct BinOpOrNum* mallocOpOrNum(struct BinOpOrNum* left, struct Token* op_or_num, struct BinOpOrNum* right) {struct BinOpOrNum* node = (BinOpOrNum*)malloc(sizeof(BinOpOrNum));if (NULL != node) {node->left = left;node->op_or_num = op_or_num;node->right = right;return node;}elseerror(); }struct Lexer {char* text;int pos; };struct Parser {struct Lexer* lexer;struct Token current_token; };struct Interpreter {struct Parser* parser; };void skip_whitespace(struct Lexer* le) {while (le->text[le->pos] == ' ') {le->pos++;} }//判斷Interpreter中當(dāng)前pos是不是數(shù)字 int is_digital(char c) {if (c >= '0' && c <= '9')return 1;elsereturn 0; }void advance(struct Lexer* le) {le->pos++; }char current_char(struct Lexer* le) {return(le->text[le->pos]); }//獲取數(shù)字token的數(shù)值（把數(shù)字字符數(shù)組轉(zhuǎn)換為數(shù)字） int integer(struct Lexer* le) {char temp[20];int i = 0;while (is_digital(le->text[le->pos])) {temp[i] = le->text[le->pos];i++;advance(le);}int result = 0;int j = 0;int len = i;while (j < len) {result += (temp[j] - '0') * pow(10, len - j - 1);j++;}return result; }void get_next_token(struct Parser* par) {//先跳空格，再判斷有沒有結(jié)束符if (current_char(par->lexer) == ' ')skip_whitespace(par->lexer);if (par->lexer->pos > (strlen(par->lexer->text) - 1)) {par->current_token = { flag_EOF, NULL };return;}char current = current_char(par->lexer);if (is_digital(current)) {par->current_token = { flag_integer, integer(par->lexer) };return;}if (current == '+') {par->current_token = { flag_plus, NULL };advance(par->lexer);return;}if (current == '-') {par->current_token = { flag_minus, NULL };advance(par->lexer);;return;}if (current == '*') {par->current_token = { flag_multiply, NULL };advance(par->lexer);;return;}if (current == '/') {par->current_token = { flag_divide, NULL };advance(par->lexer);;return;}if (current == '(') {par->current_token = { flag_LPAREN, NULL };advance(par->lexer);;return;}if (current == ')') {par->current_token = { flag_RPAREN, NULL };advance(par->lexer);;return;}error();//如果都不是以上的字符，則報(bào)錯(cuò)并退出程序 }int eat(struct Parser* par, int type) {int current_token_value = par->current_token.value;if (par->current_token.type == type) {get_next_token(par);return current_token_value;}else {error();} }//遍歷樹 int visit_BinOp(struct BinOpOrNum* node) {if (node->op_or_num->type == flag_plus)return visit_BinOp(node->left) + visit_BinOp(node->right);else if (node->op_or_num->type == flag_minus)return visit_BinOp(node->left) - visit_BinOp(node->right);else if (node->op_or_num->type == flag_multiply)return visit_BinOp(node->left) * visit_BinOp(node->right);else if (node->op_or_num->type == flag_divide)return visit_BinOp(node->left) / visit_BinOp(node->right);else if (node->op_or_num->type == flag_integer)return node->op_or_num->value; }struct BinOpOrNum* expr(struct Parser* par);//expr定義在后面，在這里要聲明才能使用 //判斷數(shù)字或括號(hào) struct BinOpOrNum* factor(struct Parser* par) {int type = par->current_token.type;if (type == flag_integer) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, flag_integer);struct BinOpOrNum* node = mallocOpOrNum(NULL, token, NULL);return node;}else if (type == flag_LPAREN) {eat(par, flag_LPAREN);//遇到括號(hào)先吃掉，然后回到exprstruct BinOpOrNum* node = expr(par);eat(par, flag_RPAREN);return node;} }//判斷乘除 struct BinOpOrNum* term(struct Parser* par) {struct BinOpOrNum* node;node = factor(par);int type = par->current_token.type;if (type == flag_multiply or type == flag_divide) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, type);struct BinOpOrNum* node_ = mallocOpOrNum(node, token, factor(par));return node_;}else {return node;} }//判斷加減 struct BinOpOrNum* expr(struct Parser* par) {struct BinOpOrNum* node;node = term(par);int type = par->current_token.type;if (type == flag_plus or type == flag_minus) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, type);struct BinOpOrNum* node_ = mallocOpOrNum(node, token, term(par));return node_;}else {return node;} }struct BinOpOrNum* parser(struct Parser* par) {return expr(par); }int interpreter(struct Interpreter* ipt) {struct BinOpOrNum* tree = parser(ipt->parser);return visit_BinOp(tree); }int main() {char text[50];//StrAssign(text, "(3+2) *7");StrAssign(text, " 3+ 2* ((3+7) + 5 )");struct Lexer le = { text, 0 };struct Parser par = { &le };get_next_token(&par);struct Interpreter ipt = { &par };int result = interpreter(&ipt);printf("%s = %d\n\n", text, result);return 0; }運(yùn)行結(jié)果：
3+ 2* ((3+7) + 5 ) = 33但是程序貌似有bug啊，不知道是建立樹那里問題還是訪問樹那里問題，明天再調(diào)試了！
原來是expr和term函數(shù)不能缺少while循環(huán)，如果缺少的話就不能判斷多個(gè)加減號(hào)和乘除號(hào)了
同時(shí)我發(fā)現(xiàn)我里面有重定義的情況，找了半天才發(fā)現(xiàn)錯(cuò)誤
修改后如下
//判斷乘除 struct BinOpOrNum* term(struct Parser* par) {struct BinOpOrNum* node = factor(par);while (par->current_token.type == flag_multiply or par->current_token.type == flag_divide) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, par->current_token.type);node = mallocOpOrNum(node, token, factor(par));}return node; }//判斷加減 struct BinOpOrNum* expr(struct Parser* par) {struct BinOpOrNum* node = term(par);while (par->current_token.type == flag_plus or par->current_token.type == flag_minus) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, par->current_token.type);//struct BinOpOrNum* node = mallocOpOrNum(node, token, term(par));//重定義了，還報(bào)錯(cuò)使用未經(jīng)初始化的指針，找了半天才發(fā)現(xiàn)問題node = mallocOpOrNum(node, token, term(par));}return node; }C語言代碼（修改優(yōu)化后）
#include <stdio.h> #include <stdlib.h> #include <memory.h> #include <string.h> #include<math.h>#define flag_integer 0 #define flag_plus 1 #define flag_minus 2 #define flag_multiply 3 #define flag_divide 4 #define flag_LPAREN 5 #define flag_RPAREN 6#define flag_EOF 7void error() {printf("程序不對(duì)勁！\n");exit(-1); }//給字符數(shù)組賦值 void StrAssign(char* T, const char* chars) {int i;for (i = 0; i < strlen(chars); i++)T[i] = *(chars + i);T[i] = '\0'; }struct Token {int type;int value; };//Token初始化函數(shù) struct Token* mallocToken(int type, int value) {struct Token* token = (Token*)malloc(sizeof(Token));if (NULL != token) {token->type = type;token->value = value;return token;}elseerror(); }//樹的節(jié)點(diǎn) struct BinOpOrNum {struct BinOpOrNum* left;struct Token* op_or_num;struct BinOpOrNum* right; };//樹結(jié)點(diǎn)初始化函數(shù) struct BinOpOrNum* mallocOpOrNum(struct BinOpOrNum* left, struct Token* op_or_num, struct BinOpOrNum* right) {struct BinOpOrNum* node = (BinOpOrNum*)malloc(sizeof(BinOpOrNum));if (NULL != node) {node->left = left;node->op_or_num = op_or_num;node->right = right;return node;}elseerror(); }struct Lexer {char* text;int pos; };struct Parser {struct Lexer* lexer;struct Token current_token; };struct Interpreter {struct Parser* parser; };void skip_whitespace(struct Lexer* le) {while (le->text[le->pos] == ' ') {le->pos++;} }//判斷Interpreter中當(dāng)前pos是不是數(shù)字 int is_digital(char c) {if (c >= '0' && c <= '9')return 1;elsereturn 0; }void advance(struct Lexer* le) {le->pos++; }char current_char(struct Lexer* le) {return(le->text[le->pos]); }//獲取數(shù)字token的數(shù)值（把數(shù)字字符數(shù)組轉(zhuǎn)換為數(shù)字） int integer(struct Lexer* le) {char temp[20];int i = 0;while (is_digital(le->text[le->pos])) {temp[i] = le->text[le->pos];i++;advance(le);}int result = 0;int j = 0;int len = i;while (j < len) {result += (temp[j] - '0') * pow(10, len - j - 1);j++;}return result; }void get_next_token(struct Parser* par) {//先跳空格，再判斷有沒有結(jié)束符if (current_char(par->lexer) == ' ')skip_whitespace(par->lexer);if (par->lexer->pos > (strlen(par->lexer->text) - 1)) {par->current_token = { flag_EOF, NULL };return;}char current = current_char(par->lexer);if (is_digital(current)) {par->current_token = { flag_integer, integer(par->lexer) };return;}if (current == '+') {par->current_token = { flag_plus, NULL };advance(par->lexer);return;}if (current == '-') {par->current_token = { flag_minus, NULL };advance(par->lexer);;return;}if (current == '*') {par->current_token = { flag_multiply, NULL };advance(par->lexer);;return;}if (current == '/') {par->current_token = { flag_divide, NULL };advance(par->lexer);;return;}if (current == '(') {par->current_token = { flag_LPAREN, NULL };advance(par->lexer);;return;}if (current == ')') {par->current_token = { flag_RPAREN, NULL };advance(par->lexer);;return;}error();//如果都不是以上的字符，則報(bào)錯(cuò)并退出程序 }int eat(struct Parser* par, int type) {int current_token_value = par->current_token.value;if (par->current_token.type == type) {get_next_token(par);return current_token_value;}else {error();} }//遍歷樹 int visit_BinOp(struct BinOpOrNum* node) {if (node->op_or_num->type == flag_plus)return visit_BinOp(node->left) + visit_BinOp(node->right);else if (node->op_or_num->type == flag_minus)return visit_BinOp(node->left) - visit_BinOp(node->right);else if (node->op_or_num->type == flag_multiply)return visit_BinOp(node->left) * visit_BinOp(node->right);else if (node->op_or_num->type == flag_divide)return visit_BinOp(node->left) / visit_BinOp(node->right);else if (node->op_or_num->type == flag_integer)return node->op_or_num->value; }struct BinOpOrNum* expr(struct Parser* par);//expr定義在后面，在這里要聲明才能使用 //判斷數(shù)字或括號(hào) struct BinOpOrNum* factor(struct Parser* par) {if (par->current_token.type == flag_integer) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, flag_integer);struct BinOpOrNum* node = mallocOpOrNum(NULL, token, NULL);return node;}else if (par->current_token.type == flag_LPAREN) {eat(par, flag_LPAREN);//遇到括號(hào)先吃掉，然后回到exprstruct BinOpOrNum* node = expr(par);eat(par, flag_RPAREN);return node;} }//判斷乘除 struct BinOpOrNum* term(struct Parser* par) {struct BinOpOrNum* node = factor(par);while (par->current_token.type == flag_multiply or par->current_token.type == flag_divide) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, par->current_token.type);node = mallocOpOrNum(node, token, factor(par));}return node; }//判斷加減 struct BinOpOrNum* expr(struct Parser* par) {struct BinOpOrNum* node = term(par);while (par->current_token.type == flag_plus or par->current_token.type == flag_minus) {struct Token* token = mallocToken(par->current_token.type, par->current_token.value);eat(par, par->current_token.type);//struct BinOpOrNum* node = mallocOpOrNum(node, token, term(par));//重定義了，還報(bào)錯(cuò)使用未經(jīng)初始化的指針，找了半天才發(fā)現(xiàn)問題node = mallocOpOrNum(node, token, term(par));}return node; }struct BinOpOrNum* parser(struct Parser* par) {return expr(par); }int interpreter(struct Interpreter* ipt) {struct BinOpOrNum* tree = parser(ipt->parser);return visit_BinOp(tree); }int main() {char text[50];//StrAssign(text, "(3+2) *7");StrAssign(text, " 3+2*(3+7)+(1 - (3+7)/5)* (2/2+3 )* 1");struct Lexer le = { text, 0 };struct Parser par = { &le };get_next_token(&par);struct Interpreter ipt = { &par };int result = interpreter(&ipt);printf("%s = %d\n\n", text, result);return 0; }運(yùn)行結(jié)果：
3+2*(3+7)+(1 - (3+7)/5)* (2/2+3 )* 1 = 19總結(jié)
今天，您已經(jīng)了解了解析樹、AST、如何構(gòu)造 AST 以及如何遍歷它們以解釋由這些 AST 表示的輸入。您還修改了解析器和解釋器并將它們分開。詞法分析器、解析器和解釋器之間的當(dāng)前接口現(xiàn)在看起來像這樣：
您可以將其理解為“解析器從詞法分析器中獲取標(biāo)記，然后返回生成的AST以供解釋器遍歷和解釋輸入。”
今天就到此為止，但在結(jié)束之前，我想簡單地談?wù)勥f歸下降解析器，即給它們一個(gè)定義，因?yàn)槲疑洗纬兄Z會(huì)更詳細(xì)地討論它們。所以你開始了：遞歸下降解析器是一個(gè)自頂向下的解析器，它使用一組遞歸過程來處理輸入。自頂向下反映了解析器從構(gòu)造解析樹的頂部節(jié)點(diǎn)開始，然后逐漸構(gòu)造較低節(jié)點(diǎn)的事實(shí)。
現(xiàn)在是練習(xí)的時(shí)候了:)
- 編寫一個(gè)翻譯器（提示：節(jié)點(diǎn)訪問者），將算術(shù)表達(dá)式作為輸入并以后綴表示法打印出來，也稱為反向波蘭表示法 ( RPN )。例如，如果翻譯器的輸入是表達(dá)式 (5 + 3) * 12 / 3，那么輸出應(yīng)該是 5 3 + 12 * 3 /。請(qǐng)?jiān)诖颂幉榭创鸢?#xff0c;但請(qǐng)先嘗試自己解決。
- 編寫一個(gè)翻譯器（節(jié)點(diǎn)訪問者），將算術(shù)表達(dá)式作為輸入并以LISP風(fēng)格的符號(hào)打印出來，即 2 + 3 將變?yōu)?(+ 2 3) 并且 (2 + 3 * 5) 將變?yōu)?(+ 2 (* 3 5))。您可以在此處找到答案，但在查看提供的解決方案之前再次嘗試先解決它。
在下一篇文章中，我們將向不斷增長的 Pascal 解釋器添加賦值和一元運(yùn)算符。在那之前，玩得開心，很快就會(huì)見到你。
PS我還提供了解釋器的 Rust 實(shí)現(xiàn)，您可以在GitHub上找到。這是我學(xué)習(xí)Rust 的一種方式，所以請(qǐng)記住，代碼可能還不是“慣用的”。關(guān)于如何改進(jìn)代碼的意見和建議總是受歡迎的。
總結(jié)
以上是生活随笔為你收集整理的【编译原理】构建一个简单的解释器（Let’s Build A Simple Interpreter. Part 7.）（笔记）解释器 interpreter 解析器 parser 抽象语法树AST的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C语言 尾递归
- 下一篇： 【编译原理】构建一个简单的解释器（Let