[译]Let’s Build A Simple Interpreter. Part 10.

原文地址：Let’s Build A Simple Interpreter. Part 10.

今天我们会继续我们当前与想要到达的目标(一个功能齐全的 Pascal 语言子集的解释器)之间的差距。

Figure 1: intro

在本文中我们修改我们的解释器来解析和解释我们第一个完整的 Pascal 程序。这个程序也可以被 Free Pascal compiler, fpc 编译。

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 4;
      c := a - - bb
   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}

在深入细节之前，从 GitHub 上面下载该解释器的源代码以及上面的 Pascal 源代码，然后在命令行上尝试一下：

1	$ python spi.py part10.pas a = 2 b = 25 c = 27 number = 2 x = 11 y = 5.99714285714

如果我删除文件 part10.pas 中 writeln 语句的注释符，再使用 fpc 编译该源码然后运行产生的可执行文件，在我的电脑上得到了下面的输出：

1	$ fpc part10.pas $ ./part10 a = 2 b = 25 c = 27 number = 2 x = 11 y = 5.99714285714286E+000

好了，让我们看看今天会讲哪些内容：

我们会学习怎样解析和解释 Pascal PROGRAM 头部
我们会学习怎样解析变量声明
我们会更新我们的解释器使它使用 DIV 关键字表示整数除法，使用斜杠/表示浮点数除法
我们会增加对 Pascal 注释的支持

让我们先看看语法的变化。今天我们会增加一些新的规则并更新一些现有的规则。

Figure 2: grammar1

Figure 3: grammar2

program 语法规则的定义更新为了包含 PORGRAM 保留关键字，程序名，和一个点号结尾的 block。下面是一个完整 Pascal 程序的例子：
1
PROGRAM Part10; BEGIN END.
block 规则将 declarations 规则和 compound_statement 规则组合在一起。我们还会在后面增加过程声明的时候用到这条规则。下面是一个 block 的例子：
1
VAR number : INTEGER; BEGIN END
再来一个例子：
1
BEGIN END
Pascal 的 declarations 有几个部分组成，且每个部分都是可选的。在本文中，我们只会使用变量声明这部分。 declarations 规则要么有一个 variable_declaration 子规则，要么为空。
Pascal 是一门静态有类型语言，意味着每个变量都需要一个变量声明来指定它的类型。在 Pascal 中，变量必须在使用之前声明。这通过在程序的 variable_declaration 部分使用保留关键字 VAR 来实现。你可以使用如下方式定义变量：
1
VAR number : INTEGER; a, b, c, x : INTEGER; y : REAL;
type_spec 规则用来处理类型 INTEGER 和 REAL 以及在变量声明时使用。在下面的例子中
1
VAR a : INTEGER; b : REAL;
变量“a”被声明为类型 INTEGER 而变量 “b”被声明为了类型 REAL(float)。在本文中，我们不会强制类型检查，但在后续文章中会加入。
term 规则修改为了使用关键字 DIV 表示整数除法以及用斜杠/表示浮点数除法。

之前，20 除以 7 使用斜杠会产生一个整数 2:
```
20 / 7 = 2
```
现在，20 除以 7 使用斜杠会产生一个实数（浮点数） 2.85714285714 :
```
20 / 7 = 2.85714285714
```
从现在起，要得到一个整数而非实数，你需要使用 DIV 关键字：
```
20 DIV 7 = 2
```
factor 规则更新为了同时处理整数和实数（浮点数）常量。我还移除了子规则 INTEGER，因为常量会用 token INTEGER_CONST 和 REAL_CONST 来表示，token INTEGER 会被用来表示整数类型。在下面的例子中 lexer 会为 20 和 7 生成一个 INTEGER_CONST token，为 3.14 生成一个 REAL_CONST token：
1
y := 20 / 7 + 3.14;

下面是我们今天的完整语法：

program : PROGRAM variable SEMI block DOT

block : declarations compound_statement

declarations : VAR (variable_declaration SEMI)+
             | empty

variable_declaration : ID (COMMA ID)* COLON type_spec

type_spec : INTEGER
          | REAL

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)*

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

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

variable : ID

在文章的剩下部分，我们会使用和上次一样的方式：

修改 lexer
修改 parser
修改 interpreter

更新 Lexer

以下是 lexer 变化的概览：

新的 token
新的和修改过的保留关健字
新的 skep_comments 方法，用来处理 Pascal 注释
重命名 integer 方法并做一些修改
更新 get_next_token 方法使它能返回新的 token

让我们深入到这些修改之中：

