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

Aaron74 投递于 2015/11/03 16:03 (共 9 段, 翻译完成于 11-18)
阅读 731
收藏 0
0
加载中

之前几篇文章:

你是怎么去弄懂像创建一个编译器或解析器这类复杂的东西的? 刚开始它就像一团乱毛线,你需要将这堆乱毛线整理成一个毛线球.

为了整理成一个毛线球,你只需要一次整理一根线,一个结。有时尽管你可以会有一些不太懂,但是你只要不停止向前,持之以恒,我向你保证最后它都会茅塞顿开的(如果我每次放弃25%我不懂的东西,继续前进,很长一段时间以后我会有很多收获)

搞懂如何创建一个编译器或解析器,我能给你的最好的忠告是去读文章,读代码,然后自已写代码,甚到在一段时期内写同样的代码很多次,然后感觉到这些东西就是你的一部份一样的,等你如此的熟悉它们之后,你再学习下一章。不要急,放慢你的脚步,花时间去深记得理解基本的概念。这种方法看上去似乎很慢,但是会有很多收获。相信我.

zhonghai
zhonghai
翻译于 2015/11/04 17:35
1

你最终会得到你完美的毛线球。你知道吗?尽管它不是那么完美,它任然比什么也不学习或者只快速浏览过几天就忘了要好。

记住-只要保持去解开它:一段线、一个结,逐一去解开它,并且通过写代码去练习你所学到的,写很多:

今天,你将要运用这一系列中的前一篇文章中的所有知识,并且学习如何分析和解释任意数值的加法、减法、乘法和除法的算术表达式。你将会写一个可以求值的解释器,表达式如"14+2*3-6/2"。

在潜水去写代码之前,让我先讨论一下操作符的结合性优先级

按惯例7+3+1与(7+3)+1是相同的,7-3-1与(7-3)-1是相同的。这里没有惊喜。我们都曾学习过并且把它视作理所当然。但如果我们处理7-3-1与7-(3-1)同样,结果将是意想不到的 5,而不是我们期望的 3。

终日乾乾
终日乾乾
翻译于 2015/11/05 14:00
2

在普通的算术和大多数编程语言中,加法、减法、乘法和除法都是左结合的:

7 + 3 + 1 等价于 (7 + 3) + 1
7 - 3 - 1 等价于 (7 - 3) - 1
8 * 4 * 2 等价于 (8 * 4) * 2
8 / 4 / 2 等价于 (8 / 4) / 2

一个左结合的运算符是什么意思呢?

当一个操作数像表达式7+3+1中的3,它的两边都有加号,我们需要有一个公约,来确定哪一个运算符与3结合。是操作数3左边的那一个还是右边的那一个?运算符+与左侧结合,因为一个两侧都有加号运算符的操作数属于它左侧的运算符,所以我们说运算符+是左结合的。这就是为什么7+3+1等价于(7+3)+1根据结合性公约

好了,那么像这样的表达式7+5*2,它的操作数5的两边有不同的运算符。它等价于7+(5*2)还是(7+5)*2?我们如何解决这种歧义?

在这种情况下,结合性公约对我们没有帮助,因为它只适用于一种类运算符,或者是加法运算符(+,-)或者是乘法运算符(*,/)。当我们在同一个表达式中有不同种类的操作符时,我们需要另一个公约来解决这个歧义。我们需要一个定义了运算符优先级的公约。

终日乾乾
终日乾乾
翻译于 2015/11/05 16:37
3

下面的就是了:我们说如果运算符*在+之前拿到它的操作数,那么它就有更高的优先级。在我们所了解和使用的算法中,乘法和除法比加法和减法有更高的优先级。所以表达式7+5*2与7+(5*2)等价,表达式7-8/4与7-(8/4)等价。

当表达式中运算符的优先级相同时,我们只是用结合律公约和从左到右的顺序来执行:

7 + 3 - 1 等价于 (7 + 3) - 1
8 / 4 * 2 等价于 (8 / 4) * 2

我希望你不要以为我愿意让你无聊到死,来听我说这么多关于运算符的结合性和优先级。关于那些约定好的一点是,我们可以为算术表达式构造一种文法,通过参考一个表明了算术运算符的结合性和优先级的表格。然后,我们可以把文法翻译成代码,通过我在第4部分所列出的指南,这样我们的解释器就能够解决运算符的结合性和优先级了。

终日乾乾
终日乾乾
翻译于 2015/11/05 18:03
1

好了,这就是我们的优先级表格:

从表中,你可以知道运算符 + 和 - 有相同的优先级,并且它们都是左结合。你还可以看到运算符 * 和 / 也是左结合,它们有相同优先级但是它们比加法和减法运算符的优先级要高。

