一起来写个简单的解释器

本系列文章参考国外编程高手鲁斯兰的博客文章《Let’s Build A Simple Interpreter》。

还记得在第7部分提到的最终目标吗？

实现一个Pascal编程语言子集的全功能解释器。

这一篇文章，我们将朝着我们的最终目标更进一步。

我们将更新我们的解释器来解析和解释我们的第一个完整的Pascal程序。

我们先来看一下要解释的Pascal程序代码：

PROGRAM Part10;VAR number : INTEGER; a, b, c, x : INTEGER; y : REAL;BEGIN BEGIN number := 2; a := number; b := 10 * a + 10 * number DIV 6; c := a - - b END; x := 11; y := 20 / 7 + 3.14; { writeln('a = ', a); } { writeln('b = ', b); } { writeln('c = ', c); } { writeln('number = ', number); } { writeln('x = ', x); } { writeln('y = ', y); }END.

在上方代码中，出现了我们之前没有接触过的内容。

实际上这些内容比较简单易懂，主要包括：

程序头

变量声明

DIV关键字

注释

这些实际上也是这一篇文章的学习目标：

如何解析和解释Pascal程序头；

如何解析Pascal的变量声明；

如何让解释器支持DIV关键字的整数除法和斜杠“/”的浮点数除法；

如何增加对注释的支持。

一、更新语法

1、Program

程序由保留字（PROGRAM）、程序名称（一个变量）、分号“；”以及语句块（block）和点“.”（DOT）组成。

program : PROGRAM variable SEMI block DOT

例如：

2、block

语句块由声明语句和符合语句组成。

block : declarations compound_statement

例如：

3、declarations

声明语句由保留字（VAR）、一个或多个变量声明（variable_declaration与分号组成）组成，当然也可以没有变量声明（empty）。

declarations : VAR (variable_declaration SEMI)+ | empty

例如：

4、variable_declaration

变量声明包括包括变量名称（ID）或者多个逗号（COMMA）分隔的变量名称、冒号（COLON）以及数据类型（type_spec）组成。

variable_declaration : ID (COMMA ID)* COLON type_spec

例如：

5、type_spec

变量声明时的类型。

本篇文章中不做类型检查，所以暂时先只有整数类型。

type_spec : INTEGER

6、没有变化的文法

以下文法较之前没有变化，放在这里帮助大家对文法整体的理解。

compound_statement : BEGIN statement_list END

statement_list : statement | statement SEMI statement_list

statement : compound_statement | assignment_statement | empty

assignment_statement : variable ASSIGN expr

empty :

expr : term ((PLUS | MINUS) term)*

7、term

在我们的程序中，除法将分为整数除法（INTEGER_DIV ）和浮点数除法（FLOAT_DIV）。

term : factor ((MUL | INTEGER_DIV | FLOAT_DIV) factor)*

例如：

15 / 6 = 2.5

15 DIV 6 = 2

8、factor

在我们的程序中数字因子将分为（INTEGER_CONST ）和实数因子（REAL_CONST ）。

提示：实数包含整数与小数。

factor : PLUS factor | MINUS factor | INTEGER_CONST | REAL_CONST | LPAREN expr RPAREN | variable

同时，因为规则的改变，常量也将去除INTEGER，而增加INTEGER_CONST（整数）和REAL_CONST（实数）。

二、更新代码

按以往的套路，有了更新的文法之后，我们就根据文法更新代码。

主要要更新以下内容：

更新词法分析器（Lexer）

更新语法分析器（Parser）

更新解释器（Interpreter）

在进行这些代码更新之前，我们需要先将常量进行更新。包括：

实数类型：REAL（之前的整数INTEGER作为整数类型，无需再添加）

整数：INTEGER_CONST

实数：REAL_CONST

整数除法符号：INTEGER_DIV

浮点数除法符号：FLOAT_DIV

程序标记：PROGRAM

变量声明标记：VAR

逗号：COMMA

冒号：COLON

更新后的常量如下：

INTEGER = 'INTEGER' # 整数类型REAL = 'REAL' # 实数类型INTEGER_CONST = 'INTEGER_CONST' # 整数（因子）REAL_CONST = 'REAL_CONST' # 实数（因子）PLUS = 'PLUS' # 加MINUS = 'MINUS' # 减MUL = 'MUL' # 乘INTEGER_DIV = 'INTEGER_DIV' # 整数除法FLOAT_DIV = 'FLOAT_DIV' # 浮点数除法LPAREN = 'LPAREN' # 左括号RPAREN = 'RPAREN' # 右括号ID = 'ID' # 变量名称ASSIGN = 'ASSIGN' # 赋值符号BEGIN = 'BEGIN' # 开始标记END = 'END' # 结束标记SEMI = 'SEMI' # 分号DOT = 'DOT' # 点（程序结束符）PROGRAM = 'PROGRAM' # 程序VAR = 'VAR' # 变量声明标记COLON = 'COLON' # 冒号COMMA = 'COMMA' # 逗号EOF = 'EOF' # 结束符号

另外，还有保留字需要添加：

VAR：变量声明

