自己手动编写一个简单的解释器 Part 1 _Linux伊甸园开源社区-24小时滚动更新开源资讯，全年无休！

“如果你不了解编译器是如何工作的，那么你就不了解计算机是如何工作的。如果你无法确保100%掌握编译器的工作原理，那么你就是不了解其工作原理” — Steve Yegge

好了，思考一下这个问题。无论你是菜鸟，还是经验丰富的软件开发人员，如果你不了解编译器和解释器的工作原理，那么你就不了解计算机的工作原理。就是这么简单。

因此，你知道编译器和解释器的工作原理吗？我的意思是，你必须确保100%掌握其工作原理，如果你无法确保这点。

或如果你不了解其工作原理，并为之焦虑不安。

其实完全不必担心。如果你能坚持下来，完成这一系列任务，并跟着我编写一个解释器和编译器，最后你会掌握它们的工作原理。同时你也会为此感到快乐且信心百倍。至少我希望实现这种效果。

为什么你要学习解释器和编译器？我给出了三个原因。

写一个解释器或一个编译器你必须要有与之匹配的一些技术能力。写一个解释器或一个编译器将会帮你提升那些技能，并且会成为一个更好的软件开发人员。同时，这些技能对于写任何软件都是有帮助的，不局限于解释器或编译器。
你真正想要知道计算机是如何工作的。通常解释器和编译器看起来就像魔法。并且你不会对这个魔法感到舒服。你想要阐述建立一个解释器和编译器的过程，理解他们是怎么工作的，让这些东西处在控制之中。
你希望创建你自己的编程语言或者支配某个特殊的语言。如果你创造了这样一门语言，你同时也会需要制作一个解释器或者编译器给这个语言。最近，你要是对新的编程语言兴趣再起。你会看到新的编程语言每天都在出现：Elixir，Go，Rust 这里仅举几例。

好的，那什么是解释器和编译器呢？

一个解释器或编译器的目标是将某些高级语言的源程序翻译成其他的形式。解释的相当含糊，不是吗？再忍我一下，之后的一系列章节你将能够确实地了解源程序被翻译成什么。

在这个时间点上，你可能会好奇到底解释器和编译器之间有什么差别呢。为了达成这个系列的目的，让我们同意以下解释：如果翻译器把源程序翻译成了机器语言，他就是一个编译器。如果源程序没先被翻译成机器语言，翻译器就处理并且执行了源程序，他就是一个解释器。形象地看起来就像这样：

我希望截至目前你已经确信你真的想要学习并构建一个解释器和编译器，那你可以期望从这个关于解释器的系列中获得什么呢？

直说了吧，你我打算为 Pascal 语言大子集实现一个简单的解释器。在该系列最后部分，你会得到一个可工作的 Pascal 解释器，和一个类似 python 中 pdb 的源码级别的调试器。

你或许会问，为什么选 pascal？首先，它不是一个虚假的语言，所以我选中它在这个系列中使用：这是一个真实的编程语言，具备许多重要的语法结构。它虽然有点古老了，但仍被使用。CS（注，计算机科学）书籍使用 pascal 编程语言实现书中示例（我知道，选择为这个语言实现解释器的理由并不充分，但我想，这也是一个学习非主流语言的好机会：））

下面例子使用 pascal 写的阶乘函数实现。可以用你自己构建的解释器解析，还可以使用后面将实现的调试器做代码级别的交互式调试。

            
                        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.

我们使用 python 作为 Pascal 解释器的实现语言，当然，你可以使用任何你熟悉的语言（来实现），因为实现原理并不依赖具体的语言特性。Okay, 该做正事了。各就各位，预备，开始!

开始制作解释器和编译器的第一步尝试是写一个简单的算术表达式解释器，也叫计算器。.今天的目标很简单：能处理计算两个个位整数相加，如 3+5。下面是是计算器，啊不，解释器的源代码：

            
                
                        
                        # 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 上运行计算器，你应该是用 input，而不是 raw_input):

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

为确保你的简单计算器能正确执行，不抛出异常，你的输入需满足以下指定的规则:

输入中只允许出现个位数整数
当前算术运算符解释器只支持加法运算
输入中的任何位置不能出现空白（注，空格，TAB等）

