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

Aaron74 投递于 2015/07/13 09:47 (共 7 段, 翻译完成于 07-14)
阅读 3412
收藏 19
3
加载中

自己手动编写一个简单的解释器 Part 1

《有效思考的5个要素》的作者 Burger 和 Starbird 在他们精彩的书中分享了一个关于他们如何观看国际知名小号演奏家 Tony Plog 为多才多艺的小号演奏者举办大师课的故事。学生们首先演奏复杂的音乐章节,他们都表演的很棒。但随后他们被要求表演非常基础的简单的音符。当他们演奏那些音符时,听起来比先前演奏的复杂片段要稚嫩些。他们完成演奏之后,大师也演奏了相同的音符。但他演奏这些音符时听起来并不稚嫩。差异惊人。Tony 解释道:控制好简单音符的能力可以让你更具备控制力来演奏复杂部分。教训是显而易见的——建立真正的精湛技术必须重点掌握简单基本的理念。

igor_sz
igor_sz
翻译于 2015/07/13 21:57
2

故事中的经验显然不仅仅可用于音乐也能用于软件开发。对我们所有人来说故事是个非常好的告诫:不要忘记深入挖掘简单基本的理念对复杂工作的重要性,即使有时候感觉像是倒退。虽然精通一个工具或者你使用的框架是重要的,但了解他们背后的原则也是非常重要的。正如 Ralph Waldo Emerson 所说:“如果你仅仅学习方法,你将被被你的方法束缚。但是如果你学习原则,你可以设计自己的方法。”

关于这点,让我们再一次深入到编译器中。

今天我将为你们展示一个包含以下功能的第一部分中提及的新版本计算器:

  1. 处理输入字符串任何地方的空白字符


  2. 消耗(consume)来自输入的多位整数


  3. 两个整数的减法(目前他仅能处理整数的加法)


igor_sz
igor_sz
翻译于 2015/07/13 22:33
1

这是新版计算器的源代码,实现了上述需求:

# Token types
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis
INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'
class Token(object):
    def __init__(self, type, value):
        # token type: INTEGER, PLUS, MINUS, or EOF
        self.type = type
        # token value: non-negative integer value, '+', '-', 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", "12 - 5", etc
        self.text = text
        # self.pos is an index into self.text
        self.pos = 0
        # current token instance
        self.current_token = None
        self.current_char = self.text[self.pos]
    def error(self):
        raise Exception('Error parsing input')
    def advance(self):
        """Advance the 'pos' pointer and set the 'current_char' variable."""
        self.pos += 1
        if self.pos > len(self.text) - 1:
            self.current_char = None  # Indicates end of input
        else:
            self.current_char = self.text[self.pos]
    def skip_whitespace(self):
        while self.current_char is not None and self.current_char.isspace():
            self.advance()
    def integer(self):
        """Return a (multidigit) integer consumed from the input."""
        result = ''
        while self.current_char is not None and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        return int(result)
    def get_next_token(self):
        """Lexical analyzer (also known as scanner or tokenizer)
        This method is responsible for breaking a sentence
        apart into tokens.
        """
        while self.current_char is not None:
            if self.current_char.isspace():
                self.skip_whitespace()
                continue
            if self.current_char.isdigit():
                return Token(INTEGER, self.integer())
            if self.current_char == '+':
                self.advance()
                return Token(PLUS, '+')
            if self.current_char == '-':
                self.advance()
                return Token(MINUS, '-')
            self.error()
        return Token(EOF, None)
    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):
        """Parser / Interpreter
        expr -> INTEGER PLUS INTEGER
        expr -> INTEGER MINUS 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 an integer
        left = self.current_token
        self.eat(INTEGER)
        # we expect the current token to be either a '+' or '-'
        op = self.current_token
        if op.type == PLUS:
            self.eat(PLUS)
        else:
            self.eat(MINUS)
        # we expect the current token to be an integer
        right = self.current_token
        self.eat(INTEGER)
        # after the above call the self.current_token is set to
        # EOF token
        # at this point either the INTEGER PLUS INTEGER or
        # the INTEGER MINUS INTEGER sequence of tokens
        # has been successfully found and the method can just
        # return the result of adding or subtracting two integers,
        # thus effectively interpreting client input
        if op.type == PLUS:
            result = left.value + right.value
        else:
            result = left.value - right.value
        return result
def 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()

将上述代码保存到 calc2.py 文件中,或者直接从 GitHub 下载。试着运行一下,看看结果是否满足预期:这个程序可以处理输入中的空白符;可以处理多位整数;除了执行整数加法,还能执行整数减法。

这是我执行的一个示例:

$ python calc2.py
calc> 27 + 3
30
calc> 27 - 7
20
calc>
袁不语
袁不语
翻译于 2015/07/14 13:05
1

这一版与 Part 1 中那一版相比,主要的改动在于:

  1. get_next_token 方法进行了一点儿重构。将增加 pos 指针的逻辑封装到了方法 advance中。

  2. 添加了两个方法: skip_whitespace 用来忽略空白符; integer 用来处理输入中的多位整数。

  3. 修改了expr 方法,使其除了可以识别 INTEGER -> PLUS -> INTEGER 语句,也能识别INTEGER -> MINUS -> INTEGER 语句。该方法在成功识别对应语句后也能解释执行对应的加法操作和减法操作。

Part 1 中,你学到了两个重要的概念,也就是标记符(token)词法分析器(lexical analyzer)。今天我将会谈一下词素(lexemes)解析(parsing)和解析器(parsers)

袁不语
袁不语
翻译于 2015/07/14 13:30
1

你已经知道标记符了。但是为了完成标记符的讨论,我需要提谈一下词素(lexemes)。什么是词素?一个词素是形成一个标记的一系列字符。在下图中,你可以看到一些标记的例子和词素的示例,希望这样可以使它们之间的关系变清晰:

还记得 expr 方法吗?我之前说过,这是实际上解释算术表达式的地方。但是在解释某个表达式之前,你首先需要识别表达式的类型,例如是加法表达式还是减法表达式。expr 方法本质上做了这些事情:从 get_next_token 方法输出的标记流中发现语句的结构,然后解释识别出的语句,生成算数表达式的结果。

袁不语
袁不语
翻译于 2015/07/14 14:21
1

从标记流中发现结构的过程,或者说从标记流中识别语句的过程,称为解析(parsing)。解释器或者编译器中承担该任务的部分称为解析器(parser)

现在你知道expr方法是该解释器中解析(parsing)解释(interpreting)执行的地方 —— expr方法首先尝试从标记流中识别(解析)INTEGER -> PLUS -> INTEGER语句或者INTEGER -> MINUS -> INTEGER语句,然后在成功地识别(解析)其中某个语句之后,该方法解释这个语句,返回加法操作或者减法操作的结果给调用者。

袁不语
袁不语
翻译于 2015/07/14 14:34
1

现在是再次练习的时候了。

  1. 继承计算机解决两个数的乘法的方法

  2. 继承计算机解决两个数的除法的方法

  3. 修改代码来解释包含任意数量增量或减量的表达式。 例如 “9 - 5 + 3 + 11”

检查你的学习情况.

     1.什么是语义?

     2.在字符流中识别构造器的方法的过程叫什么?或则换句话说,识别具体段落中的字符流的程序是什么?

     3.编译器(解析器)执行的部分称为什么?

我希望你会喜欢今天的材料。在本系列的下一遍文章中,你将会学到用计算器去处理更加复杂的算术表达式。希望继续收看。

自己手动编写一个简单的解释器 Part 1

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

评论(7)

常伟佳
常伟佳
Part 3 出来了!可以参加翻译吗?
[Let’s Build A Simple Interpreter. Part 3. - Ruslan's Blog](http://ruslanspivak.com/lsbasi-part3/)
hefeimissyou
hefeimissyou
急切等待~~
blu10ph
blu10ph
留爪~
Summer姐姐
Summer姐姐

引用来自“明轩chen”的评论

未完待续
我翻译得比较水
Summer姐姐
Summer姐姐

引用来自“igor_sz”的评论

未完待续
Stay tuned 哈哈哈
明轩chen
明轩chen
未完待续
igor_sz
igor_sz
未完待续
返回顶部
顶部