如何写一个简单的解释器（Interpreter）-9

今天要如何解析和解释Pascal语言的定义、复合语句、赋值语句、变量。还要聊聊符号表以及存储和查找变量。

BEGIN
    BEGIN
        number := 2;
        a := number;
        b := 10 * a + 10 * number / 4;
        c := a - - b
    END;
    x := 11;
END.

你看，不只是数学计算了，还多了一些眼熟的编程语言或者说计算机系学生特有的知识：

Pascal程序的定义是一串复合的语句，加上一个句号。比如：
```
“BEGIN  END.”
           
```
事先声明，这并不是一个完整的程序声明，后面会扩充它。
复合语句是什么意思呢？一个复合语句指的是一块代码，被BEGIN和END包起来的一系列语句，也可以是其他复合语句。在复合语句中的每一个语句，除了最后一个，都是分号结束的。最后一个语句可能有，也能没有分号。下面是一些例子：

“BEGIN END”
“BEGIN a := 5; x := 11 END”
“BEGIN a := 5; x := 11; END”
“BEGIN BEGIN a := 5 END; x := 11 END”

可以看到：

语句列表是一系列的语句。
一个语句，可以是一个符合语句，一个赋值语句，也可以是一个空语句。
赋值语句就是一个变量后面跟着赋值token，也就是一个冒号一个等号。比如 “a := 11” “b := a + 9 - 5 * 2”
一个变量是一个标识符。我们使用ID token来表示变量。token的值是一个变量的名字，比如a、number等等。这个a和b就是变量。“BEGIN a := 11; b := a + 9 - 5 * 2 END”
空的语句表示不再继续产生新的东西了。在解析器里，我们使用empty_statement语法规则去表示语句列表的结束，空语句用‘’BEGIN END‘’表示。
factor规则也升级了，可以处理变量了。

完整的语法是这么严肃的表示的：

program : compound_statement DOT

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

    factor : PLUS factor
           | MINUS factor
           | INTEGER
           | LPAREN expr RPAREN
           | variable

    variable: ID

You probably noticed that I didn’t use the star ‘*’ symbol in the compound_statement rule to represent zero or more repetitions, but instead explicitly specified the statement_listrule. This is another way to represent the ‘zero or more’ operation, and it will come in handy when we look at parser generators like PLY, later in the series. I also split the “(PLUS | MINUS) factor” sub-rule into two separate rules.

compound_statement里面并没有使用星星号，相反，“重复”这种表达方式是直接写入了statement_list规则。这是另一种表达0个或者多个的表达方式。另外，我把(PLUS | MINUS)factor这个规则分解成了两个子规则。

In order to support the updated grammar, we need to make a number of changes to our lexer, parser, and interpreter. Let’s go over those changes one by one.

为了支持更新后的语法，我们需要针对lexer、parser和interpreter做出大量的改动。

词法分析器的改动如下：

如何写一个简单的解释器（Interpreter）-9

值得一提的是新的token里有一个SEMI，这个token代表一个复合语句中的多条语句的分隔符。另一个值得一提的token是ID，是一个表示有效标识符的token。

有时候，我们需要区分不同的字符，比如‘:’ vs ‘:=’ vs ‘==’ vs ‘=>’。我们需要偷窥一下缓存区，这时候并不是想真正去读取这个缓存区。为了这个目的，我引入了一个peek方法，它的引入也会让get_next_token方法的实现更简洁一些。peek方法的作用只有一个，就是在self.pos变量不增长得情况下读取下一个字符。

peek方法的定义如下：

def peek(self):
    peek_pos = self.pos + 1
    if peek_pos > len(self.text) - 1:
        return None
    else:
        return self.text[peek_pos]

因为Pascal的变量和保留字都是识别码，所以我们把它们的处理合并到同一个函数里面，就是_id方法。工作原理是：词法分析器读取一字母和数组的字符串序列，并检查这个字符序列是不是一个保留字。如果是保留字，词法分析器就返回预定义的一个token来表示那个保留字，否则lexer就返回一个新的ID token，值是字符自己，英文叫lexeme。这个过程的代码是：

