实现一个简朴的注释器（5）

SpringBoot&Shiro实现权限管理

译自：
（已取得作者受权）

你怎样处置惩罚和相识像建立诠释器或编译器如许庞杂的事变？在入手下手时，统统看上去都像是一团杂乱无章的纱线，你须要解开缠结才获得圆满的球。

抵达那边的要领是将它解开一个线，一次解开一个结。不过有时候，你可能会以为本身听不懂某些内容，但必需继承前进，我向你保证，假如你充足对峙，它最终将“咔嗒”一声被解开。

在明白怎样建立诠释器和编译器的过程当中，最好的发起之一是阅读文章中的诠释，阅读代码，然后本身编写代码，甚至在一段时候里编写雷同的代码，使你能完全相识材料和代码，然后继承进修新主题。不要焦急，只需放慢脚步，花点时候深刻明白基础概念，这类要领虽然看似很慢，但会在将来取得报答。置信我。

末了，最终将取得圆满的毛线球，纵然不是那末圆满，它也比什么也不做或许疾速阅读后的几天内忘记好多了。

请记着：一步步明白这些学问点，并经由过程编写代码演习所学的学问：

本日，你将运用前几篇文章中取得的学问，进修怎样剖析和诠释具有恣意数目的加，减，乘和除运算的算术表达式，你将编写一个诠释器，该诠释器将能够对"14 + 2 * 3 - 6 / 2"之类的表达式求值。

在深切进修并编写一些代码之前，我们先讨论一下运算符的连系性(associativity)和优先级(associativity)。

依据通例7 + 3 + 1与（7 + 3）+ 1雷同，而7 - 3 - 1相当于（7 - 3）- 1。 我们都相识这些。假如我们将7 - 3 - 1视为7 -（3 - 1），则结果将会不测的变成5，而不是我们预期的3。

在平常算术和大多数编程语言中，加，减，乘和除是左连系(left-associative)的：

7 + 3 + 1 is equivalent to (7 + 3) + 1
7 - 3 - 1 is equivalent to (7 - 3) - 1
8 * 4 * 2 is equivalent to (8 * 4) * 2
8 / 4 / 2 is equivalent to (8 / 4) / 2

什么是运算标记的左连系性呢？

当表达式7 + 3 + 1中的3之类的操作数在两侧都带有加号时，我们须要商定来肯定哪一个运算符实用于3，是左侧的加号照样右侧的加号？我们说运算符加号左连系，是由于在存在两侧都带有加号的操作数时，此时左侧的加号实用于此操作数，因而我们说运算符加号是左连系的(The operator + associates to the left because an operand that has plus signs on both sides belongs to the operator to its left and so we say that the operator + is left-associative.)，所以依据连系性通例，7 + 3 + 1即是（7 + 3）+ 1。

我们再来看7 + 5 * 2这个表达式，在操作数5的双方都有差别范例的运算符，该表达式即是7 +（5 * 2）照样（7 + 5）* 2呢？我们怎样处理这类歧义？

在这类情况下，连系性商定对我们没有协助，由于它仅实用于加减法（+，-）或乘除法（*，/）这类统一范例的运算符。当我们在统一表达式中具有差别品种的运算符时，我们须要另一种商定来处理歧义。我们须要一个定义运算符相对优先级的商定。

我们说假如运算符乘号在加号之前实行其操作数，则乘号具有更高的优先级(higher precedence)。在我们所运用的运算中，乘法和除法的优先级高于加法和减法，所以表达式7 + 5 * 2等效于7 +（5 * 2），表达式7 - 8 / 4等效于7-（8 / 4）。

在含有优先级雷同的运算符的表达式中，我们仅运用连系性商定并从左到右实行运算符：

7 + 3 - 1 is equivalent to (7 + 3) - 1
8 / 4 * 2 is equivalent to (8 / 4) * 2

愿望你不要由于这些运算符的连系性和优先级而觉得无聊，我们能够应用这些商定来组织算术表达式的语法，以显现算术运算符的连系性和优先级，然后，我们能够依据我在中概述的准则将语法转换为代码，我们的诠释器将能够处置惩罚运算符的优先级和连系性商定。

这是我们的优先级表(precedence table)：

从表中能够看出，运算符加号和减号具有雷同的优先级，而且它们都是左连系的，还能够看到，运算符乘号和除号也是左连系的，它们之间也具有雷同的优先级，然则比加减运算符具有更高的优先级。

