简单算术表达式语法分析器

一个简单的算术表达式语法分析器可以根据下面的 BNF 文法来实现：

<expr> ::= <term> {<addop> <term>}
<term> ::= <factor> {<mulop> <factor>}
<factor> ::= <number> | '(' <expr> ')'
<addop> ::= '+' | '-'
<mulop> ::= '*' | '/'
<number> ::= <digit> {<digit>}
<digit> ::= '0' | '1' | ... | '9'

其中，`<expr>` 表示一个表达式，`<term>` 表示一个项，`<factor>` 表示一个因子，`<addop>` 表示加减运算符，`<mulop>` 表示乘除运算符，`<number>` 表示一个数字，`<digit>` 表示一个数字位。

我们可以使用递归下降的方式来实现语法分析器。具体来说，我们可以为每个非终结符号编写一个函数，这些函数将递归地调用其他函数来解析它们所代表的部分，并返回解析结果。例如，下面是一个可能的实现：

class SyntaxError(Exception):
    pass

class Parser:
    def __init__(self, text):
        self.tokens = self.tokenize(text)
        self.pos = 0

    def tokenize(self, text):
        # 将文本分解为一个个 token
        ...

    def parse(self):
        # 解析整个表达式
        result = self.parse_expr()
        if self.pos != len(self.tokens):
            raise SyntaxError('Unexpected token: {}'.format(self.tokens[self.pos]))
        return result

    def parse_expr(self):
        # 解析表达式
        result = self.parse_term()
        while self.pos < len(self.tokens) and self.tokens[self.pos][0] in '+-':
            op = self.tokens[self.pos][0]
            self.pos += 1
            right = self.parse_term()
            if op == '+':
                result += right
            else:
                result -= right
        return result

    def parse_term(self):
        # 解析项
        result = self.parse_factor()
        while self.pos < len(self.tokens) and self.tokens[self.pos][0] in '*/':
            op = self.tokens[self.pos][0]
            self.pos += 1
            right = self.parse_factor()
            if op == '*':
                result *= right
            else:
                result /= right
        return result

    def parse_factor(self):
        # 解析因子
        if self.tokens[self.pos][0] == '(':
            self.pos += 1
            result = self.parse_expr()
            if self.tokens[self.pos][0] != ')':
                raise SyntaxError('Expected )')
            self.pos += 1
            return result
        elif self.tokens[self.pos][1] == 'NUMBER':
            result = int(self.tokens[self.pos][0])
            self.pos += 1
            return result
        else:
            raise SyntaxError('Expected number or (')

在这个实现中，`Parser` 类接受一个表达式文本，并将其分解为一个个 token。然后，我们可以调用 `parse` 方法来解析整个表达式。这个方法首先调用 `parse_expr` 函数来解析表达式，然后检查是否所有 token 都已经被解析。如果还有剩余的 token，我们就抛出一个 `SyntaxError` 异常。

`parse_expr` 函数解析表达式。它首先调用 `parse_term` 函数来解析第一个项，然后进入一个循环，直到没有更多的加减运算符为止。在循环中，我们解析下一个项和运算符，并根据运算符来更新结果。

`parse_term` 函数解析项。它的工作方式与 `parse_expr` 函数类似，但是它处理乘除运算符。

`parse_factor` 函数解析因子。如果当前 token 是左括号，则我们解析一个表达式，然后检查下一个 token 是否是右括号。否则，如果当前 token 是数字，则我们将其解析为一个整数。否则，我们抛出一个 `SyntaxError` 异常。