RESERVED_KEYWORDS = {

'BEGIN': Token('BEGIN', 'BEGIN'),
 'END': Token('END', 'END'),
 }

 def _id(self):
 """Handle identifiers and reserved keywords"""
 result = ''
 while self.current_char is not None and self.current_char.isalnum():
 result += self.current_char
 self.advance()

 token = RESERVED_KEYWORDS.get(result, Token(ID, result))
 return token

get_next_token方法的代码是：

def get_next_token(self):
    while self.current_char is not None:
        ...
        if self.current_char.isalpha():
            return self._id()

        if self.current_char == ':' and self.peek() == '=':
            self.advance()
            self.advance()
            return Token(ASSIGN, ':=')

        if self.current_char == ';':
            self.advance()
            return Token(SEMI, ';')

        if self.current_char == '.':
            self.advance()
            return Token(DOT, '.')
        ...

试验一下我们的词法解析器。

>>> from spi import Lexer
>>> lexer = Lexer('BEGIN a := 2; END.')
>>> lexer.get_next_token()
Token(BEGIN, 'BEGIN')
>>> lexer.get_next_token()
Token(ID, 'a')
>>> lexer.get_next_token()
Token(ASSIGN, ':=')
>>> lexer.get_next_token()
Token(INTEGER, 2)
>>> lexer.get_next_token()
Token(SEMI, ';')
>>> lexer.get_next_token()
Token(END, 'END')
>>> lexer.get_next_token()
Token(DOT, '.')
>>> lexer.get_next_token()
Token(EOF, None)
>>>

继续，解析器的改动如下：

如何写一个简单的解释器（Interpreter）-9

让我们从新的ADT节点开始：

复合AST节点指的是孩子是一系列表达式的节点。

class Compound(AST):
    """Represents a 'BEGIN ... END' block"""
    def __init__(self):
        self.children = []

赋值AST节点指的是赋值语句。left变量存放着Var节点，right变量存放着expr parser方法的返回值。

class Assign(AST):
    def __init__(self, left, op, right):
        self.left = left
        self.token = self.op = op
        self.right = right

Var AST节点指的是一个变量。 self.value 存放的是变量的名字。

class Var(AST):
    """The Var node is constructed out of ID token."""
    def __init__(self, token):
        self.token = token
        self.value = token.value

NoOp 节点存放空语句。比如 ‘BEGIN END’ 就是一个合法的组合语句，它包含了空语句。
```
class NoOp(AST):
    pass
           
```

你一定还记得，语法中的每一个规则在解析器的实现里，都有一个对应的方法。这次我们要增加更多的方法。这些方法负责解析新的语言结构，来构建新的AST节点，其实很容易的：

def program(self):
    """program : compound_statement DOT"""
    node = self.compound_statement()
    self.eat(DOT)
    return node

def compound_statement(self):
    """
    compound_statement: BEGIN statement_list END
    """
    self.eat(BEGIN)
    nodes = self.statement_list()
    self.eat(END)

    root = Compound()
    for node in nodes:
        root.children.append(node)

    return root

def statement_list(self):
    """
    statement_list : statement
                   | statement SEMI statement_list
    """
    node = self.statement()

    results = [node]

    while self.current_token.type == SEMI:
        self.eat(SEMI)
        results.append(self.statement())

    if self.current_token.type == ID:
        self.error()

    return results

def statement(self):
    """
    statement : compound_statement
              | assignment_statement
              | empty
    """
    if self.current_token.type == BEGIN:
        node = self.compound_statement()
    elif self.current_token.type == ID:
        node = self.assignment_statement()
    else:
        node = self.empty()
    return node

def assignment_statement(self):
    """
    assignment_statement : variable ASSIGN expr
    """
    left = self.variable()
    token = self.current_token
    self.eat(ASSIGN)
    right = self.expr()
    node = Assign(left, token, right)
    return node

def variable(self):
    """
    variable : ID
    """
    node = Var(self.current_token)
    self.eat(ID)
    return node

def empty(self):
    """An empty production"""
    return NoOp()

factor 方法也需要升级一下，来解析变量。

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

