let's build a simple interpreter 1(转)(翻)

让我们构建一个简单的解释器（1）

原文链接：https://ruslanspivak.com/lsbasi-part1/

“If you don’t know compilers work,then you don’t know how computers work. If you’re not 100% sure whether you know how compilers work,then you don’t know how they work.”
–Steve Yegge

好吧，各位。想想上面这句话，无论你是一个菜鸟还是一个资深的软件开发工程师，如果你不懂编译器和解释器是如何工作的，那么你就不会知道计算机是如何工作的。这应该很容易理解。

所以，你知道编译器或者解释器是如何工作的吗？好吧，我的意思是你真的百分百确定你知道他是如何工作的吗？如果你不知道

I don't

或者你知道并因此而感到焦虑

OMG

不要担心。如果你能够坚持走完这一系列的学习并且和我一起构建一个解释器和编译器，那么最后你就能够知道它们是怎么工作的。同时，我也希望因此你能够感到快乐且增加自信。

happy

我们为什么要学习解释器和编译器？我将会给出以下三个理由。

1.编写一个解释器或编译器，需要结合使用大量的专业技能。编写解释器和编译器，将会帮助你提高那些专业技能并且成为一个更好地软件开发者。这些你通过这种方式学到的技能，将会对你写任何软件都将有所帮助，而不仅仅只限于解释器或编译器。

2.你真的非常想要知道计算机是如何工作的。解释器和编译器经常被视为一种魔术，而你不应该满足于简单运用它们。你想要揭开解释器和编译器的面纱，并且能够熟练运用它们。

3.你想要创造一个你自己的编程语言或者领域特定语言。如果你创造了一个语言，那么你也就需要为这种语言编写一个解释器或编译器。最近，新型编程语言的研究又引起了一大波热潮。你甚至几乎每天都能够看到一种新型语言蹦出来，比如Elixir、Go、Rust等。

好了，那么解释器和编译器到底是什么呢？

一个解释器和编译器的目标就是将用高级语言编写的源程序翻译成另一种形式。是不是解释的相当含糊？再忍耐一下吧，之后的文章中，你就会学到如何将源程序进行翻译的了。

在这里，就让我先来解释一下编译器和解释器到底有什么区别吧。如果一个翻译器将源程序代码翻译成机器语言，那么这就是一个编译器。如果一个翻译器没有将源代码翻译成机器语言，就处理并且运行了源代码，那么这就是一个解释器。大概看起来就如下图所示：

compiler and interpreter

我希望到现在为止你很确信你真的想要学习并且构建一个解释器和编译器。那么你可以从这一个关于解释器的系列中的学习到什么呢？

直说吧，我打算一起去为Pascal语言的一个大子集实现一个简单的解释器。在这一系列的最后，你将会拥有一个Pascal的解释器，这个解释器还能够从源代码级别进行调试，就像Python的pdb一样。

你可能会问，为什么是Pascal？首先，这不是一个虚无的语言，所以我选择它在这个系列中使用：这是一个真实使用的编程语言并且拥有许多重要语言结构。虽然有些老，却非常实用，CS书籍使用Pascal编程语言作为他们的示范样例（虽然这个理由不是很充分，但是我想这也是一个学习一种非主流语言的好机会）。

这里是一个使用Pascal的阶乘函数。通过你自己的解释器，你将能够解释执行并且进行调试源代码程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
program factorial;

function factorial(n: integer): longint;
begin
    if n = 0 then
        factorial := 1
    else
        factorial := n * factorial(n - 1);
end;

var
    n: integer;

begin
    for n := 0 to 16 do
        writeln(n, '! = ', factorial(n));
end.

我们实现Pascal解释器的语言将会是Python，但是你能够使用任何语言，因为解释器的实现并不依赖于语言的特性。Okay，该开始着手正事了。预备，开始！（翻译者在学习时也使用JAVA再次实现）

