本系列文章参考国外编程高手鲁斯兰的博客文章《Let’s Build A Simple Interpreter》。
还记得在第7部分提到的最终目标吗？
实现一个Pascal编程语言子集的全功能解释器。
这一篇文章，我们将朝着我们的最终目标更进一步。
我们将更新我们的解释器来解析和解释我们的第一个完整的Pascal程序。
我们先来看一下要解释的Pascal程序代码：
PROGRAM Part10;
VAR
number : INTEGER;
a, b, c, x : INTEGER;
y : REAL;
BEGIN {Part10}
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. {Part10}
在上方代码中，出现了我们之前没有接触过的内容。
实际上这些内容比较简单易懂，主要包括：
- 程序头
- 变量声明
- 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 = block
class Block(AST): # 定义语句块节点
def __init__(self, declarations, compound_statement): # 语句块由声明和符合语句组成
self.declarations = declarations
self.compound_statement = compound_statement
class VarDecl(AST): # 定义变量声明节点
def __init__(self, var_node, type_node): # 变量声明由变量和类型组成
self.var_node = var_node
self.type_node = type_node
class Type(AST): # 定义类型节点
def __init__(self, token):
self.token = token
self.name = 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 node
def 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 node
def 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 {Part10AST}
a := 2;
b := 10 * a + 10 * a DIV 4;
y := 20 / 7 + 3.14;
END. {Part10AST}
这段程序使用抽象语法树表示，如下图所示：（引用自鲁斯兰博客）
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程序进行测试。
在下一篇文章中，我们将更深入的学习关于符号表的管理。
项目源代码下载：【点此下载】
转载请注明：魔力Python » 一起来写个简单的解释器（10）