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

文章目錄

• • python代碼
  • c代碼
  • 總結

讓我們再次深入研究解釋器和編譯器。

今天，我將向您展示第 1 部分中計算器的新版本，它將能夠：

1、處理輸入字符串中任意位置的空白字符
2、從輸入中使用多位整數
3、兩個整數相減（目前只能相加）

與第 1 部分的版本相比，主要的代碼變化 是：

1、該get_next_token方法重構了一下。增加pos指針的邏輯被分解為一個單獨的方法Advance。
2、添加了另外兩種方法：skip_whitespace忽略空白字符和integer處理輸入中的多位整數。
3、該EXPR方法被修改，以識別INTEGER - > MINUS - > INTEGER短語除了INTEGER - > PLUS - > INTEGER短語。該方法現在還可以在成功識別相應短語后解釋加法和減法。

python代碼

# -*- coding: utf-8 -*- """ # -*- coding: utf-8 -*- """ @File : calc2.py @Time : 2021/7/8 10:32 @Author : Dontla @Email : sxana@qq.com @Software: PyCharm """ # EOF (end-of-file) token is used to indicate that # there is no more input left for lexical analysis INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'class Token(object):def __init__(self, type_, value):# token type: INTEGER, PLUS, MINUS, or EOFself.type = type_# token value: non-negative integer value, '+', '-', or Noneself.value = valuedef __str__(self):"""String representation of the class instance.Examples:Token(INTEGER, 3)Token(PLUS '+')"""return 'Token({type}, {value})'.format(type=self.type,value=repr(self.value))def __repr__(self):return self.__str__()class Interpreter(object):def __init__(self, text):# client string input, e.g. "3 + 5", "12 - 5", etcself.text = text# self.pos is an index into self.textself.pos = 0# current token instanceself.current_token = Noneself.current_char = self.text[self.pos]def error(self):raise Exception('Error parsing input')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."""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, '-')self.error()return Token(EOF, None)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.get_next_token()else:self.error()def expr(self):"""Parser / Interpreterexpr -> INTEGER PLUS INTEGERexpr -> INTEGER MINUS INTEGER"""# set current token to the first token taken from the inputself.current_token = self.get_next_token()# we expect the current token to be an integerleft = self.current_tokenself.eat(INTEGER)# we expect the current token to be either a '+' or '-'op = self.current_tokenif op.type == PLUS:self.eat(PLUS)else:self.eat(MINUS)# we expect the current token to be an integerright = self.current_tokenself.eat(INTEGER)# after the above call the self.current_token is set to# EOF token# at this point either the INTEGER PLUS INTEGER or# the INTEGER MINUS INTEGER sequence of tokens# has been successfully found and the method can just# return the result of adding or subtracting two integers,# thus effectively interpreting client inputif op.type == PLUS:result = left.value + right.valueelse:result = left.value - right.valuereturn 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:continueinterpreter = Interpreter(text)result = interpreter.expr()print(result)if __name__ == '__main__':main()

運行結果：

D:\python_virtualenv\my_flask\Scripts\python.exe C:/Users/Administrator/Desktop/編譯原理/python/calc2.py calc> 33234 - 324 32910

c代碼

注意，跟上一課代碼不同的是，eat函數在最后才調用get_next_token函數，使得最后得到的token不是當前token而是下一個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_EOF 3struct Token {int type;int value; };struct Interpreter {char* text;int pos;struct Token current_token; };void error() {printf("輸入非法！\n");exit(-1); }void skip_whitespace(struct Interpreter* pipt) {while (pipt->text[pipt->pos] == ' ') {pipt->pos++;} }//判斷Interpreter中當前pos是不是數字 int is_integer(char c) {if (c >= '0' && c <= '9')return 1;elsereturn 0; }void advance(struct Interpreter* pipt) {pipt->pos++; }char current_char(struct Interpreter* pipt) {return(pipt->text[pipt->pos]); }//獲取數字token的數值（把數字字符數組轉換為數字） int integer(struct Interpreter* pipt) {char temp[20];int i = 0;while (is_integer(pipt->text[pipt->pos])) {temp[i] = pipt->text[pipt->pos];i++;advance(pipt);}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 (pipt->pos > (strlen(pipt->text) - 1)) {pipt->current_token = { flag_EOF, NULL };return;}if (current_char(pipt) == ' ')skip_whitespace(pipt);if (is_integer(current_char(pipt))) {pipt->current_token = { flag_digital, integer(pipt) };return;}if (current_char(pipt) == '+') {pipt->current_token = { flag_plus, NULL };pipt->pos++;return;}if (current_char(pipt) == '-') {pipt->current_token = { flag_minus, NULL };pipt->pos++;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(char* text) {struct Interpreter ipt = { text, 0 };get_next_token(&ipt);int left = eat(&ipt, flag_digital);//斷言第一個token是數字//int left = ipt.current_token.value;int op = ipt.current_token.type;//斷言第二個token是加號或減號if (op == flag_plus) {eat(&ipt, flag_plus);}else {eat(&ipt, flag_minus);}int right = eat(&ipt, flag_digital);//斷言第三個token是數字int result = 0;if (op == flag_plus) {result = left + right;}else if (op == flag_minus) {result = left - right;}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';int result = expr(text);printf("= %d\n\n", result);}return 0; }

運行結果：（能夠自動跳過空格，那么有人會問，數字之間的空格呢，能跳過嗎？通常來說，我們一般將數字間的空格視為輸入非法的，空格有其另外的作用！）

請輸入算式： 3+5 = 8請輸入算式： 44 + 55 = 99請輸入算式：555 + 555 = 1110請輸入算式：

總結

在第 1 部分中，您學習了兩個重要概念，即token標記和詞法分析器lexical analyzer。今天我想談談詞素lexeme、解析parsing和解析器parsers。

您已經了解標記。但是為了讓我完成對標記的討論，我需要提及詞素。什么是詞素？詞素是形成一個標記的字符序列。在下圖中，您可以看到一些標記和示例詞素的示例，希望它可以使它們之間的關系變得清晰：

現在，還記得我們的朋友expr方法嗎？我之前說過，這就是算術表達式的解釋實際發生的地方。但在解釋一個表達式之前，您首先需要識別它是什么類型的短語，例如，是加法還是減法。這就是expr方法本質上所做的：它在從get_next_token方法獲得的標記流中找到結構，然后解釋已識別的短語，生成算術表達式的結果。

在標記流中找到結構的過程，或者換句話說，識別標記流中的短語的過程稱為解析。執行該工作的解釋器或編譯器的部分稱為解析器。

所以現在您知道expr方法是解析和解釋發生的解釋器的一部分- expr方法首先嘗試識別（解析）INTEGER -> PLUS -> INTEGER或INTEGER -> MINUS -> INTEGER短語標記流，在成功識別（解析）其中一個短語后，該方法會對其進行解釋，并將兩個整數的加法或減法結果返回給調用者。

現在又到了鍛煉的時候了。

1、擴展計算器以處理兩個整數的乘法
2、擴展計算器以處理兩個整數的除法
3、修改代碼以解釋包含任意數量的加法和減法的表達式，例如“9 - 5 + 3 + 11”

檢查你的理解。

1、什么是詞素lexeme？【詞素是形成一個標記的字符序列】
2、在標記流中找到結構的過程的名稱是什么，或者換句話說，識別該標記流中某個短語的過程的名稱是什么？【解析】
3、執行解析的解釋器（編譯器）部分的名稱是什么？【解析器】

總結

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

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