1.介绍

本系列文章参照该教程学习总结,欢迎查看原文。我个人的学习代码已经放到我的github
 词法分析、语法分析、语义分析等定义请参考编译器解释器中的词法分析、语法分析、语义分析

英文原作者所有源代码查看

2.改善加法解释器

在第一章中我们实现了一个简单的解释器，本节将增添减法、多位数和跳过空格的支持。在前面的作业中，我们已经做过了一部分内容，接下来就看看作者给出的代码和我们有什么区别吧。

calc3.py代码如下 

import pdb
INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'


class Token(object):

    def __init__(self, type, value):
        self.type = type
        self.value = value

    def __str__(self):
        return 'Token({type},{value})'.format(
            type=self.type,
            value=repr(self.value)
        )


class Interpreter(object):

    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.current_token = None
        self.current_char = self.text[self.pos]

    def error(self):
        raise Exception('Error parsing input')

    def advance(self):  # 这个方法是新增的，用于移动指针修改self.current_char的值
        self.pos += 1
        if self.pos > len(self.text) - 1:
            self.current_char = None
        else:
            self.current_char = self.text[self.pos]

    def skip_whitespace(self):  # 这个方法用于配合advance方法跳过空格
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):  # 获取多位数的数字串
        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):
        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())   # 注意这里使用了一个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):
        if self.current_token.type == token_type:
            self.current_token = self.get_next_token()
        else:
            self.error()

    def expr(self):
        self.current_token = self.get_next_token()

        left = self.current_token
        self.eat(INTEGER)

        op = self.current_token
        if op.type == PLUS:
            self.eat(PLUS)

        else:
            self.eat(MINUS)

        right = self.current_token
        self.eat(INTEGER)

        if op.type == PLUS:
            result = left.value + right.value
        else:
            result = left.value - right.value

        return result


def main():
    while True:
        try:
            text = input('calc>')
        except EOFError:
            break
        if not text:
            continue
        interpreter = Interpreter(text)
        result = interpreter.expr()
        print(result)


if __name__ == '__main__':
    main()

2.1 与自己写的代码对比

相比自己写的代码改进的地方：

  1. get_next_token()方法结构清晰很多，仅仅做期望类型的判断匹配，功能上高内聚。
  2. 通过引入advance()方法来移动指针，修改current_char还有integer()方法来获取完整的多位数数字串，成功从get_next_token方法解耦了相关移动pos和更新值的代码

2.2 概念复习和升华

  • 词汇单位/词位(lexeme): lexeme 就是组成 token 的字符序列。在下面的图片中你可以看到一些 token 和 lexeme 的示例，希望已经把它们之间的关系表达清楚了

  • 语法分析(parsing):识别 token 流中的短语（短语例如：INTEGER->PLUS->INTEGER）。该过程称之为 parsing（语法分析）
  • 语法分析器:解释器或编译器中用以完成识别 token 流中的短语的工作的部分，称之为 parser（语法分析器）。例如代码中的expr方法，以及调用的get_next_token

    expr 方法是解释器中既做了 parsing（语法分析）又做了 interpreting（解释）的部分。expr 方法首先试图识别（parsing）token 流中的 INTEGER -> PLUS -> INTEGER 或 INTEGER -> MINUS -> INTEGER 短语，成功完成识别（parsed）其中一种短语后，该方法解释它，并将两整数相加或相减的结果返回给调用者。

3. 练习

最后又布置了一道题目是继续改进程序，使得其支持乘除法和长式子（不支持分辨乘除优先级）计算例如：“9 – 5 + 3 + 11”。我们通过前面给出的代码的基础上自己实现一遍加深理解。（以下代码并不一定是最好的，仅仅是个人练习的产出，建议自己实现一遍才有意义）

calc4.py代码如下 

import pdb
INTEGER, PLUS, MINUS, MULTIPLY, DIVIDE, EOF = 'INTEGER', 'PLUS', 'MINUS', 'MULTIPLY', 'DIVIDE', 'EOF'
'''改进以支持整数乘除和长式子(长式子不之分区分乘除优先级)'''


class Token(object):

    def __init__(self, type, value):
        self.type = type
        self.value = value

    def __str__(self):
        return 'Token({type},{value})'.format(
            type=self.type,
            value=repr(self.value)
        )


class Interpreter(object):

    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.current_token = None
        self.current_char = self.text[self.pos]

    def error(self):
        raise Exception('Error parsing input')

    def advance(self):  # 这个方法是新增的，用于移动指针修改self.current_char的值
        self.pos += 1
        if self.pos > len(self.text) - 1:
            self.current_char = None
        else:
            self.current_char = self.text[self.pos]

    def skip_whitespace(self):  # 这个方法用于配合advance方法跳过空格
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):  # 获取多位数的数字串
        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):
        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())   # 注意这里使用了一个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(MULTIPLY, '*')

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

            self.error()

        return Token(EOF, None)

    def eat(self, token_type):
        if self.current_token.type == token_type:
            self.current_token = self.get_next_token()
        else:
            self.error()

    def expr(self):

        self.current_token = self.get_next_token()
        final_result = 0  # 这个才是最后的结果
        result = 0          # 保留每一轮计算的临时结果
        while self.current_token.type != EOF:     # 每一趟循环获取一次计算的结果叠加到final_result
            # pdb.set_trace()
            if self.current_token.type == INTEGER:  # 如果是数字，说明第一次进循环
                left = self.current_token
                self.eat(INTEGER)
            else:   # 如果不是数字则不是第一次进循环，需要将left的值设定为上一次的结果
                left = Token(INTEGER, result)

            op = self.current_token
            if op.type == PLUS:
                self.eat(PLUS)

            elif op.type == MINUS:
                self.eat(MINUS)
            elif op.type == MULTIPLY:
                self.eat(MULTIPLY)
            else:
                self.eat(DIVIDE)

            right = self.current_token
            self.eat(INTEGER)

            if op.type == PLUS:
                result = left.value + right.value
            elif op.type == MINUS:
                result = left.value - right.value
            elif op.type == MULTIPLY:
                result = left.value * right.value
            else:
                result = left.value / right.value

        final_result += result
        return final_result


def main():
    while True:
        try:
            text = input('calc>')
        except EOFError:
            break
        if not text:
            continue
        interpreter = Interpreter(text)
        result = interpreter.expr()
        print(result)


if __name__ == '__main__':
    main()