DIV：整数除法

PROGRAM：程序

整数类型：INTEGER

实数类型：REAL

更新后的保留字代码如下：

RESERVED_KEYWORDS = { # 保留字 'PROGRAM': Token('PROGRAM', 'PROGRAM'), 'VAR': Token('VAR', 'VAR'), 'DIV': Token('INTEGER_DIV', 'DIV'), 'INTEGER': Token('INTEGER', 'INTEGER'), 'REAL': Token('REAL', 'REAL'), 'BEGIN': Token('BEGIN', 'BEGIN'), 'END': Token('END', 'END'),}

接下来，我们完成代码的更新。

1、更新词法分析器（Lexer）

首先，需要添加跳过注释的方法。

注释以大括号“{”开头和大括号“}”结尾。

所哟，当读取到的字符为大括号“{”时，需要跳过注释内容，当读取到大括号“}”时结束。

示例代码：

def skip_comment(self): # 添加跳过注释内容到的方法 while self.current_char != '}': # 如果当前字符不是注释结束符号 self.advance() # 提取下一个字符 self.advance() # 提取下一个字符（跳过注释结束符号）

然后，我们的程序需要支持整数和浮点数。

当读取到整数字符时，需要向后依次读取字符，如果读取到小数点“.”，就将小数点加入数字字符串中，并继续读取小数点右侧的所有整数，否则直接读取完所有的整数字符。

示例代码：

def number(self): # 添加处理整数和实数的方法 result = '' # 定义保存数字字符串的变量 while self.current_char is not None and self.current_char.isdigit(): # 如果当前字符不是None并且为整数 result += self.current_char # 连接已有数字字符串 self.advance() # 提取下一字符 if self.current_char == '.': # 如果当前字符为小数点 result += self.current_char # 连接已有数字字符串 self.advance() # 提取下一字符 while self.current_char is not None and self.current_char.isdigit(): # 如果当前字符不是None并且为整数（小数点后均为整数） result += self.current_char # 连接已有数字字符串 self.advance() # 提取下一字符 return Token(REAL_CONST, float(result)) # 遍历完小数点右侧所有整数后，返回存储了小数数值的实数记号。 return Token(INTEGER_CONST, int(result)) # 没有小数点时，遍历完所有整数后，返回存储了整数数值的整数记号。

最后，我们更新get_next_token()方法，根据新的常量和词法分析规则更新代码。

def get_next_token(self): while self.current_char is not None: if self.current_char == '{': # 如果当前字符为注释起始标记 self.advance() # 跳过当前字符 self.skip_comment() # 跳过注释内容 continue # 继续获取下一记号 ...省略部分代码... if self.current_char.isdigit(): # 当前字符为整数时 return self.number() # 获取整数或实数记号 if self.current_char == ':': # 当前字符为冒号时 self.advance() # 提取下一字符 return Token(COLON, ':') # 返回冒号记号 if self.current_char == ',': # 当前字符为逗号时 self.advance() # 提取下一字符 return Token(COMMA, ',') # 返回逗号标记 ...省略部分代码... if self.current_char == '/': # 当前字符为斜杠时 self.advance() # 提取下一字符 return Token(FLOAT_DIV, '/') # 返回浮点数除法记号 ...省略部分代码... return Token(EOF, None)

2、更新语法分析器（Parser）

根据新的文法，添加AST类。包括：Program、Block、VarDecl和Type。

示例代码：

class Program(AST): # 定义程序节点 def __init__(self, name, block): # 程序由名称和语句块组成 self.name = name self.block = blockclass Block(AST): # 定义语句块节点 def __init__(self, declarations, compound_statement): # 语句块由声明和符合语句组成 self.declarations = declarations self.compound_statement = compound_statementclass VarDecl(AST): # 定义变量声明节点 def __init__(self, var_node, type_node): # 变量声明由变量和类型组成 self.var_node = var_node self.type_node = type_nodeclass Type(AST): # 定义类型节点 def __init__(self, token): self.token = token self.value = token.value

然后，在语法分析器中添加4个新的方法，用于解析新的语言结构，构造新的AST节点。

这些新的方法包括：block()、declarations()、variable_declaration()和type_spec()。

示例代码：

def block(self): # 构造块节点的方法 declarations = self.declarations() compound_statement = self.compound_statement() node = Block(declarations, compound_statement) # 块节点由声明节点和符合语句节点组成 return nodedef declarations(self): # 构造声明节点的方法 declarations = [] # 声明节点包含多个变量声明节点 if self.current_token.value_type == VAR: # 如果当前记号为变量 self.eat(VAR) # 验证记号 while self.current_token.value_type == ID: # 遍历变量名称 declarations.extend(self.variable_declaration()) # 声明列表中添加变量声明 self.eat(SEMI) # 验证分号 return declarations # 返回声明节点列表def variable_declaration(self): # 构造变量声明节点的方法 var_nodes = [Variable(self.current_token)] # 第一个变量声明节点添加到变量声明节点列表 self.eat(ID) # 验证变量名称记号 while self.current_token.value_type == COMMA: # 遍历逗号 self.eat(COMMA) # 验证逗号 var_nodes.append(Variable(self.current_token)) # 添加变量节点到变量节点列表 self.eat(ID) # 验证变量名称记号 self.eat(COLON) # 验证冒号 type_node = self.type_spec() # 一组变量声明的类型节点 var_declarations = [VarDecl(var_node, type_node) for var_node in var_nodes] # 生成变量声明列表 return var_declarations # 返回变量声明节点列表def type_spec(self): # 构造变量类型节点的方法 token = self.current_token # 获取当前记号 if token.value_type == INTEGER: # 如果是整数类型 self.eat(INTEGER) # 验证整数记号 else: # 否则 self.eat(REAL) # 验证实数记号 node = Type(token) # 创建类型节点 return node # 返回类型节点

除此之外，根据新的文法，我们还要修改program()方法、term()方法和factor()方法。

示例代码：

def program(self): self.eat(PROGRAM) # 验证程序开始标记 var_node = self.variable() # 获取变量节点 program_name = var_node.name # 获取程序名称 self.eat(SEMI) # 验证分号 block_node = self.block() # 获取块节点 node = Program(program_name, block_node) # 创建程序节点 self.eat(DOT) # 验证程序结束符号 return node # 返回程序节点def term(self): node = self.factor() while self.current_token.value_type in (MUL, INTEGER_DIV, FLOAT_DIV): # 除法修改为整数除法和浮点数除法 token = self.current_token if token.value_type == MUL: self.eat(MUL) elif token.value_type == INTEGER_DIV: # 整数除法 self.eat(INTEGER_DIV) elif token.value_type == FLOAT_DIV: # 浮点数除法 self.eat(FLOAT_DIV) node = BinaryOperator(node, token, self.factor()) return nodedef factor(self): current_token = self.current_token if current_token.value_type == PLUS: ...省略部分代码... elif current_token.value_type == INTEGER_CONST: # 整数 self.eat(INTEGER_CONST) return Num(current_token) elif current_token.value_type == REAL_CONST: # 实数 self.eat(REAL_CONST) return Num(current_token) elif current_token.value_type == LPAREN: ...省略部分代码...

到这里，我们就完成了语法分析器部分的代码更新。

以下方这段Pascal程序为例：

PROGRAM Part10AST;VAR a, b : INTEGER; y : REAL;BEGIN a := 2; b := 10 * a + 10 * a DIV 4; y := 20 / 7 + 3.14;END.

这段程序使用抽象语法树表示，如下图所示：（引用自鲁斯兰博客）

3、更新解释器（Interpreter）

对应着新添加的的4个AST类，我们需要在解释器中添加相应的访问方法：

visit_Program

visit_Block

visit_VarDecl

visit_Type

示例代码：

def visit_Program(self, node): # 添加访问程序的方法 self.visit(node.block) # 访问语句块def visit_Block(self, node): # 添加访问语句块的方法 for declaration in node.declarations: # 遍历声明列表 self.visit(declaration) # 访问声明 self.visit(node.compound_statement) # 访问复合语句def visit_VarDecl(self, node): # 添加访问变量声明的方法 pass # 无需处理def visit_Type(self, node): # 添加访问类型的方法 pass # 无需处理

最后，我们还需要修改visit_BinaryOperator()方法来解释整数除法和浮点数除法。

def visit_BinaryOperator(self, node): if node.operator.value_type == PLUS: return self.visit(node.left) + self.visit(node.right) elif node.operator.value_type == MINUS: return self.visit(node.left) - self.visit(node.right) elif node.operator.value_type == MUL: return self.visit(node.left) * self.visit(node.right)elif node.operator.value_type == INTEGER_DIV: # 如果是整数除法return self.visit(node.left) // self.visit(node.right) # 返回整数除法运算结果elif node.operator.value_type == FLOAT_DIV: # 如果是浮点数除法return self.visit(node.left) / self.visit(node.right) # 返回浮点数除法运算结果

当我们完成以上全部代码，就可以对文章开始的Pascal程序进行解释了。

最终显示输出的符号表为：{‘number’: 2, ‘a’: 2, ‘b’: 23, ‘c’: 25, ‘x’: 11, ‘y’: 5.997142857142857}

让我们总结一下，在这一篇文章中都做了什么来完成了Pascal解释器的扩展：

文法中添加了新规则并更新了现有规则；

将新的记号和相关方法添加到词法分析器中，并更新和修改了现有的方法；

将新的AST节点类添加到语法分析器中，以构建新的语言结构；

将新的文法规则对应的新方法添加到了语法分析器中，并更新现有的方法；

将新的访问方法添加到了解释器中，并更新现有访问方法。

通过这些变化，我们也解决了上一篇文章中提到的一些程序缺陷，实现了以下内容：

解释器现在可以处理程序头；

变量现在可以使用VAR关键字来声明；

DIV关键字用于整数除法，斜杠“/”用于浮点数除法。

练习：重新实现解释器而不看源代码，并使用文章开头的Pascal程序进行测试。

在下一篇文章中，我们将更深入的学习关于符号表的管理。