解析器的 parse 方法也升级了，从一个程序的定义处开始解析。

def parse(self):
    node = self.program()
    if self.current_token.type != EOF:
        self.error()

    return node

回顾一下我们的Pascal程序源代码：

BEGIN
    BEGIN
        number := 2;
        a := number;
        b := 10 * a + 10 * number / 4;
        c := a - - b
    END;
    x := 11;
END.

用 genastdot.py 来显示一下AST树形结构。

$ python genastdot.py assignments.txt > ast.dot && dot -Tpng -o ast.png ast.dot

如何写一个简单的解释器（Interpreter）-9

最后，是解释器代码的改动：

如何写一个简单的解释器（Interpreter）-9

为了解释新的AST节点，我们增加了下列visit_方法：

visit_Compound
visit_Assign
visit_Var
visit_NoOp

Compound 和 NoOp visitor 方法很简单，visit_Compound方法按顺序访问它的孩子节点，visit_NoOp 方法则什么都不做。

def visit_Compound(self, node):
    for child in node.children:
        self.visit(child)

def visit_NoOp(self, node):
    pass

Assign 和 Var visitor 方法值得深入研究一下。

visit_Assign 方法做了一件事——为了把一个数值赋值给变量，需要找个地方把数值存起来备用。

def visit_Assign(self, node):
    var_name = node.left.value
    self.GLOBAL_SCOPE[var_name] = self.visit(node.right)

这个方法在符号表 GLOBAL_SCOPE中存放了一个个的键值对。符号表在Python里用字典实现。

比如 “a := 3;” 的计算过程——符号表在visit_Assign方法执行前后的状态变化如下：

如何写一个简单的解释器（Interpreter）-9

另一个例子，“b := a + 7;”。

如何写一个简单的解释器（Interpreter）-9

赋值语句的右边是a+7。里面涉及到一个变量a。我们需要用visit_Var方法来找到a的值，然后才能计算a+7的值。

计算a的值就需要在符号表里面去查找a。如果找不到要抛异常。

def visit_Var(self, node):
    var_name = node.value
    val = self.GLOBAL_SCOPE.get(var_name)
    if val is None:
        raise NameError(repr(var_name))
    else:
        return val

如何写一个简单的解释器（Interpreter）-9

我们用python命令行来打印一些我们的新的解释器的内部函数和数据吧。

$ python
>>> from spi import Lexer, Parser, Interpreter
>>> text = """\
... BEGIN
...
...     BEGIN
...         number := 2;
...         a := number;
...         b := 10 * a + 10 * number / 4;
...         c := a - - b
...     END;
...
...     x := 11;
... END.
... """
>>> lexer = Lexer(text)
>>> parser = Parser(lexer)
>>> interpreter = Interpreter(parser)
>>> interpreter.interpret()
>>> print(interpreter.GLOBAL_SCOPE)
{'a': 2, 'x': 11, 'c': 27, 'b': 25, 'number': 2}

目前的实现还有有些限制，如下所示。以后的章节我们会一一解决它们。比如program的定义不完整，变量没有声明，没有类型检查机制，符号表占用内存过大，使用“/”符号而不是div来表示整数的除法，没有区分大小写。

如何写一个简单的解释器（Interpreter）-9

如何写一个简单的解释器（Interpreter）-9

继续阅读

What else is new in C# 5?

:linux内核编译过程的最终总结版

Linux 内核编译全功略

apache+sqlite+php for Arm Linux(转)

Eclipse 整合 Resin

认识 C++ 中的 explicit 关键字

谈谈explicit关键字

Passing parameters to a Jasper report

无法将匿名方法转换为类型“System.Delegate”，因为它不是委托类型

上周技术关注：软件的力量

[转贴]Linux下Makefile的automake生成全攻略[-]

Windows Mobile 进阶系列.第一回.真的了解.NET CF吗?

GBA C/C++ Programming tutorial ---Lesson 1Gameboy Advance (GBA)

命令行编译C程序

error C2143: syntax error : missing ';' before 'type' in Visual C++

VS2008 不在支持 Attributed ATL