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

Posted on | Comments:

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

不怕慢，就怕停。 ── 中国谚语

嗨，欢迎回来！

今天我们会多走几步并学习怎样解析 Pascal 过程声明。

Figure 1: babysteps

什么是一个 过程声明 ？过程声明是一个定义一个标识符（过程名）的语言结构，它将该 标识符与一个 Pascal 代码块关联起来。

在深入之前，先说一点 Pascal 过程和它的声明：

  • Pascal 过程没有返回语句。他们在到达相应代码块结尾时退出。
  • Pascal 过程可以互相嵌套。
  • 为了简单，本文中的过程声明不会有正式的参数。不过别担心，在后续文章中会解决这个 问题的。

下面是今天的测试程序： 

1
PROGRAM Part12;
VAR
   a : INTEGER;

PROCEDURE P1;
VAR
   a : REAL;
   k : INTEGER;

   PROCEDURE P2;
   VAR
      a, z : INTEGER;
   BEGIN {P2}
      z := 777;
   END;  {P2}

BEGIN {P1}

END;  {P1}

BEGIN {Part12}
   a := 10;
END.  {Part12}

从上面可以看出，我们定义了两个过程（P1和P2）且 P2 是嵌套在 P1 里的。在上面的代码 中，我在注释中用过程名来清楚地表示每个过程的开始和结束位置。

我们今天的目标很明确：学习怎样解析这样的代码。

首先，我们需要对语法进行一些修改以添加过程声明。好了，让我们动手吧！

下面是修改过的语法规则：

Figure 2: grammar

declarations : VAR (variable_declaration SEMI)+
             | (PROCEDURE ID SEMI block SEMI)*
             | empty

过程声明子规则包含了保留关键字 PROCEDURE 后跟一个标识符（过程名），后跟一个分 号，后再跟一个 block 规则，最后由分号结尾。哇！这里我觉得，不管上句话说得多好 都不如一幅图能说清楚！：）

下面是规则 declarations 修改后的句法图：

Figure 3: syntaxdiagram

从语法和上面的图中可以看出，在同一级别你可以有任意多的过程声明。例如，在下面的代 码片段中我们在同一级别上定义了两个过程声明，P1 和 P1A： 

1
PROGRAM Test;
VAR
   a : INTEGER;

PROCEDURE P1;
BEGIN {P1}

END;  {P1}

PROCEDURE P1A;
BEGIN {P1A}

END;  {P1A}

BEGIN {Test}
   a := 10;
END.  {Test}

上面的句法图和语法规则也表明了过程声明可以嵌套，因为 procedure declaration 子 规则引用了 block=规则，而 =block 规则包含了 declarations 规则，而 declarations 规则反过来又包含了 procedure declaration 子规则。作为提醒，下面 是第十部分中 block 规则的句法图和语法：

Figure 4: block rule from part10

好了，现在让我们把注意力集中在解释器中需要修改以支持过程声明的部分上:

更新 Lexer

我们只需要增加一个名为 PROCEDURE 的 token： 

1
PROCEDURE = 'PROCEDURE'

并将 ‘PROCEDURE’ 添加到保留关键字中。下面是完整的保留关键字到 token 的映射： 

1
2
3
4
5
6
7
8
9
10
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'),
    'PROCEDURE': Token('PROCEDURE', 'PROCEDURE'),
}

更新 Parser

下面是 parser 所要做修改的概述：

  1. 新的 ProcedureDecl AST 结点
  2. 修改 parser 的 declarations 方法以支持过程声明

让我们看一下这些修改。

  1. ProcedureDecl AST 结点代表了一个过程声明。它的构建函数接受过程名和代码块的 AST 结点作为参数。 

    1
    2
    3
    4
    class ProcedureDecl(AST):
        def __init__(self, proc_name, block_node):
    	self.proc_name = proc_name
    	self.block_node = block_node

  2. 下面是 Parser 类中修改过的 declarations 方法 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    def declarations(self):
        """declarations : VAR (variable_declaration SEMI)+
    		    | (PROCEDURE ID SEMI block 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)

        while self.current_token.type == PROCEDURE:
    	self.eat(PROCEDURE)
    	proc_name = self.current_token.value
    	self.eat(ID)
    	self.eat(SEMI)
    	block_node = self.block()
    	proc_decl = ProcedureDecl(proc_name, block_node)
    	declarations.append(proc_decl)
    	self.eat(SEMI)

        return declarations

    希望上面的代码是无需解释的。它符合文章前面的过程声明的语法/句法图。

更新符号表构建器

我们还需要在 Interpreter 类中增加一个新的空的 visit_ProcedureDecl 方法，它会 让我们的解释器忽略所有的过程声明。

到现在为止还不错。

既然我们已经做了所有必要的修改，让我们看一看加入新的 ProcedureDecl 结点后抽象 语法树是什么样的。

下面又是我们的 Pascal 程序（你可以直接从 GitHub 下载）： 

1
PROGRAM Part12;
VAR
   a : INTEGER;

PROCEDURE P1;
VAR
   a : REAL;
   k : INTEGER;

   PROCEDURE P2;
   VAR
      a, z : INTEGER;
   BEGIN {P2}
      z := 777;
   END;  {P2}

BEGIN {P1}

END;  {P1}

BEGIN {Part12}
   a := 10;
END.  {Part12}

让我们生成一个 AST 然后用程序 genastdot.py 来可视化一下： 

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

Figure 5: procdecl ast

在上面的图片中你可以看到两个 ProcedureDecl 结点：ProcDecl:P1 和 ProcDecl:P2 分 别对应于过程 P1 和 P2。任务完成。：）

作为今天最后一项，让我们像以前一样快速地检查一下我们修改过的解释器，这次这个 Pascal 程序里包含了过程声明。如果你还没下载解释器和测试程序，下载下来并在命令行 上运行它。输出应该像下面这样： 

$ python spi.py part12.pas
Define: INTEGER
Define: REAL
Lookup: INTEGER
Define: <a:INTEGER>
Lookup: a

Symbol Table contents:
Symbols: [INTEGER, REAL, <a:INTEGER>]

Run-time GLOBAL_MEMORY contents:
a = 10

好了，在掌握了这些知识和经验的基础上，我们已经准备好解决嵌套作用域的问题，我们需 要理解它来使得我们可以分析嵌套作用域，并帮助我们做好处理过程和函数调用的准备。而 这正是我们下一篇文章中要做的：深入到嵌套作用域中。所以下次别忘了带上游泳装备！敬 请关注，下次再见！

本系列的所有文章：

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