我们开始解释器和编译器的第一部就是写一个简单的算术表达式的简单解释器，也就是计算器。今天的目标很简单，做一个能够将处理两个单个整数相加的计算器，就想3+5。这里就是计算器的源代码，哦不，是解释器的源代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# Token types## EOF (end-of-file) token is used to indicate that# there is no more input left for lexical analysisINTEGER, PLUS, EOF = 'INTEGER', 'PLUS', 'EOF'class Token(object):
    def __init__(self, type, value):
        # token type: INTEGER, PLUS, or EOF
        self.type = type
        # token value: 0, 1, 2. 3, 4, 5, 6, 7, 8, 9, '+', or None
        self.value = value

    def __str__(self):
        """String representation of the class instance.        Examples:            Token(INTEGER, 3)            Token(PLUS '+')        """
        return 'Token({type}, {value})'.format(
            type=self.type,
            value=repr(self.value)
        )

    def __repr__(self):
        return self.__str__()class Interpreter(object):
    def __init__(self, text):
        # client string input, e.g. "3+5"
        self.text = text
        # self.pos is an index into self.text
        self.pos = 0
        # current token instance
        self.current_token = None

    def error(self):
        raise Exception('Error parsing input')

    def get_next_token(self):
        """Lexical analyzer (also known as scanner or tokenizer)        This method is responsible for breaking a sentence        apart into tokens. One token at a time.        """
        text = self.text

        # is self.pos index past the end of the self.text ?
        # if so, then return EOF token because there is no more
        # input left to convert into tokens
        if self.pos > len(text) - 1:
            return Token(EOF, None)

        # get a character at the position self.pos and decide
        # what token to create based on the single character
        current_char = text[self.pos]

        # if the character is a digit then convert it to
        # integer, create an INTEGER token, increment self.pos
        # index to point to the next character after the digit,
        # and return the INTEGER token
        if current_char.isdigit():
            token = Token(INTEGER, int(current_char))
            self.pos += 1
            return token

        if current_char == '+':
            token = Token(PLUS, current_char)
            self.pos += 1
            return token

        self.error()

    def eat(self, token_type):
        # compare the current token type with the passed token
        # type and if they match then "eat" the current token
        # and assign the next token to the self.current_token,
        # otherwise raise an exception.
        if self.current_token.type == token_type:
            self.current_token = self.get_next_token()
        else:
            self.error()

    def expr(self):
        """expr -> INTEGER PLUS INTEGER"""
        # set current token to the first token taken from the input
        self.current_token = self.get_next_token()

        # we expect the current token to be a single-digit integer
        left = self.current_token
        self.eat(INTEGER)

        # we expect the current token to be a '+' token
        op = self.current_token
        self.eat(PLUS)

        # we expect the current token to be a single-digit integer
        right = self.current_token
        self.eat(INTEGER)
        # after the above call the self.current_token is set to
        # EOF token

        # at this point INTEGER PLUS INTEGER sequence of tokens
        # has been successfully found and the method can just
        # return the result of adding two integers, thus
        # effectively interpreting client input
        result = left.value + right.value
        return resultdef main():
    while True:
        try:
            # To run under Python3 replace 'raw_input' call
            # with 'input'
            text = raw_input('calc> ')
        except EOFError:
            break
        if not text:
            continue
        interpreter = Interpreter(text)
        result = interpreter.expr()
        print(result)if __name__ == '__main__':
    main()

将上述代码保存到calc1.py文件或者你可以直接从GitHub上下载。在你准备钻研代码之前，先在命令行上运行，这样你就能看到执行结果。先试试吧！这里是一个在我笔记本上的简单会话（如果你想要使用Python3运行这个计算器，你可能需要将raw_input替换为input）:

1
2
3
4
5
6
7
8
$ python calc1.py
calc> 3+4
7
calc> 3+5
8
calc> 3+9
12
calc>

为了确保你的计算器能够正常工作不抛异常，你的输入需要满足一下指定规则：

  ·单个数字作为输入

  ·只能运算加法

  ·在输入的任何地方不能有空格

这些限制就能使得计算器的实现变得简单。别担心过，不久我们就能做一个更加复杂更加完善的了。

好了，现在就让我们看看这个解释器是如何工作并且它是如何进行算数运算的。

当你在命令行输入 3+5 的时候，解释器就获得了一个字符串 “3+5”。为了使解释器能够理解这一字符串，那么就要将 “3+5” 拆分成不同的个体单元，我们将这些个体称为tokens。一个token是一个拥有类型和值的对象。比如字符 “3” 的类型为整数，而对应的值就为整数 ”3“。

