一起来写个简单的解释器

本系列文章参考国外编程高手鲁斯兰的博客文章《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程序进行测试。

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180725A0I9LQ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券