编译原理实战基于Python 3.11构建四则运算词法分析器词法分析作为编译器的第一道工序其核心任务是将字符流转换为有意义的单词序列。本文将以Python 3.11为开发环境从零实现一个能够识别四则运算表达式包含数字、运算符和括号的词法分析器。通过这个实践项目您将深入理解有限自动机(DFA)的理论如何转化为实际代码。1. 词法分析器设计基础词法分析器的本质是模式识别引擎需要处理以下核心问题如何定义各类词法单元token的模式如何高效扫描输入字符串如何处理边界条件和错误情况在四则运算场景中我们需要识别的token类型包括整数如42浮点数如3.14运算符,-,*,/括号(,)空白字符通常被忽略1.1 有限自动机的Python实现策略确定有限自动机(DFA)的实现有两种典型方式状态转移表法用二维表格显式表示状态转移条件分支法用代码逻辑隐式表达状态转移我们将采用第二种方式因为它更符合Python的动态特性代码也更具可读性。以下是关键状态定义from enum import Enum, auto class State(Enum): START auto() IN_INTEGER auto() IN_FLOAT auto() IN_OPERATOR auto() IN_PAREN auto() ERROR auto()1.2 正则表达式与手工实现的权衡虽然Python的re模块可以快速实现词法分析但手工实现DFA更有教学价值更直观展示状态转移过程更容易添加自定义错误处理性能通常更优避免正则引擎开销下表对比两种实现方式的特性特性正则表达式实现手工DFA实现开发速度快慢运行效率中等高可调试性差好错误处理灵活性有限完全可控教学价值低高2. 核心实现解析2.1 Token类型定义首先定义词法单元的数据结构from dataclasses import dataclass from typing import Literal dataclass class Token: type: Literal[INTEGER, FLOAT, OPERATOR, PAREN] value: str position: int # 在源字符串中的起始位置2.2 词法分析器类框架构建词法分析器的主框架class Lexer: def __init__(self, text: str): self.text text self.pos 0 self.current_char self.text[self.pos] if self.text else None def advance(self): 移动到下一个字符 self.pos 1 if self.pos len(self.text): self.current_char self.text[self.pos] else: self.current_char None def skip_whitespace(self): 跳过空白字符 while self.current_char is not None and self.current_char.isspace(): self.advance() def get_next_token(self) - Token: 获取下一个token while self.current_char is not None: if self.current_char.isspace(): self.skip_whitespace() continue # 整数和浮点数识别 if self.current_char.isdigit(): return self.handle_number() # 运算符识别 if self.current_char in -*/: token Token(OPERATOR, self.current_char, self.pos) self.advance() return token # 括号识别 if self.current_char in (): token Token(PAREN, self.current_char, self.pos) self.advance() return token raise Exception(fInvalid character {self.current_char} at position {self.pos}) return None # 输入结束2.3 数字识别算法数字识别是词法分析中最复杂的部分需要处理以下情况纯整数123浮点数3.14科学计数法本例暂不实现def handle_number(self) - Token: 处理数字字面量整数或浮点数 start_pos self.pos num_str has_decimal False while self.current_char is not None and (self.current_char.isdigit() or self.current_char .): if self.current_char .: if has_decimal: raise Exception(fMultiple decimal points in number at position {self.pos}) has_decimal True num_str self.current_char self.advance() # 检查数字有效性 if num_str.endswith(.): raise Exception(fTrailing decimal point at position {self.pos}) return Token(FLOAT if has_decimal else INTEGER, num_str, start_pos)3. 高级功能扩展3.1 错误恢复机制健壮的词法分析器应该能够从错误中恢复而不是遇到第一个错误就崩溃。我们添加错误恢复逻辑def get_next_token(self) - Token: try: # 原有识别逻辑... except Exception as e: print(fLexical error: {e}) # 跳过当前字符尝试恢复 self.advance() return self.get_next_token() # 递归调用注意实际项目中可能需要限制递归深度3.2 位置跟踪增强为支持更好的错误报告增强位置跟踪功能dataclass class Position: line: int column: int dataclass class Token: type: str value: str position: Position # 替换原来的整数位置 class Lexer: def __init__(self, text: str): self.line 1 self.column 1 # 其余初始化... def advance(self): if self.current_char \n: self.line 1 self.column 1 else: self.column 1 # 其余advance逻辑...4. 完整实现与测试4.1 完整词法分析器代码from dataclasses import dataclass from typing import Literal, Optional dataclass class Position: line: int column: int dataclass class Token: type: Literal[INTEGER, FLOAT, OPERATOR, PAREN, EOF] value: str position: Position class Lexer: def __init__(self, text: str): self.text text self.pos 0 self.line 1 self.column 1 self.current_char self.text[self.pos] if self.text else None def advance(self): if self.current_char \n: self.line 1 self.column 1 else: self.column 1 self.pos 1 if self.pos len(self.text): self.current_char self.text[self.pos] else: self.current_char None def skip_whitespace(self): while self.current_char is not None and self.current_char.isspace(): self.advance() def handle_number(self) - Token: start_pos Position(self.line, self.column) num_str has_decimal False while self.current_char is not None and (self.current_char.isdigit() or self.current_char .): if self.current_char .: if has_decimal: raise Exception(fMultiple decimal points at {self.line}:{self.column}) has_decimal True num_str self.current_char self.advance() if num_str.endswith(.): raise Exception(fTrailing decimal point at {self.line}:{self.column}) return Token(FLOAT if has_decimal else INTEGER, num_str, start_pos) def get_next_token(self) - Optional[Token]: try: while self.current_char is not None: if self.current_char.isspace(): self.skip_whitespace() continue if self.current_char.isdigit(): return self.handle_number() if self.current_char in -*/: token Token(OPERATOR, self.current_char, Position(self.line, self.column)) self.advance() return token if self.current_char in (): token Token(PAREN, self.current_char, Position(self.line, self.column)) self.advance() return token raise Exception(fUnexpected character {self.current_char} at {self.line}:{self.column}) return Token(EOF, , Position(self.line, self.column)) except Exception as e: print(fError: {e}) self.advance() return self.get_next_token() def tokenize(text: str) - list[Token]: lexer Lexer(text) tokens [] while (token : lexer.get_next_token()) is not None: if token.type ! EOF: tokens.append(token) return tokens4.2 测试案例验证词法分析器处理各种情况的能力# 测试混合表达式 expression 3.14 * (42 6.28) / 0.5 tokens tokenize(expression) for token in tokens: print(f{token.type:8} {token.value:6} at {token.position.line}:{token.position.column}) # 预期输出 # FLOAT 3.14 at 1:1 # OPERATOR * at 1:6 # PAREN ( at 1:8 # INTEGER 42 at 1:9 # OPERATOR at 1:12 # FLOAT 6.28 at 1:14 # PAREN ) at 1:18 # OPERATOR / at 1:20 # FLOAT 0.5 at 1:225. 性能优化与生产级考量5.1 内存效率优化对于大型源代码文件可以优化内存使用使用生成器逐步产生token而非构建完整列表避免不必要的字符串拼接改进的token生成方法def tokenize_generator(text: str): lexer Lexer(text) while (token : lexer.get_next_token()) is not None: if token.type ! EOF: yield token5.2 运算符扩展实际编译器需要支持更多运算符类型OPERATORS { : PLUS, -: MINUS, *: MUL, /: DIV, ^: POW, %: MOD, : ASSIGN, # 可以继续添加更多运算符 } # 在get_next_token方法中修改运算符识别 if self.current_char in OPERATORS: op self.current_char # 处理多字符运算符如, 等 self.advance() if op (self.current_char or ) in {, , -, *, /}: op self.current_char self.advance() return Token(OPERATOR, op, Position(self.line, self.column))5.3 与语法分析器的集成词法分析器通常与语法分析器协同工作可以通过以下方式改进接口class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.get_next_token() def eat(self, token_type): if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: raise Exception(fExpected {token_type}, got {self.current_token.type}) def parse(self): # 解析逻辑... pass通过这个实践项目我们不仅实现了四则运算的词法分析器还展示了如何将编译原理中的DFA理论转化为实际代码。这种实现方式虽然比使用正则表达式更繁琐但提供了更好的可扩展性和更深入的学习体验。