下面是如何根据优先级表格来构造一个文法的规则:

1. 对于每一个优先级级别定义一个非终结符。这个非终结符的主体应该包含这一级别的算术运算符和下一个更高级别的非终结符。

2. 创建一个附加的非终结因子作为表达式的基础单元,在我们这个例子里就是一个数字。一般规则是如果你有 N 个优先级别,那么你总共就需要有 N+1 个非终结符:一个非终结符对应一个优先级别,再加上一个非终结符也就是表达式的基础单元。

向前进!

让我们按照这个规则来构造我们的文法吧。

终日乾乾
终日乾乾
翻译于 2015/11/06 15:12
1

根据规则1,我们需要定义两个非终结符:一个叫 expr 作为等级 2,另一个叫 term 作为等级1.然后根据规则2,我们需要定义一个整形的非终结符算法基本单元作为因数。

我们新语法的开始符号将会是 expr,expr 的结果(production)将会包含一个代表着使用二级操作符的实体,我们例子里面使用的是+和-,同时也会包含下一个更高优先级的非终结符 term,等级1:

term 的结果会包含代表使用等级 1 操作符的实体,在我们这个例子中是 * 和 /,同时也会包含表达式基本单元的整形非终结符因数:

非终结符因子的结果将会是:

暖冰
暖冰
翻译于 2015/11/07 23:02
1

你已经看到了前文分析的语法和句法图解,在这里我们要将它们组合成一个语法,这个语法充分考虑了运算符的结合性和优先级:

这里是一个语法图,对应上面的语法:

下图中每一个矩形框都是一个“调用方法”,来调用另一个图。拿表达式7+5*2来说,从顶层图expr开始,向下走到达最底层的图factor,你就会看到高优先级的运算符*和/在低级图中,比高级图中的+和-先执行。

把运算符优先级将得更透彻些,让我们来看一下同一个算术表达式7+5*2按照我们之前的语法和语法图来分解的过程。这只是另一种方式来表示高优先级运算符在低优先级运算符之前执行:

好了,让我们按照指导原则第4部分来把语法转换为代码,看看我们新的解释器是如何工作的,怎么样?

下面再复习一次语法:

这就是一个计算器的完整代码,它可以处理包含整数并且任意数量的加法、减法、乘法和除法运算符的有效算术表达式。

终日乾乾
终日乾乾
翻译于 2015/11/18 17:23
1

以下是主要的变化与第4部分中的代码:

  • 词法分析程序类现在可以标记+,-,*,/(没有新来的,我们刚从以前的文章组合码成一个类,支持所有这些令牌)

  • 回想一下,每个规则(生产),R,定义的语法,变成了一个具有相同名称的方法和引用的规则成为一个方法调用:R()。因此解释器类现在有三种方法,对应于非终结符语法:expr,term,和 factor。

源代码:

# 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, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', 'EOF')class Token(object):
    def __init__(self, type, value):
        # token type: INTEGER, PLUS, MINUS, MUL, DIV, 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, '+')            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. "3 * 5", "12 / 3 * 4", etc
        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, '/')

            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"""
        token = self.current_token
        self.eat(INTEGER)
        return token.value

    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>  14 + 2 * 3 - 6 / 2        17        expr   : term ((PLUS | MINUS) term)*        term   : factor ((MUL | DIV) factor)*        factor : INTEGER        """
        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()

将以上代码保存到 calc5.py 文件或直接从 GitHub 下载它。像往常一样,试试自己的翻译正确计算算术表达式,运营商有不同的优先级。

下面请看这个例子:

$ python calc5.py
calc> 3
3
calc> 2 + 7 * 4
30
calc> 7 - 8 / 4
5
calc> 14 + 2 * 3 - 6 / 2
17
机智的祺祺
机智的祺祺
翻译于 2015/11/16 12:42
1

下面是今天的练习题:

  • 不看本文中提供的代码而单纯凭借对本文的记忆来编写一个编译器,给出一些测试并且确保通过。

  • 扩展编译器处理包括括号的算术表达式,这样你的编译器可以评估深层嵌套的算术表达式,例如:7 + 3 *(10 /(12 /(3 + 1)- 1))

检查你是否真的明白了:

  1. 什么叫做操作符左结合?

  2. + 和 - 是左结合还是右结合?那么 * 和 / 呢?

  3. + 的运算优先级比 * 高吗?

嘿,你读到最后!这真是棒极啦的。我下次还会更新更多的文章,关注我是一个明智之选。另外,和往常一样,不要忘记做练习。

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

评论(0)

返回顶部
顶部