以下是有关怎样依据优先级表组织语法的划定规矩：

1、为每一类优先级定义一个非终结符。非最终符的发生式主体应包括该类优先级的算术运算符和下一类更高优先级的非终结符。( The body of a production for the non-terminal should contain arithmetic operators from that level and non-terminals for the next higher level of precedence.)

2、为基础的表达单元（在本文下为整数）建立一个附加的非终结符factor。平常划定规矩是，假如具有N类优先级，则统共将须要N + 1个非终结符：每类级别一个非终结符（N个）再加上一个运算基础单元的非终结符factor（1个）。(Create an additional non-terminal factor for basic units of expression, in our case, integers. The general rule is that if you have N levels of precedence, you will need N + 1 non-terminals in total: one non-terminal for each level plus one non-terminal for basic units of expression.)

继承！

让我们遵照划定规矩并构建语法。

依据划定规矩1，我们将定义两个非终结符：一个用于级别2的称为expr的非终结符和一个用于级别1的称为term的非终结符，经由过程划定规矩2，我们将为算术的基础单元定义一个非终结符factor来表达整数。

新语法的肇端标记将为expr，expr的发生式将包括一个示意运用级别2的运算符主体，在本例中为加号和减号，并将包括更高级别优先级的非终结符term。
级别2：

term发生式将包括一个运用级别1运算符的主题，即运算符乘号和除号，而且它也包括基础表达式单元（整数）的非终结符factor：

非终结符factor的发生式为：

你已经在之前的文章看见过以上发生式的语法和语法图，在这里，考虑到连系性和优先级，我们将它们组合成一个语法：

这是与上面的语法相对应的语法图：

图中的每一个矩形框都是对另一个图的“函数挪用(method call)”。 假如你采纳表达式7 + 5 * 2并从顶部expr入手下手，然后一向走到最底部的factor，那末应当能够看到较高优先级的运算符乘号和除号在较低的图中，运算符加号和减号在较高的图中，而且高优先级的运算符先实行。

让我们看一下依据上面的语法和语法图来对算术表达式7 + 5 * 2盘算的剖析步骤，这是显现高优先级运算符先于低优先级运算符实行的另一种体式格局：

好的，让我们依据第4部份中的指点要领将语法转换为代码，然后看看我们的新诠释器怎样事情。

这是语法：

这是盘算器的完全代码，能够处置惩罚包括恣意数目的加，减，乘和除整数运算的有用算术表达式。

与第4部份中的代码比拟，以下是重要转变的处所：

1、Lexer类如今能够对+，-，*和/举行标记化（这里没有什么新颖的，我们只是将以前文章中的代码组合到一个支撑所有这些Token的类中）
2、追念一下，在语法中定义的每一个划定规矩（发生式）R都邑转换为具有雷同称号的函数，而且对该划定规矩的援用会成为函数挪用：R()， 所以Interpreter类如今具有对应于语法中三种非终结符函数：expr，term和factor。
源代码：

# Token types
#
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis
INTEGER, 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 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
        lexer = Lexer(text)
        interpreter = Interpreter(lexer)
        result = interpreter.expr()
        print(result)


if __name__ == '__main__':
    main()

将以上代码保存到calc5.py文件中，或直接从下载,尝试一下，然后本身看看诠释器是不是正确地盘算了具有差别优先级运算符的算术表达式。

这是我的笔记本电脑上的运转结果：

$ python calc5.py
calc> 3
3
calc> 2 + 7 * 4
30
calc> 7 - 8 / 4
5
calc> 14 + 2 * 3 - 6 / 2
17

接下来是本日的演习：

1、在不阅读本文代码的情况下编写本文所述的诠释器，完成后编写一些测试，并确保它们经由过程。

2、扩大诠释器以处置惩罚包括括号的算术表达式，以便你的诠释器能够盘算深度嵌套的算术表达式，比方：7 + 3 *（10 /（12 /（3 + 1）-1））

末了再来温习回想一下：

1、运算符的左连系是什么意义？
2、运算符加号和减号是左连系照样右连系？ 乘号和除号呢？
3、运算符加号的优先级是不是比运算符乘号高？

嘿，你一向阅读到末了！ 真的很棒 下次我会再写一篇新文章，敬请期待。

Swift--struct与class的区别(汇编角度底层分析)