将这些输入的字符串拆分为tokens的程序就叫词法分析( lexical analysis)。所以，我们的解释器最先需要的就是读取输入的字符并且将他们转换为tokens的流。解释器的这一部分就叫词法分析器（ lexical analyzer ）或者词法器（ lexer ）。你可能还看到过这一部分的其他名字，例如 scanner 或者 tokenizer。它们都是一个意思：解释器或编译器中，将输入的字符转换为tokens流的一部分。

在Interpreter类中的函数方法get_next_token就是词法分析器。每一次调用它，你就会得到下一个从输入的字符里面得到的token，并且传递给解释器。让我们更近一步的看一下这个方法本身，看看它具体是如何将字符转换为tokens的。输入存储在变量 text中，text中包含了字符串以及一个字符串的位置索引的值pos（想象这个字符串是一个字符的数组）。pos的初始化地址为0，并且指向字符 ‘3’。这个方法首先确认这个字符是否为数字，如果是的话，那么他就将pos自增1并且返回一个类型为整数的token实例。在这个例子中，字符串 ‘3’ 就是一个整数 3 。

integer3

现在 text中的 pos 的值就指向了字符 ‘+’ 。下次你调用这个方法的时候，他就会检验位置 pos 指向的字符是否为数字，然后再查询这个字符是否为一个加号标志，当然它是。这个方法的结果，就是自增 pos 并且返回一个新创建的类型为PLUS并且值为 ‘+’ 的token。

plustoken

pos 现在就指向了字符 ‘5’ 。当你再次调用get_next_token方法的时候，方法就检查他是否为一个数字，显然是的，所以 pos 自增1且返回一个新的整数token并且将这个token的值设置为整数 5 ：

integer5

索引 pos 现在已经到了字符串 “3+5” 的最后，每次到这种时候，函数get_next_token就返回一个EOF的token：

tokenEOF

尝试一下并且看看词法分析器是如何工作的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> from calc1 import Interpreter
>>>
>>> interpreter = Interpreter('3+5')
>>> interpreter.get_next_token()
Token(INTEGER, 3)
>>>
>>> interpreter.get_next_token()
Token(PLUS, '+')
>>>
>>> interpreter.get_next_token()
Token(INTEGER, 5)
>>>
>>> interpreter.get_next_token()
Token(EOF, None)
>>>

到这里，你的解释器已经能够从输入的字符串里获得tokens流了，解释器就需要去用它进一步处理：他需要从词法分析函数get_next_token获得如下的结构：整数->加号->整数。

负责找到并且解释这一数据结构的函数是expr。这个方法验证了输入的token的顺序是否是正确的，比如：整数->加号->整数。在正确验证了数据结构后，他将加号左边和右边的token的值相加，因此就正确解释了你传递给解释器的表达式。

函数expr使用了辅助函数eat去验证传递过来的token的类型是否正确，在匹配了token的类型，函数eat获得下一个token并且将他赋值为变量 current_token 。看起来就像是在吞食当前匹配的标记符，并不断将 pos 指向下一个位置。如果token流的顺序与预期不符，则函数eat就会抛出异常。

让我们复述一下，你的解释器是如何验算一个算术表达式的：

 ·解释器获得了一个字符串， “3+5”

 ·解释器调用expr方法去找到一个从词法分析器get_next_token中获得的token流。并且尝试去匹配形式：整型->加号->整型。确认了结构后，解释器就将两个整型tokens的值相加，这对于解释器来说就比较清楚了。

祝贺你自己！你已经学会了构建你的第一个解释器。

现在是练习时间啦！

练习

你是不是认为仅仅是读了这篇文章还完全不够呢？好吧，让我们来处理一些一下更复杂的情况吧：

 1.改变代码是的输入的字符能够是多位数的数字，例如 “12+3”

 2. 添加一个方法，能够跳过空格，这样你的解释器就能处理如 “  12+3” 的情况啦。

 3.改变代码使得运算不仅仅是 ”+“ 还能处理 ”-“ 例如 ”7-5“

检验你是否理解了呢？

 1.解释器是什么？

 2.编译器是什么？

 3.解释器和编译器之间有什么区别？

 4.token是什么？

 5.将输入的字符流转换为tokens的程序叫什么名字？

 6.解释器中处理文法分析的部件叫什么？

 7.解释器和编译器中，第6题的其他通用名是什么？