1.介绍

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

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

2. 优先级和语法图

2.1 优先级

associativiy表示左结合
优先级表格构建文法规则：

  1. 为每个优先级定义一个非终结符。非终结符所在产生式的主体应该包含同等级的算术运算符和优先级高一级的非终结符。
  2. 为表达式创建一个额外的非终结符 factor 作为基本单位，在我们的例子中该基本单位是整数。通用的规则是如果你有 N 层优先级，那么你总共需要 N + 1 个非终结符：每层优先级需要一个非终结符，加上一个用作表达式基本单位的非终结符。（在本例中，是2层优先级，需要3个非终结符expr,term,factor）

2.2 构造文法

根据2.1优先级表格规则来构建文法
 根据规则 1，我们要定义两个非终结符：用于等级 2 的非终结符称为 expr，用于等级 1 的非终结符称为 term。而根据规则 2，我们将定义一个 factor （即一个整数）用作算术表达式的基本单位。

新文法的开始符号是 expr，expr 产生式包含一个主体，该主体使用来自等级 2 的运算符（在我们的例子中是 + 和 – 运算符）。同时 expr 产生式也包含更高优先级（等级 1）的 term 非终结符：

term 表达式包含一个主体，该主题使用来自等级 1 的运算符（在我们的例子中是 * 和 /）。同时 term 产生式也包含用作表达式基本单位的 factor（即整数）：


而非终结符 factor 的产生式是：


因此，我们得到三个产生式（规则）为：


根据产生式我们可以得到语法图：


根据如下语法图规则我们就可以转化成相应的代码

例如7 + 5 * 2 的分解可以用下图来表示：

根据文法给出的信息，我们可以写出代码： 

'''计算乘除法的计算器'''
INTEGER, PLUS, MINUS, MUL, DIV, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '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)
        )

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


class Lexer(object):

    '''词法分析器(Scanner)'''

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

    def error(self):
        raise Exception('Invalid syntax')

    def advance(self):
        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):
        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())
            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
        self.current_token = self.lexer.get_next_token()

    def error(self):
        raise Exception('Invalid syntax')

    def eat(self, token_type):
        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):
        ########################################################################################
        #                                                                                      #
        # 对于14+2*3-6/2 这个表达式来说，14首先通过term方法处理，直接返回14                    #
        # 然后遇到+号，直接进入expr中的while判断代码，把+号后的代码看成一个term整体，通过      #
        # term方法可以返回2*3的值，然后又到expr中的while判断代码判断是否操作符是加减号，发现是 #
        # 减号，又把减号后面的东西当做整体term操作，得到6/2的值，然后result减去该值得到        #
        # 最后结果，最后判断的时候结果为EOF，则退出expr函数                                    #
        #                                                                                      #
        # 解答这道题的关键是根据相应的语法图来写代码，在expr这一层内不要混进factor()函数       #
        # 如果混进该方法，则与语法图表达的就不一致（我就因为这个一开始没想出来咋做）           #
        ########################################################################################
        result = self.term()
        while self.current_token.type in (PLUS, MINUS):
            token = self.current_token
            if token.type == PLUS:
                self.eat(PLUS)
                result += self.term()
            elif token.type == MINUS:
                self.eat(MINUS)
                result -= self.term()

        return result


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

if __name__ == '__main__':
    main()