这些限制对保持计算器简单很有必要。别担心，很快，你的实现就会越来越复杂的。

Okay，现在我们研究下，你的解释器如何工作，如何计算算术表达式的。

你在命令行输入表达式 3+5 ，你的解释器会得到一个字符串 “3+5”。为能准确理解并处理字符串，解释器第一步要将输入的“3+5” 分割成多个部件，这些部件我们称为标记符（token），标记符是指对象，它具有类型和值属性。例如，字符串“3”，标记符号的类型是整型（INTEGER），对应的值是整数3。

将输入字符串分割为标记符的过程称为文法分析。所以，解释器的第一步工作是读取输入的字符序列，并将其转换为标记符流。解释器中处理该部分工作的部分称为文法分析器，或叫词法分析器。简而言之，你或许听到过该部件的其他命名，如 scanner (扫描器)或 tokenizer (标记符生成器)。这指的都是一回事：解释器或编译器的该部件将输入的字符序列转变成标记符号流。

Interpreter 类中的函数 get_next_token 是文法分析器。每次调用它时，从输入给解释器的字符序列输入中,会得到相邻下一个标记符（的起始位置索引）。咱们仔细看一下这个函数本身，研究下，它是如何完成将字符序列转换成标记符工作的。输入保存到变量 text 中，text 变量存储输入字符串，而 pos 变量则是字符串的索引(将字符串看成一个字符数组)。pos 的初始值为 0，指向字符‘3’。函数首先检查字符是否是一个整型数字，如果是，pos 变量加 1，返回 ‘3’的标记符实例，其类型是整型（INTEGER)，值是3：

pos 索引现在指向 text 变量中的‘+’ 字符。你再次调用该函数时，它测试 pos 索引指向的 text 中的字符是否是整型数字，而测试的结果是一个加号。结果，函数使 pos 变量自增，返回新创建的标记符实例，类型是 PLUS，值是‘+’。

pos 变量指向字符‘5’。你又一次调用函数 get_next_token，来检查当前指向的字符是否整型数字, 这次是了，因此，pos 变量自增，返回新的标记符实例，其类型是整型（ INTEGER），值是 5：

由于 pos 索引当前指向字符串“3+5” 的最后位置，你再调用函数 get_next_token，则返回 EOF标记符:

观察计算器的词法分析器部件（程序）是如何工作的：

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

                    

            
            

好的，既然你的解释器能访问（获取）输入字符序列生成的标记符流，解释器需要用它进一步处理：它需要从词法分析器函数 get_next_token 生成的序化（线性）的标记符流中，找出数据的结构：INTEGER -> PLUS -> INTEGER。也就是说，它尝试找出标记符序列：一个整数，接着是加号，之后是一个整数。

负责发现和解释数据结构的函数是 expr。该函数校验（验证）标记符序列是否与预期序列一致，比如，INTEGER -> PLUS -> INTEGER。在结构确认无误后，它将加号左边标记符的值与其右边标记符值相加，生成（表达式的）结果，这样，就将你传给解释器的表达式，成功计算出算术表达式的结果。

expr 函数本身调用了助手函数 eat 校验输入标记符参数的类型与当前的标记符类型是否匹配。匹配输入标记符类型后，eat 函数获取下一个标记符，将其赋值给 current_token 变量，看起来像正在吞食当前匹配的标记符，并不断将虚拟指针指向标记符序列流的下一个位置。如果标记符序列流的结构与预期的 INTEGER PLUS INTEGER 序列并不一致的话，eat 函数则会抛出异常。

我们复述下，你的解释器验算（evaluate，原意是评价）算术表达式时，都做了哪些工作（或都发生了什么）:

解释器获取了一个输入字符串，就是 “3+5”
解释器条用 expr 函数找出由文法分析器 get_next_token 返回的标记符序列流的结构。结构应该是<INTEGER PLUS INTEGER>形式。确认结构无误后，它解析输入为两个整型标记符的值之和，原因很明显，此时，解释器需要做的事就两个整数 3，5 求和运算。

自豪吧！你已经能构建属于你自己的解释器了!

现在，该动手练习了。