1.介绍

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

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

2. 个位数加法

文章第一篇实现了一个个位数加法的解释器(不支持包含空格),虽然比较简单,但是通过一个小练习可以了解一些解释器需要涉及的一些基本概念和处理过程。

2.1 记号(token)和词法分析器(lexical ananlyzer or lexer)

记号(token)是一对元素,即(类型,值)

解释器或者编译器将输入字符串转换成一串记号(tokens)的过程就是词法分析的过程也就是lexer的工作了

3. 代码实现

代码中比较重要的类是:

  1. Token: 记号类型,保存类型和值
  2. Intepreter: 解释器类型,调用其中的方法可以完成词法分析

代码中比较重要的方法的调用链:
expr()->eat()->get_next_token()

expr()用于调用eat()方法检验输入是否符合期望的类型,同时计算结果
eat()就是用来判断输入的内容的类型是否符合期望的类型
get_next_token()通过一个指针移动获取响应的token

calc1.py如下

import pdb
'''该程序用于处理个位数的加法'''


# EOF标记用于说明没有更多的内容需要此法分析器来分析
INTEGER, PLUS, EOF = 'INTEGER', 'PLUS', 'EOF'


class Token(object):  # Token表示一个对<类型,值>例如表达式"3+5"中的3对应的token是<3,INTEGER>

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

    def __repr__(self):
        return self.__str__()


class Interpreter(object):

    def __init__(self, text):  # text指整个表达式比如"3+5"
        self.text = text
        self.pos = 0  # 记录指针的位置,用于分析text
        self.current_token = None  # 记录当前的token比如"3"

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

    def get_next_token(self):
        '''完成词法分析器的功能, 将完整的text分隔成多个tokens'''
        text = self.text
        if self.pos > len(text) - 1:  # 如果指针位置到末尾了
            return Token(EOF, None)

        current_char = text[self.pos]

        # 如果没到末尾,判断是否是数字,是数字则返回对应的Token
        if current_char.isdigit():
            token = Token(INTEGER, int(current_char))
            self.pos += 1
            return token

        # 如果是符号
        if current_char == '+':
            token = Token(PLUS, current_char)
            self.pos += 1
            return token

        self.error()

    def eat(self, token_type):
        '''该方法用于计算表达式,判断实际的token与预期的token_type的类型是否相等'''
        # pdb.set_trace()
        if self.current_token.type == token_type:
            self.current_token = self.get_next_token()
        else:
            self.error()

    def expr(self):    # 词法分析器的代码段
        '''计算表达式例如:INTEER PLUS INTEGER'''
        # pdb.set_trace()
        self.current_token = self.get_next_token()
        left = self.current_token
        self.eat(INTEGER)  # 预期输入的第一个token是数字

        op = self.current_token
        self.eat(PLUS)

        right = self.current_token
        self.eat(INTEGER)

        # 此时的current_token变成EOF,可以返回结果
        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()

文章最后布置了另外一道题目,把以上代码改成能支持整数加减法。这里需要注意,虽然实现整数加减法师很简单的,但是我们尽量不改动以上代码的核心框架,因为这个是实现解释器的基础。也就是说,接下来实现的代码也必须包含词法分析,表达式类型匹配等核心操作。以下代码是个人写的版本,和第二章作者给出的答案不同,大家可以对照着看。最好自己写一遍,看看自己哪些地方思考的不够好。

calc2.py代码如下

import pdb
'''该程序用于处理多位数的加减法'''


# EOF标记用于说明没有更多的内容需要此法分析器来分析
INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'


class Token(object):  # Token表示一个对<类型,值>例如表达式"3+5"中的3对应的token是<3,INTEGER>

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

    def __repr__(self):
        return self.__str__()


class Interpreter(object):

    def __init__(self, text):  # text指整个表达式比如"3+5"
        self.text = text
        self.pos = 0  # 记录指针的位置,用于分析text
        self.current_token = None  # 记录当前的token比如"3"

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

    def isOp(self, text):
        '''用于判断是否是操作符'''
        if text == '+' or text == '-':
            return True
        else:
            return False

    def get_next_token(self):
        '''完成词法分析器的功能, 将完整的text分隔成多个tokens'''
        text = self.text
        length = len(text)  # 字符总长度
        if self.pos > length - 1:  # 如果指针在末尾(pos从0开始)
            return Token(EOF, None)
        current_char = text[self.pos]
        if self.isOp(current_char):
            if current_char == '+':
                token = Token(PLUS, current_char)
                self.pos += 1
                return token
            if current_char == '-':
                token = Token(MINUS, current_char)
                self.pos += 1
                return token

        s = ''
        while True:  # 如果没到末尾,判断是否是数字,是数字则继续移动指针直到遇到操作符获取整个数字
            if current_char.isdigit():  # 如果是数字
                s += current_char  # 如果是数字则追加到list
                self.pos += 1  # 移动指针,之后的判断都是对pos+1后的位置的值进行判断
            # 遇到符号要计算整个INTEGER的值
            if self.isOp(current_char):    # 如果是符号,则把之前记录下来的一串字符作为Token返回
                # 将list先转化成str再转化成int的整数
                # pdb.set_trace()
                token = Token(INTEGER, int(s))
                return token
            # 遇到最后个数字要计算整个INTEGER的值
            if self.pos > length - 1:  # 如果指针在末尾(pos从0开始)
                token = Token(INTEGER, int(s))
                return token

            else:
                current_char = text[self.pos]  # 重新获取下一个字符
                continue
        self.error()

    def eat(self, token_type):
        '''该方法用于计算表达式,判断实际的token与预期的token_type的类型是否相等'''
        # pdb.set_trace()
        if self.current_token.type == token_type:
            self.current_token = self.get_next_token()
        else:
            self.error()

    def expr(self):
        '''计算表达式例如:INTEER PLUS INTEGER'''
        # pdb.set_trace()
        self.current_token = self.get_next_token()
        left = self.current_token
        self.eat(INTEGER)  # 预期输入的第一个token是数字

        op = self.current_token.value
        if op == '+':
            self.eat(PLUS)
        elif op == '-':
            self.eat(MINUS)

        right = self.current_token
        self.eat(INTEGER)

        # self.current_token = self.get_next_token()
        # self.eat(EOF)

        # 此时的current_token变成EOF,可以返回结果
        result = 0
        if op == '+':
            result = left.value + right.value
            return result
        if op == '-':
            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()