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()