本文将指导你如何使用 Python 构建一个能够解析和求值后缀表达式的解析器。我们将从词法分析（tokenize）开始，然后构建一个递归下降解析器，并最终实现表达式求值功能。我们将重点解决解析器在处理操作符顺序时的常见错误，并提供一个可工作的示例。
词法分析器 (Tokenizer)
词法分析器的作用是将输入的字符串（源代码）分解成一个个的 token。每个 token 代表源代码中的一个有意义的单元，例如数字、操作符、空白符等。
import re
token_patterns = [
('OPERATOR', r'[+\-*/]'),
('NUMBER', r'\d+'),
('WHITESPACE', r'\s+'),
]
def tokenize(source_code):
tokens = []
source_code = source_code.strip()
while source_code:
matched = False
for token_type, pattern in token_patterns:
match = re.match(pattern, source_code)
if match:
value = match.group(0)
tokens.append((token_type, value))
source_code = source_code[len(value):].lstrip()
matched = True
break
if not matched:
raise ValueError(f"Invalid character in source code: {source_code[0]}")
return tokens这段代码定义了一个 tokenize 函数，它接收源代码字符串作为输入，并返回一个 token 列表。每个 token 是一个元组，包含 token 类型和 token 值。正则表达式用于匹配不同类型的 token。
解析器 (Parser)
解析器的作用是将 token 列表转换成一个抽象语法树 (AST)，AST 能够更清晰地表达表达式的结构。对于后缀表达式，AST 可以简化为嵌套的元组结构。
立即学习“Python免费学习笔记（深入）”；
原始代码的问题在于后缀表达式的解析顺序错误。后缀表达式的特点是操作符位于操作数之后，因此解析时需要先解析右操作数，再解析左操作数。
以下是修正后的解析器代码：
def parse_expression(tokens):
if not tokens:
return None
token_type, value = tokens.pop() # 从列表末尾取元素
if token_type == 'NUMBER':
return int(value)
elif token_type == 'OPERATOR':
if value in ('+', '-', '*', '/'):
right = parse_expression(tokens)
left = parse_expression(tokens)
return (value, left, right)
else:
raise ValueError(f"Unexpected operator: {value}")
else:
raise ValueError(f"Unexpected token: {token_type}")关键的修改在于使用 tokens.pop() 从 token 列表的 末尾 取出 token。这样可以保证按照后缀表达式的顺序进行解析。
求值器 (Evaluator)
求值器的作用是根据 AST 计算表达式的值。
def evaluate_expression(expression):
if isinstance(expression, int):
return expression
elif isinstance(expression, tuple):
operator, left, right = expression
if operator == '+':
return evaluate_expression(left) + evaluate_expression(right)
elif operator == '-':
return evaluate_expression(left) - evaluate_expression(right)
elif operator == '*':
return evaluate_expression(left) * evaluate_expression(right)
elif operator == '/':
return evaluate_expression(left) / evaluate_expression(right)
else:
raise ValueError(f"Invalid expression: {expression}")求值器递归地计算表达式的值。如果表达式是一个数字，则直接返回该数字。如果表达式是一个元组，则递归地计算左操作数和右操作数的值，然后根据操作符进行计算。
完整代码示例
import re
token_patterns = [
('OPERATOR', r'[+\-*/]'),
('NUMBER', r'\d+'),
('WHITESPACE', r'\s+'),
]
def tokenize(source_code):
tokens = []
source_code = source_code.strip()
while source_code:
matched = False
for token_type, pattern in token_patterns:
match = re.match(pattern, source_code)
if match:
value = match.group(0)
tokens.append((token_type, value))
source_code = source_code[len(value):].lstrip()
matched = True
break
if not matched:
raise ValueError(f"Invalid character in source code: {source_code[0]}")
return tokens
def parse_expression(tokens):
if not tokens:
return None
token_type, value = tokens.pop() # 从列表末尾取元素
if token_type == 'NUMBER':
return int(value)
elif token_type == 'OPERATOR':
if value in ('+', '-', '*', '/'):
right = parse_expression(tokens)
left = parse_expression(tokens)
return (value, left, right)
else:
raise ValueError(f"Unexpected operator: {value}")
else:
raise ValueError(f"Unexpected token: {token_type}")
def evaluate_expression(expression):
if isinstance(expression, int):
return expression
elif isinstance(expression, tuple):
operator, left, right = expression
if operator == '+':
return evaluate_expression(left) + evaluate_expression(right)
elif operator == '-':
return evaluate_expression(left) - evaluate_expression(right)
elif operator == '*':
return evaluate_expression(left) * evaluate_expression(right)
elif operator == '/':
return evaluate_expression(left) / evaluate_expression(right)
else:
raise ValueError(f"Invalid expression: {expression}")
def main():
source_code = "2 3 4 * +"
tokens = tokenize(source_code)
tokens.reverse() # 逆转列表，因为我们从末尾pop
parsed_expression = parse_expression(tokens)
print(f"Source code: {source_code}")
print(f"Parsed expression: {parsed_expression}")
result = evaluate_expression(parsed_expression)
print(f"Result: {result}")
if __name__ == "__main__":
main()输出:
Source code: 2 3 4 * +
Parsed expression: ('+', 2, ('*', 3, 4))
Result: 14总结与注意事项
- 后缀表达式的解析顺序: 后缀表达式的关键在于操作符位于操作数之后。因此，在解析时需要从 token 列表的末尾开始，先解析右操作数，再解析左操作数。
- 错误处理: 在实际应用中，需要添加更完善的错误处理机制，例如处理除零错误、无效操作符等。
- 代码可读性: 为了提高代码的可读性，可以使用更具描述性的变量名和注释。
- 调试技巧: 使用 print 语句可以帮助你调试解析器和求值器，了解程序的执行流程和变量的值。
- tokens.reverse(): 由于我们修改后的 parse_expression 函数从 token 列表的末尾弹出元素，所以需要在调用 parse_expression 之前使用 tokens.reverse() 反转 token 列表，以确保正确的解析顺序。
通过本文，你应该能够理解如何使用 Python 构建一个基本的后缀表达式解析器和求值器。希望这个教程能够帮助你更好地理解编译原理和解析器的实现。
