如何寫一個簡單的解釋器（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