自己手动编写一个简单的解释器 Part 1 已翻译 100%

Aaron74 投递于 2015/07/01 16:05 (共 10 段, 翻译完成于 07-03)
阅读 15060
收藏 257
27
加载中

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

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

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

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

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

金柳颀
金柳颀
翻译于 2015/07/01 22:31
9

为何需要学习解释器和编译器?此处我给出三个理由:

  1. 如果想要编写一个解释器或编译器,需要掌握并结合运用大量的专业技能。通过编写解释器或编译器,有助于提升自己这方面的专业技能,并成为一名更优秀的软件开发者。你所学到的技能也可用于编写任何软件,而不仅限于解释器或编译器。

  2. 迫切渴望了解计算机的工作原理。解释器和编译器常常看起来就像一种魔术,而你不应该满足于简单地运用这种魔术。你想揭开解释器和编译器编写过程的神秘面纱,理解它们的工作原理,并实现对解释器和编译器的控制。

  3. 渴望创造自己的程序设计语言或领域特定语言。如果你想创造一门语言,也需要为这种语言创建一个解释器或编译器。最近,新程序设计语言的研究热潮再次到来。我们几乎每天都能看到突然冒出一门新的程序设计语言:Elixir、Go、Rust,此处就只列出这些例子了。

理由就是这些了。但是,解释器和编译器到底是什么呢?

金柳颀
金柳颀
翻译于 2015/07/01 22:56
2

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

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

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

lostTemple
lostTemple
翻译于 2015/07/01 22:53
2

直说了吧,你我打算为 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, 该做正事了。 各就各位,预备,开始!

gx老苗
gx老苗
翻译于 2015/07/02 09:37
4

开始制作解释器和编译器的第一步尝试是写一个简单的算术表达式解释器,也叫计算器。今天的目标很简单:能处理计算两个个位整数相加,如 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等)

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

gx老苗
gx老苗
翻译于 2015/07/02 10:19
1

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

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

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

gx老苗
gx老苗
翻译于 2015/07/02 10:51
3

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 标记符:

gx老苗
gx老苗
翻译于 2015/07/02 11:12
1

观察计算器的词法分析器部件(程序)是如何工作的:

>>> 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 函数则会抛出异常。

gx老苗
gx老苗
翻译于 2015/07/02 16:32
1

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

  • 解释器获取了一个输入字符串,就是 “3+5”

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

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

现在,该动手练习了。

你不会认为读完这篇文章(掌握构建解释器)就够了吧? Okay,别让手闲着,完成下面的练习:

  1. 修改代码,允许多位数整数输入,如 “12+3”

  2. 增加函数能忽略空白字符,则计算器可以接受含空白的输入,如 ”12 + 3“

  3. 修改代码,将 ‘+’替换成‘-‘,实现 “7-5”表达式的减法运算。

gx老苗
gx老苗
翻译于 2015/07/02 17:25
2

测验你是否理解

  1. 什么是解释器?

  2. 什么是编译器?

  3. 解释器和编译器的区别是什么?

  4. 标记符是什么?

  5. 将输入分割为标记符的进程名叫什么?

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

  7. 解释器或编译器中的上题6的部件,其他通用名怎么称呼,请列举出来。

在本文结束之前,我真切希望你正在学习解释器和编译器。希望你马上就学,而不是扔到一边。别等了。如果你已经概略看过本位,再读一遍。如果你认真读过,但没有完成练习——那就现在开始(做练习)。如果你没有做完,那完成它。你读懂大意,理解怎么回事了吗?签署保证书,今天就开始学习解释器和编译器!

本人, ________, 思想健全,身体健康,在此郑重声明,今天开始学习解释器和编译器,每一处,我都要100%掌握它们是如何工作的!

签名:


日期:

签好,注明日期, 放到每天都能看到的显眼处,以确保你坚持你的承诺。牢记承诺的定义:

“Commitment is doing the thing you said you were going to do long after the mood you said it in has left you.” — Darren Hardy

Okay, 今天的事到此结束。该 mini 系列的后一篇,扩展你的计算器,处理更多的算术表达式。请继续关注。

推荐书目:

语言实现模式: 构建专属领域和通用编程语言 (程序员实用手册)

实现编译器和解释器: 以软件工程师方式

现代编译器和解释器,java实现

现代编译器设计

编译器:原理, 技术, 和工具 (2nd Edition)

gx老苗
gx老苗
翻译于 2015/07/02 18:03
1
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接。
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。
加载中

评论(23)

寻花不问柳
为什么不用java来开发呢?哈哈,用C来开发也可以
小-夜-曲
小-夜-曲

独孤青冥
独孤青冥
不明觉厉。
哆啦比猫
哆啦比猫
evaluate应该是“求值”吧,怎么会是“验算”
PYPlus
PYPlus
之前工作 搞过这个 用yacc和lex开发的
Loveni
Loveni
不懂
Brokedge
Brokedge
龙虎..........
htfy96
htfy96
没学过编译原理自己搞个小解释器,不断修改后发现和标准的preprocessor -> tokenizer -> lexical analysis -> interpreter过程基本一致。编译的确是一门学问
沙枣
沙枣
这是解释器比较复杂的实现方式,还有更好的
紫电清霜
紫电清霜
i know 100% 咯~
返回顶部
顶部