【編譯原理】讓我們來構建一個簡單的解釋器（Let’s Build A Simple Interpreter. Part 6.）

文章目錄

• • python代碼
  • C語言代碼
  • 總結

今天是這一天:) “為什么？” 你可能會問。原因是今天我們結束了對算術表達式的討論（好吧，幾乎）通過在我們的語法中添加括號表達式并實現一個解釋器，該解釋器將能夠評估具有任意深度嵌套的括號表達式，例如表達式 7 + 3 * (10 / (12 / (3 + 1) - 1))。

讓我們開始吧，好嗎？

首先，讓我們修改語法以支持括號內的表達式。正如您在第 5 部分 中記得的那樣，因子規則用于表達式中的基本單位。在那篇文章中，我們唯一的基本單位是整數。今天我們要添加另一個基本單位——括號表達式。我們開始做吧。

這是我們更新的語法：

的EXPR和術語制作完全相同如在第5部分和唯一的變化是在因子生產其中終端LPAREN表示左括號“（”，終端RPAREN表示右括號“）”，和非括號之間的終結符 expr指的是expr 規則。

這是factor的更新語法圖，現在包括替代方案：

（翻譯不完全準確，將就著看吧！大致也能看懂）

因為expr和術語的語法規則沒有改變，它們的語法圖看起來與第 5 部分中的相同：

這是我們新語法的一個有趣特性——它是遞歸的。如果您嘗試推導表達式 2 * (7 + 3)，您將從expr開始符號開始，最終您將再次遞歸使用expr規則推導 (7 + 3) 部分原始算術表達式。

讓我們根據語法對表達式 2 * (7 + 3) 進行分解，看看它的樣子：

順便說一句：如果您需要復習遞歸，請看一看 Daniel P. Friedman 和 Matthias Felleisen 的The Little Schemer一書——它真的很棒。

好的，讓我們開始吧，將我們新更新的語法翻譯成代碼。

以下是對上一篇文章中代碼的主要更改：

該詞法已被修改為返回兩個標記：LPAREN的左括號和RPAREN一個右括號。
該解釋的因素法已略有更新解析除了整數括號表達式。
這是可以計算包含整數的算術表達式的計算器的完整代碼；任意數量的加法、減法、乘法和除法運算符；和帶有任意深度嵌套的括號表達式：

python代碼

# -*- coding: utf-8 -*- """ @File : calc6.py @Time : 2021/7/21 10:00 @Author : Dontla @Email : sxana@qq.com @Software: PyCharm """ # 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)class Interpreter(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 token.valueelif token.type == LPAREN:self.eat(LPAREN)result = self.expr()self.eat(RPAREN)return resultdef term(self):"""term : factor ((MUL | DIV) factor)*"""result = self.factor()while self.current_token.type in (MUL, DIV):token = self.current_tokenif token.type == MUL:self.eat(MUL)result = result * self.factor()elif token.type == DIV:self.eat(DIV)result = result / self.factor()return resultdef expr(self):"""Arithmetic expression parser / interpreter.calc> 7 + 3 * (10 / (12 / (3 + 1) - 1))22expr : term ((PLUS | MINUS) term)*term : factor ((MUL | DIV) factor)*factor : INTEGER | LPAREN expr RPAREN"""result = self.term()while self.current_token.type in (PLUS, MINUS):token = self.current_tokenif token.type == PLUS:self.eat(PLUS)result = result + self.term()elif token.type == MINUS:self.eat(MINUS)result = result - self.term()return resultdef main():while True:try:# To run under Python3 replace 'raw_input' call# with 'input'# text = raw_input('calc> ')text = input('calc> ')except EOFError:breakif not text:continuelexer = Lexer(text)interpreter = Interpreter(lexer)result = interpreter.expr()print(result)if __name__ == '__main__':main()

運行結果：

D:\python_virtualenv\my_flask\Scripts\python.exe C:/Users/Administrator/Desktop/編譯原理/python/calc6.py calc> 5 * ( 3 - 2)/(2 -1) + ( 4 - 2) 7.0 calc>

C語言代碼

將首次初始化token放在函數外執行，之前放在函數內執行老出錯找了好久才找到問題，第一次初始化怎么能放在反復調用的函數內呢？