为了处理程序头，变量声明，整数和浮点数常量，以及整数和浮点数除法，我们需要增加一些新的 token ── 其中一些是关键字 ── 而且我们修改 INTEGER 的意义使它表示整数类型而非一个整型常量。下面是新增的和要修改的 token 的完整列表：
- PROGRAM (保留关键字)
- VAR (保留关键字)
- COLON (:)
- COMMA (,)
- INTEGER (我们要让它表示整数类型而不是像 3 或 5 这样的整型常量)
- REAL (表示 Pascal 的 REAL 类型)
- INTEGER_CONST (如，3 或 5)
- REAL_CONST (如，3.14 等)
- INTEGER_DIV 表示整数除法(保留关键字 DIV)
- FLOAT_DIV 表示浮点数除法(斜杠/)

以下是保留关键字到 token 的完整映射：

RESERVED_KEYWORDS = {
    'PROGRAM': Token('PROGRAM', 'PROGRAM'),
    'VAR': Token('VAR', 'VAR'),
    'DIV': Token('DIV', 'DIV'),
    'INTEGER': Token('INTEGER', 'INTEGER'),
    'REAL': Token('REAL', 'REAL'),
    'BEGIN': Token('BEGIN', 'BEGIN'),
    'END': Token('END', 'END'),
}

增加 skip_comment 方法来处理 Pascal 注释。该方法很简单，它只是丢弃到结束花括号之前的所有字符：

def skip_comment(self):
    while self.current_char != '}':
	self.advance()
    self.advance()  # the closing curly brace

把 integer 方法重命名为 number. 它可以处理整型和浮点型常量如 3 或 3.14 :

def number(self):
    """Return a (multidigit) integer or float consumed from the input."""
    result = ''
    while self.current_char is not None and self.current_char.isdigit():
	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():
	    result += self.current_char
	    self.advance()

	token = Token('REAL_CONST', float(result))
    else:
	token = token('INTEGER_CONST', int(result))
    return token

我们还需要修改 get_next_token 方法使它能返回新的 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, '/')
	...

更新 Parser

现在来看看 parser 的修改。

下面是所有修改的概览：

新的 AST 结点： Program, Block, VarDecl, Type
根据新语法产生的新方法：block, declarations, variable_declaration, type_spec.
更新现有的方法：program, term, factor

让我们一个一个来看：

我们从新的 AST 结点说起。一个有 4 个新结点：

AST 结点 Program 表示一个程序，它将会是我们的根结点

class Program(AST):
    def __init__(self, name, block):
	self.name = name
	self.block = block

AST 结点 Block 会保存声明和一个复合语句：

class Block(AST):
    def __init__(self, declarations, compound_statement):
	self.declarations = declarations
	self.compound_statement = compound_statement

AST 结点 VarDecl 表示一个变量声明。它保存一个变量结点和一个类型结点：

class VarDecl(AST):
    def __init__(self, var_node, type_node):
	self.var_node = var_node
	self.type_node = type_node

AST 结点 Type 表示一个变量类型（INTEGER 或 REAL）：

class Type(AST):
    def __init__(self, token):
	self.token = token
	self.value = token.value

你可能还记得，语法中的每条规则都在我们的递归下降 parser 里有一个相应的方法。今天我们会添加 4 个新方法：block, declarations, variable_declaration, 和 type_spec. 这些方法负责解析新的语言结构及构建新的 AST 结点：

def block(self):
    """block : declarations compound_statement"""
    declaration_nodes = self.declarations()
    compound_statement_node = self.compound_statement()
    node = Block(declaration_nodes, compound_statement_node)
    return node

def declarations(self):
    """declarations : VAR (variable_declaration SEMI)+
		    | empty
    """
    declarations = []
    if self.current_token.type == VAR:
	self.eat(VAR)
	while self.current_token.type == ID:
	    var_decl = self.variable_declaration()
	    declarations.extend(var_decl)
	    self.eat(SEMI)

    return declarations

