开源中国

我们不支持 IE 10 及以下版本浏览器

It appears you’re using an unsupported browser

为了获得更好的浏览体验,我们强烈建议您使用较新版本的 Chrome、 Firefox、 Safari 等,或者升级到最新版本的IE浏览器。 如果您使用的是 IE 11 或以上版本,请关闭“兼容性视图”。
自己手动编写一个简单的解释器 Part 6 - 技术翻译 - 开源中国社区

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

标签: <无>
Aaron74 推荐于 3年前 (共 4 段, 翻译完成于 11-10) 评论 12
收藏  
109
推荐标签: 待读

之前几篇文章:

今天是个大日子:) “为什么?” 你可能会问。因为今天讲完括号表达式,然后再实现语法解释器对任意深层次,类似7 + 3 * (10 / (12 / (3 + 1) - 1)) 这样嵌套括号表达式的解析之后我们就可以结束算术表达式部分的讨论啦。(嗯,差不多吧)

接下来就开始,没意见吧?

首先,我们调整语法以支持括号表达式。你应该在 Part 5 学过,表达式的基本单元使用了 factor 原则。在那篇文章中,整数就是我们拥有的唯一的基本单元。今天我们就要增加另一个基本单元--括号表达式。让我们开始学习吧。

暖冰
 翻译得不错哦!

下面是我们升级后的语法:

expr 部分和 term 部分和我们在 Part5 里面的一样。这里唯一改变的地方是在 factor 里面,这里的 LPAREN 代表左括号‘(’,RPAREN 代表右括号‘)’,两个括号中间的 expr 代表表达式。

下面是这个 factor 升级后的语法图解,里面包含了可选项。

因为这个语法规则的 expr 和 term 两个部分没有改变,这个语法图解跟 Part5 里面的看起来一样:

在我们新的语法里面有个很有趣的特点-递归性。如果你想于执行表达式2*(7+3),你需要从expr的起始符号开始,最终你需要再次回头执行原始表达式中的(7+3)。

让我们把2*(7+3)根据语法来进行分解,看看它是如何执行的:

说点题外话:如果你需要复习一下关于递归的知识的话,你可以看看 Daniel P. Friedman 和 Matthias Felleisen 合著的 The Little Schemer 这本书,讲的非常好。

暖冰
 翻译得不错哦!

好了,接下来让我们直接根据新的语法翻译代码。

根据前文对代码做的主要修改如下:

  1. Lexer 修改成多返回两个令牌:LPAREN 代表左括号,RPAREN 代表右括号。

  2. 解释器的因子方法在除了整数意外的括号表达式方面有了略微的改进。

这是一份完整的可以处理任意深度嵌套的任意位数的加减乘除四则运算的计算机源代码:

# Token types## EOF (end-of-file) token is used to indicate that# there is no more input left for lexical analysisINTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF')class Token(object):
    def __init__(self, type, value):
        self.type = type
        self.value = value

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

    def __repr__(self):
        return self.__str__()class Lexer(object):
    def __init__(self, text):
        # client string input, e.g. "4 + 2 * 3 - 6 / 2"
        self.text = text
        # self.pos is an index into self.text
        self.pos = 0
        self.current_char = self.text[self.pos]

    def error(self):
        raise Exception('Invalid character')

    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. One token at a time.        """
        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, '-')

            if self.current_char == '*':
                self.advance()
                return Token(MUL, '*')

            if self.current_char == '/':
                self.advance()
                return Token(DIV, '/')

            if self.current_char == '(':
                self.advance()
                return Token(LPAREN, '(')

            if self.current_char == ')':
                self.advance()
                return Token(RPAREN, ')')

            self.error()

        return Token(EOF, None)class Interpreter(object):
    def __init__(self, lexer):
        self.lexer = lexer
        # set current token to the first token taken from the input
        self.current_token = self.lexer.get_next_token()

    def error(self):
        raise Exception('Invalid syntax')

    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.lexer.get_next_token()
        else:
            self.error()

    def factor(self):
        """factor : INTEGER | LPAREN expr RPAREN"""
        token = self.current_token
        if token.type == INTEGER:
            self.eat(INTEGER)
            return token.value
        elif token.type == LPAREN:
            self.eat(LPAREN)
            result = self.expr()
            self.eat(RPAREN)
            return result

    def term(self):
        """term : factor ((MUL | DIV) factor)*"""
        result = self.factor()

        while self.current_token.type in (MUL, DIV):
            token = self.current_token
            if token.type == MUL:
                self.eat(MUL)
                result = result * self.factor()
            elif token.type == DIV:
                self.eat(DIV)
                result = result / self.factor()

        return result

    def expr(self):
        """Arithmetic expression parser / interpreter.        calc> 7 + 3 * (10 / (12 / (3 + 1) - 1))        22        expr   : term ((PLUS | MINUS) term)*        term   : factor ((MUL | DIV) factor)*        factor : INTEGER | LPAREN expr RPAREN        """
        result = self.term()

        while self.current_token.type in (PLUS, MINUS):
            token = self.current_token
            if token.type == PLUS:
                self.eat(PLUS)
                result = result + self.term()
            elif token.type == MINUS:
                self.eat(MINUS)
                result = result - self.term()

        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
        lexer = Lexer(text)
        interpreter = Interpreter(lexer)
        result = interpreter.expr()
        print(result)if __name__ == '__main__':
    main()

将上面的代码保存为 calc6.py,测试一下,看看你得新解释器能不能正确处理不同操作符已经任意嵌套深度的算术表达式。

一个简单的 python 会话:

$ python calc6.py
calc> 3
3
calc> 2 + 7 * 4
30
calc> 7 - 8 / 4
5
calc> 14 + 2 * 3 - 6 / 2
17
calc> 7 + 3 * (10 / (12 / (3 + 1) - 1))22
calc> 7 + 3 * (10 / (12 / (3 + 1) - 1)) / (2 + 3) - 5 - 3 + (8)10
calc> 7 + (((3 + 2)))12
ismdeep
 翻译得不错哦!

下面是今天为你准备的个小练习


  • 按照本文讲解的方法编写一个自己的算数表达式解析器。记住:重复练习是所有学习方法之母。

嘿,你已经一路看到最后了!恭喜你,你已经学会了如何创建(如果你做了所有的练习-真的编写过)一个简单的可以执行很复杂算术表达式的递归文法文法分析器/解析器。

下一篇文章中我将讲解更多关于递归文法分析器的细节。我也会介绍一个整个系列都会用到,而且在解析器和编译器中都非常重要且运用广泛的数据结构。

敬请期待。在那之前请你继续练习编写你的解析器。更重要的:享受乐趣享受过程!

暖冰
 翻译得不错哦!
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们
评论(12)
Ctrl/CMD+Enter

把虎书看一遍,就有个tiger语言了
如果开发一个语言,这样做事走远路了。。没有人这样做。读一篇理解原理就可以了。

目前开发语言多采用VM技术。这些底层的交给VM去处理。
yacc配合lex分分钟写出来
看成Perl6的路过。。。
自己实现个可以对编程语言如何工作会有个直观感觉,帮助找到找到“世界上最好的语言”…………→_→

引用来自“neo-chen”的评论

如果开发一个语言,这样做事走远路了。。没有人这样做。读一篇理解原理就可以了。

目前开发语言多采用VM技术。这些底层的交给VM去处理。
但是对于学习来说 是可行的
快速阅读,不要留恋,深入研究,要回利用前人的成果,知识是积累使用的。
这个可以学习一下
递归深度不能太深,应该写一个专门求幂和做分解递归的沉降机,也就是你们人类所谓的守护进程和虚拟机,你12357 268 123 12 1 归元
这是传统解释器的写法,最新的解释器写法是将语法从语言中分离出来,让人专注于语言能力。
高深
wonderful
顶部