#include <stdio.h> #include <stdlib.h> #include <memory.h> #include <string.h> #include<math.h>#define flag_digital 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 5struct Token {int type;int value; };struct Lexer {char* text;int pos; };struct Interpreter {struct Lexer* lexer;struct Token current_token; };void error() {printf("輸入非法！\n");exit(-1); }void skip_whitespace(struct Lexer* le) {while (le->text[le->pos] == ' ') {le->pos++;} }//判斷Interpreter中當前pos是不是數字 int is_integer(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]); }//獲取數字token的數值（把數字字符數組轉換為數字） int integer(struct Lexer* le) {char temp[20];int i = 0;while (is_integer(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 Interpreter* pipt) {//先跳空格，再判斷有沒有結束符if (current_char(pipt->lexer) == ' ')skip_whitespace(pipt->lexer);if (pipt->lexer->pos > (strlen(pipt->lexer->text) - 1)) {pipt->current_token = { flag_EOF, NULL };return;}char current = current_char(pipt->lexer);if (is_integer(current)) {pipt->current_token = { flag_digital, integer(pipt->lexer)};return;}if (current == '+') {pipt->current_token = { flag_plus, NULL };advance(pipt->lexer);return;}if (current == '-') {pipt->current_token = { flag_minus, NULL };advance(pipt->lexer);;return;}if (current == '*') {pipt->current_token = { flag_multiply, NULL };advance(pipt->lexer);;return;}if (current == '/') {pipt->current_token = { flag_divide, NULL };advance(pipt->lexer);;return;}if (current == '(') {pipt->current_token = { flag_LPAREN, NULL };advance(pipt->lexer);;return;}if (current == ')') {pipt->current_token = { flag_RPAREN, NULL };advance(pipt->lexer);;return;}error();//如果都不是以上的字符，則報錯并退出程序 }int eat(struct Interpreter* pipt, int type) {int current_token_value = pipt->current_token.value;if (pipt->current_token.type == type) {get_next_token(pipt);return current_token_value;}else {error();} }int expr(struct Interpreter* pipt);//expr定義在后面，在這里要聲明才能使用 int factor(struct Interpreter* pipt) {if (pipt->current_token.type == flag_digital) {return eat(pipt, flag_digital);}else if(pipt->current_token.type == flag_LPAREN) {eat(pipt, flag_LPAREN);int result = expr(pipt);eat(pipt, flag_RPAREN);return result;}}//判斷乘除 int term(struct Interpreter* pipt) {int result = factor(pipt);while (true) {int token_type = pipt->current_token.type;if (token_type == flag_multiply) {eat(pipt, flag_multiply);result = result * factor(pipt);}else if (token_type == flag_divide) {eat(pipt, flag_divide);result = result / factor(pipt);}else {return result;}} } int expr(struct Interpreter* pipt) {int result = term(pipt);while (true) {int token_type = pipt->current_token.type;if (token_type == flag_plus) {eat(pipt, flag_plus);result = result + term(pipt);}else if (token_type == flag_minus) {eat(pipt, flag_minus);result = result - term(pipt);}else {return result;}} }int main() {char text[50];while (1){printf("請輸入算式：\n");//scanf_s("%s", text, sizeof(text));//sanf沒法輸入空格？int i = 0;while ((text[i] = getchar()) != '\n') {//putchar(text[i]);i++;}text[i] = '\0';struct Lexer le = {text, 0};struct Interpreter ipt = { &le };get_next_token(&ipt);int result = expr(&ipt);printf("= %d\n\n", result);}return 0; }

運行結果：

請輸入算式： 3+3 = 6請輸入算式： 4/2 = 2請輸入算式： 2+3-4 = 1請輸入算式： 3+(3+2) = 8請輸入算式： 2*(4+3) = 14請輸入算式： 2*(5 +3 ) - (3+4) = 9

總結

如本文所述，編寫您自己的算術表達式解釋器版本。請記住：重復是所有學習之母。

嘿嘿，你一直讀到最后！恭喜，您剛剛學會了如何創建（如果您已經完成了練習 - 您實際上已經編寫了）一個可以計算非常復雜的算術表達式的基本遞歸下降解析器/解釋器。

在下一篇文章中，我將更詳細地討論遞歸下降解析器。我還將在解釋器和編譯器構造中介紹一種重要且廣泛使用的數據結構，我們將在整個系列中使用它。

請繼續關注，很快就會見到你。在此之前，繼續為您的解釋器工作，最重要的是：玩得開心，享受這個過程！

總結

以上是生活随笔為你收集整理的【编译原理】让我们来构建一个简单的解释器（Let’s Build A Simple Interpreter. Part 6.）（python/c/c++版）（笔记）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。