def variable_declaration(self):
    """variable_declaration : ID (COMMA ID)* COLON type_spec"""
    var_nodes = [Var(self.current_token)]  # first ID
    self.eat(ID)

    while self.current_token.type == COMMA:
	self.eat(COMMA)
	var_nodes.append(Var(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):
    """type_spec : INTEGER
		 | REAL
    """
    token = self.current_token
    if self.current_token.type == INTEGER:
	self.eat(INTEGER)
    else:
	self.eat(REAL)
    node = Type(token)
    return node

我们还需要修改 program, term, factor 这些方法来适应我们修改过的语法：

def program(self):
    """program : PROGRAM variable SEMI block DOT"""
    self.eat(PROGRAM)
    var_node = self.variable()
    prog_name = var_node.value
    self.eat(SEMI)
    block_node = self.block()
    program_node = Program(prog_name, block_node)
    self.eat(DOT)
    return program_node

def term(self):
    """term : factor ((MUL | INTEGER_DIV | FLOAT_DIV) factor)*"""
    node = self.factor()

    while self.current_token.type in (MUL, INTEGER_DIV, FLOAT_DIV):
	token = self.current_token
	if token.type == MUL:
	    self.eat(MUL)
	elif token.type == INTEGER_DIV:
	    self.eat(INTEGER_DIV)
	elif token.type == FLOAT_DIV:
	    self.eat(FLOAT_DIV)

	node = BinOp(left=node, op=token, right=self.factor())

    return node

def factor(self):
    """factor : PLUS factor
	      | MINUS factor
	      | INTEGER_CONST
	      | REAL_CONST
	      | LPAREN expr RPAREN
	      | variable
    """
    token = self.current_token
    if token.type == PLUS:
	self.eat(PLUS)
	node = UnaryOp(token, self.factor())
	return node
    elif token.type == MINUS:
	self.eat(MINUS)
	node = UnaryOp(token, self.factor())
	return node
    elif token.type == INTEGER_CONST:
	self.eat(INTEGER_CONST)
	return Num(token)
    elif token.type == REAL_CONST:
	self.eat(REAL_CONST)
	return Num(token)
    elif token.type == LPAREN:
	self.eat(LPAREN)
	node = self.expr()
	self.eat(RPAREN)
	return node
    else:
	node = self.variable()
	return node

现在，让我们看看加上新结点后 抽象语法树 长什么样。下面是一个小的可运行的 Pascal 程序：

1	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}

让我们用 genastdot.py 来生成一个 AST 看一下：

1	$ python genastdot.py part10ast.pas > ast.dot && dot -Tpng -o ast.png ast.dot

Figure 4: ast

在这幅图中你可以看到我们加入的新结点。

更新 Interpreter

lexer 和 parser 的变化说完了。剩下的就是添加新的 visitor 方法到 Interpreter 类中。一共有 4 个新的访问结点的方法：

visit_Program
visit_Block
visit_VarDecl
visit_Type

他们都很直截了当。可以看到 Interpreter 并未对 VarDecl 和 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):
    # Do nothing
    pass

def visit_Type(self, node):
    # Do nothing
    pass

我们还需要修改 visit_BinOp 方法来解释整数和浮点数除法：

def visit_BinOp(self, node):
    if node.op.type == PLUS:
	return self.visit(node.left) + self.visit(node.right)
    elif node.op.type == MINUS:
	return self.visit(node.left) - self.visit(node.right)
    elif node.op.type == MUL:
	return self.visit(node.left) * self.visit(node.right)
    elif node.op.type == INTEGER_DIV:
	return self.visit(node.left) // self.visit(node.right)
    elif node.op.type == FLOAT_DIV:
	return float(self.visit(node.left)) / float(self.visit(node.right))

让我们总结一下在这篇文章中为了扩展 Pascal 解释器都做了哪些工作：

向语法中增加新的规则并更新了现有的一些规则
向 lexer 增加新的 token 和相应方法，更新并修改一些现有的方法
根据新的语言结构向 parser 增加新的 AST 结点
根据新的语法规则向我们的递归下降 parser 增加新的并更新现有的方法
向 interpreter 增加新的并更新一个现有的 visitor 方法

结果我们的修改也使我们摆脱了一些第九部分引入的权益之处，即：

我们的 interpreter 现在可以处理 PROGRAM 头部
现在可以用 VAR 关键字来声明变量
关键字 DIV 用于整数除法及斜杠/用于浮点数除法

如果你还没有自觉地做的话，就把重新实现一下本文中的 interpreter 作为练习吧，不要参考源代码，用 par10.pas 作为你的输入文件。

今天就到这。在下一篇文章中，我会详细讨论一下符号表管理。敬请关注，下次再见！

顺便说一下，我还在写一本书“et’s Build A Web Server: First Steps”，解释了怎么从头写一个基本的 Web 服务器。你可以从这里，这里和这里来感受一下这本书。

本系列的所有文章：

Last Updated 2018-05-26 Sat 14:12.
Render by hexo-renderer-org with Emacs 25.2.2 (Org mode 9.1.13)