1.介绍

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

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

2. 抽象语法树(abstract syntax tree)和分析树(parser tree or concrete syntax tree)

使用树这样的数据结构来表达中间表达式

下图用一个树结构来表达2*7+3

2.1 分析树(parser tree)

分析树:表示一个给定的输入如何根据相应的文法转化成语言。
分析树的样子如下,可见能看出产生式的应用:

2.2 抽象分析树(AST)

AST和parser tree的效果如下。从对比可以看出来,AST中简化了产生式的替换,更加的简介紧凑。AST是解释器中核心的数据结构。此外从图上可知,AST是按照后续遍历的。

产生一个AST需要的数据结构:

class AST(object):
    pass


class BinOp(AST):

    '''不专门再为各个符号定义节点类,而是定义一个二元操作符类,即“左值 符号 右值”这样的形式'''

    def __init__(self, left, op, right):
        self.left = left
        self.token = self.op = op
        self.right = right


class Num(AST):
    '''用来表示AST当中的数字节点'''

    def __init__(self, token):
        self.token = token_type
        self.value = token.value

2.3 后续遍历

后续遍历伪代码

3. 完整代码

这里特别值得注意的一个设计思想是:
通过反射技术在visit函数中获取到visit_NodeType 方法,这里的NodeType为Num或者BinOp,因此可以获取的方法为visit_Num或者visit_BinOp。在python的标准库里面也是类似的的方法去调用不同的访问节点的方法。也就是说扩展了更多的NoteType类型,可以动态地调用不同的方法。

基本的过程可以理解为:


与之前的代码相比,Integer类现在通过遍历Parser处理时产生的AST来计算结果

""" SPI - Simple Pascal Interpreter """

###############################################################################
#                                                                             #
#  LEXER     词法分析                                                         #
#                                                                             #
###############################################################################

# 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, LPAREN, RPAREN, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'
)


class Token(object):

    def __init__(self, type, value):
        self.type = type
        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. "4 + 2 * 3 - 6 / 2"
        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, '/')

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

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

            self.error()

        return Token(EOF, None)


###############################################################################
#                                                                             #
#  PARSER      语法分析                                                       #
#                                                                             #
###############################################################################

class AST(object):
    pass


class BinOp(AST):

    '''二元操作符'''

    def __init__(self, left, op, right):
        self.left = left
        self.token = self.op = op
        self.right = right


class Num(AST):

    '''AST上的数字节点类'''

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


class Parser(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 | LPAREN expr RPAREN"""
        token = self.current_token
        if token.type == INTEGER:
            self.eat(INTEGER)
            return Num(token)   # 将token放在Num对象当中
        elif token.type == LPAREN:
            self.eat(LPAREN)
            node = self.expr()
            self.eat(RPAREN)
            return node

    def term(self):
        """term : factor ((MUL | DIV) factor)*"""
        node = self.factor()

        while self.current_token.type in (MUL, DIV):
            token = self.current_token
            if token.type == MUL:
                self.eat(MUL)
            elif token.type == DIV:
                self.eat(DIV)

            # 这里使用factor()方法,和我们给出的产生式一致
            node = BinOp(left=node, op=token, right=self.factor())

        return node

    def expr(self):
        # expr用于语法分析,检查语法合法性,同时构建AST,最后返回AST的根节点
        """
        expr   : term ((PLUS | MINUS) term)*
        term   : factor ((MUL | DIV) factor)*
        factor : INTEGER | LPAREN expr RPAREN
        """
        node = self.term()

        while self.current_token.type in (PLUS, MINUS):
            token = self.current_token
            if token.type == PLUS:
                self.eat(PLUS)
            elif token.type == MINUS:
                self.eat(MINUS)

            # 采用BinOp来产生当前节点和左右孩子(当然也可能为空)
            # 这里仍然是调用term()方法,和我们给出的产生式要一致
            node = BinOp(left=node, op=token, right=self.term())

        return node  # expr最后返回的是AST的根节点

    def parse(self):
        return self.expr()


###############################################################################
#                                                                             #
#  INTERPRETER                                                                #
#                                                                             #
###############################################################################

class NodeVisitor(object):

    '''用于遍历AST'''

    def visit(self, node):
        method_name = 'visit_' + type(node).__name__    # 动态的获取方法的名字,为visit_Num或者visit_BinOp
        visitor = getattr(self, method_name, self.generic_visit)
        return visitor(node)    # 根据前面获取的内容不同,这里的visitor可能为visit_Num或者为visit_BinOp

    def generic_visit(self, node):
        raise Exception('No visit_{} method'.format(type(node).__name__))


class Interpreter(NodeVisitor):  # 注意继承了NodeVisitor

    def __init__(self, parser):
        self.parser = parser

    def visit_BinOp(self, node):
        if node.op.type == PLUS:
            return self.visit(node.left) + self.visit(node.right)   # 调用了父类当中的 visit方法
        elif node.op.type == MINUS:
            return self.visit(node.left) - self.visit(node.right)
        elif node.op.type == MUL:
            return self.visit(node.left) * self.visit(node.right)
        elif node.op.type == DIV:
            return self.visit(node.left) / self.visit(node.right)

    def visit_Num(self, node):
        return node.value

    def interpret(self):
        # 将解释器的功能单独的分离出来,即用于一边访问AST一边计算,最后得到结果
        tree = self.parser.parse()  # 得到AST
        return self.visit(tree)     # visit  方法中会根据节点的类型使用不同的访问方法visit_Num或者visit_BinOp


def main():
    while True:
        try:
            try:
                text = input('spi> ')
            except NameError:  # Python3
                text = input('spi> ')
        except EOFError:
            break
        if not text:
            continue

        lexer = Lexer(text)
        parser = Parser(lexer)
        interpreter = Interpreter(parser)
        result = interpreter.interpret()
        print(result)


if __name__ == '__main__':
    main()

4. 总结

这一章主要是引入了一个新概念抽象语法分析树AST,然后改造了原来的代码。语法分析利用Lexer类产生一个AST树,然后Interpreter类中的interpret方法遍历这棵树,同时得出结果。这样代码职责更加清晰,当问题复杂了可以更好的分离代码。因为复杂表达式转化成AST然后再分析AST比较高效。