简介这是一份面向编译原理学习者与课程实践者的词法分析阶段完整实现资源围绕C语言文法到MIPS汇编的编译流程展开适合正在做编译器课程设计或希望理解前端词法扫描机制的学生与开发者。压缩包共19个文件以10个h头文件与7个cpp源文件为主另含2个txt测试用例整体约30KB体量轻便但结构完整。代码覆盖词法分析、语法解析、中间代码生成、MIPS目标代码生成、寄存器分配与错误处理等关键模块头文件承担类定义与接口声明源文件对应各阶段具体实现测试文本可用于验证词法切分与编译结果。已有121人学习读者可借此梳理从源代码字符串到标记序列、再到汇编输出的完整链路理解符号表、递归下降等核心概念在实际工程中的落地方式并对照模块划分掌握编译器各组件之间的协作关系与排错思路。1. 词法分析在编译器里到底卡在哪一步从一段报错说起很多人第一次写编译器卡住的地方不是语法树也不是代码生成而是词法分析。你写了一个int a 10;结果程序报unexpected character 或者把拆成了和后面语法分析直接崩掉。这类问题几乎都出在词法分析这一层。词法分析是编译器的第一个阶段负责把源代码字符流切成有意义的记号Token比如关键字、标识符、数字、运算符。它看起来简单但实际写起来边界条件非常多注释怎么跳过、字符串里的转义怎么处理、数字字面量支持几种进制、运算符最长匹配怎么保证。如果你正在学编译器开发或者想自己写一个能跑的小型编译器词法分析是你绕不过去的第一道坎。这篇文章会从零讲清楚词法分析的实现路径包括状态机设计、正则到 DFA 的转换、手写扫描器的参数设置以及那些只有真正跑过才知道的坑。适合已经会一门编程语言、想动手写编译器前端的读者。2. 从正则到 DFA词法分析器的理论底座怎么落地2.1 为什么不能直接用正则表达式逐条匹配很多新手第一反应是词法规则不就是一堆正则吗我写十几个正则逐个去匹配源代码不就行了。这个思路在玩具阶段能跑但一旦规则变多性能会断崖式下跌。假设你有 50 条正则规则每条都要从当前位置尝试匹配最坏情况下每个字符都要试 50 次。更麻烦的是正则引擎通常带回溯遇到a b c这种简单语句还好遇到长标识符或者嵌套注释回溯次数会爆炸。正规的做法是把所有词法规则合并成一个确定有限自动机DFA。DFA 的特点是对每个输入字符只有一个确定的下一个状态不需要回溯时间复杂度是 O(n)n 是源代码字符数。也就是说无论你有多少条词法规则扫描一遍就能切完所有 Token。这个性质对编译器来说非常重要因为词法分析是每编译一次就要跑一遍的性能直接影响开发体验。从正则到 DFA 的路径是正则表达式 → NFA非确定有限自动机→ DFA → 最小化 DFA。实际工程中你不需要每次都手推这个流程可以用工具生成也可以手写一个状态机。但理解这个转换过程能帮你在手写扫描器时知道哪些地方容易出错。2.2 用 Thompson 构造法把正则转成 NFAThompson 构造法是一种把正则表达式递归地转成 NFA 的算法。核心思想是每种正则操作连接、选择、闭包都有对应的 NFA 片段然后把这些片段拼起来。下面是一个简化版的 Python 实现只支持连接、选择和星号闭包足够覆盖大多数词法规则。class NFA: def __init__(self, states, start, accept, transitions): self.states states # 状态集合 self.start start # 起始状态 self.accept accept # 接受状态 self.transitions transitions # 转移表{状态: {字符: [下一状态]}} def char_nfa(c): 单个字符的 NFA return NFA({0, 1}, 0, 1, {0: {c: [1]}}) def concat_nfa(n1, n2): 连接n1 的接受状态通过 ε 连接到 n2 的起始状态 trans dict(n1.transitions) for s, m in n2.transitions.items(): trans[s len(n1.states)] {k: [v len(n1.states) for v in vs] for k, vs in m.items()} trans[n1.accept] {ε: [n2.start len(n1.states)]} return NFA( set(range(len(n1.states) len(n2.states))), n1.start, n2.accept len(n1.states), trans ) def union_nfa(n1, n2): 选择新建起始状态通过 ε 分别指向两个 NFA offset len(n1.states) len(n2.states) trans {} for s, m in n1.transitions.items(): trans[s 1] {k: [v 1 for v in vs] for k, vs in m.items()} for s, m in n2.transitions.items(): trans[s 1 len(n1.states)] {k: [v 1 len(n1.states) for v in vs] for k, vs in m.items()} trans[0] {ε: [n1.start 1, n2.start 1 len(n1.states)]} return NFA(set(range(offset 1)), 0, n1.accept 1, trans) def star_nfa(n): 闭包新建起始和接受状态加 ε 转移 offset len(n.states) trans {} for s, m in n.transitions.items(): trans[s 1] {k: [v 1 for v in vs] for k, vs in m.items()} trans[0] {ε: [n.start 1, offset 1]} trans[n.accept 1] {ε: [n.start 1, offset 1]} return NFA(set(range(offset 2)), 0, offset 1, trans)这段代码里char_nfa生成单个字符的 NFAconcat_nfa把两个 NFA 串起来union_nfa处理选择star_nfa处理闭包。参数说明states是状态编号集合start是起始状态编号accept是接受状态编号transitions是字典键是状态值是该状态下遇到某字符可以跳转的状态列表。注意这里用了ε表示空转移实际构造 DFA 时需要做 ε-闭包计算。这个实现没有做状态编号优化实际工程中你会用更紧凑的表示比如用整数数组代替字典。但理解这个结构后你就能明白为什么词法分析器可以做到线性扫描因为 NFA 转成 DFA 后每个状态对每个输入字符最多只有一个后继。2.3 子集构造法把 NFA 转成 DFA 的关键步骤NFA 转 DFA 的标准方法是子集构造法。核心思路是DFA 的每个状态对应 NFA 的一个状态集合。从 NFA 的起始状态的 ε-闭包开始对每个输入字符计算能到达的 NFA 状态集合如果这个集合没出现过就作为新的 DFA 状态。重复这个过程直到没有新状态产生。下面是一个可运行的子集构造实现def epsilon_closure(nfa, states): 计算状态集合的 ε-闭包 stack list(states) closure set(states) while stack: s stack.pop() for next_s in nfa.transitions.get(s, {}).get(ε, []): if next_s not in closure: closure.add(next_s) stack.append(next_s) return closure def move(nfa, states, ch): 从状态集合出发经过字符 ch 能到达的状态集合 result set() for s in states: for next_s in nfa.transitions.get(s, {}).get(ch, []): result.add(next_s) return result def nfa_to_dfa(nfa): 子集构造法 start_closure epsilon_closure(nfa, {nfa.start}) dfa_states [start_closure] dfa_trans {} queue [start_closure] while queue: current queue.pop(0) for ch in set(c for s in current for c in nfa.transitions.get(s, {}) if c ! ε): next_states epsilon_closure(nfa, move(nfa, current, ch)) if not next_states: continue if next_states not in dfa_states: dfa_states.append(next_states) queue.append(next_states) dfa_trans[(tuple(sorted(current)), ch)] tuple(sorted(next_states)) return dfa_states, dfa_trans参数说明nfa是上一步构造的 NFA 对象states是当前 NFA 状态集合。epsilon_closure用栈做深度优先遍历避免递归深度过大。move计算经过单个字符后的状态集合。nfa_to_dfa返回 DFA 的状态列表和转移表转移表的键是当前状态集合字符值是下一状态集合。这个算法的时间复杂度是 O(2^n)n 是 NFA 状态数。实际词法规则的 NFA 状态数通常在几十到几百所以子集构造完全可行。但如果你有几百条规则生成的 DFA 状态可能上千这时候需要考虑状态最小化或者直接用工具生成。2.4 手写扫描器时状态机怎么设计才不容易翻车虽然理论上可以用工具生成 DFA但实际工程中很多编译器前端选择手写扫描器。手写的好处是错误信息更友好、可以处理上下文相关的情况比如 C 语言里的 typedef 名字、性能可控。手写扫描器的核心是一个大的 switch-case 或者状态函数集合。我一般会按 Token 类型分几个扫描函数scan_identifier、scan_number、scan_string、scan_operator。主循环里先跳过空白和注释然后根据当前字符分派到对应的扫描函数。每个扫描函数内部用 while 循环吃字符直到遇到不属于当前 Token 的字符为止。关键参数设置标识符的起始字符集和后续字符集要分开定义数字扫描要处理小数点、指数符号、进制前缀运算符扫描要用最长匹配原则。最长匹配的意思是遇到时不能只吃就返回要继续看下一个字符是不是。这个逻辑在手写扫描器里通常用「先吃一个字符再看下一个」的方式实现。3. 手写一个能跑的词法分析器从字符流到 Token 序列3.1 定义 Token 类型和数据结构在动手写扫描器之前先定义 Token 的结构。一个 Token 至少包含类型枚举、原始文本lexeme、行号、列号。行号和列号在报错时非常有用没有它们用户看到unexpected token根本不知道去哪找。from enum import Enum, auto from dataclasses import dataclass class TokenType(Enum): # 关键字 INT auto() IF auto() ELSE auto() WHILE auto() RETURN auto() # 标识符和字面量 IDENTIFIER auto() NUMBER auto() STRING auto() # 运算符 PLUS auto() MINUS auto() STAR auto() SLASH auto() ASSIGN auto() EQ auto() NEQ auto() LT auto() GT auto() LE auto() GE auto() # 分隔符 LPAREN auto() RPAREN auto() LBRACE auto() RBRACE auto() SEMICOLON auto() COMMA auto() # 结束 EOF auto() dataclass class Token: type: TokenType lexeme: str line: int column: int def __repr__(self): return fToken({self.type.name}, {self.lexeme!r}, {self.line}:{self.column})参数说明TokenType用auto()自动分配枚举值避免手动编号出错。Token用dataclass自动生成__init__和__repr__方便调试。lexeme保存原始文本后面语法分析报错时可以直接引用。line和column从 1 开始计数符合大多数编辑器的习惯。这个结构看起来简单但实际写的时候容易漏掉EOF类型。没有EOF语法分析器就不知道什么时候该停容易写出死循环。另外column的计算要注意 Tab 字符的处理有些编译器把 Tab 算作一个字符有些算作多个我一般按一个字符算简单且够用。3.2 主扫描循环跳过空白、注释和换行主循环负责维护当前位置、行号、列号然后分派到具体的扫描函数。下面是一个完整的实现class Lexer: def __init__(self, source: str): self.source source self.pos 0 self.line 1 self.column 1 self.keywords { int: TokenType.INT, if: TokenType.IF, else: TokenType.ELSE, while: TokenType.WHILE, return: TokenType.RETURN, } def peek(self, offset0): idx self.pos offset if idx len(self.source): return \0 return self.source[idx] def advance(self): ch self.source[self.pos] self.pos 1 if ch \n: self.line 1 self.column 1 else: self.column 1 return ch def skip_whitespace_and_comments(self): while self.pos len(self.source): ch self.peek() if ch in \t\r\n: self.advance() elif ch / and self.peek(1) /: # 单行注释 while self.peek() ! \n and self.peek() ! \0: self.advance() elif ch / and self.peek(1) *: # 块注释 self.advance() self.advance() while not (self.peek() * and self.peek(1) /): if self.peek() \0: raise SyntaxError(fUnterminated block comment at line {self.line}) self.advance() self.advance() self.advance() else: break def next_token(self) - Token: self.skip_whitespace_and_comments() if self.pos len(self.source): return Token(TokenType.EOF, , self.line, self.column) ch self.peek() if ch.isalpha() or ch _: return self.scan_identifier() if ch.isdigit(): return self.scan_number() if ch : return self.scan_string() return self.scan_operator()参数说明peek(offset)返回当前位置往后偏移offset的字符越界返回\0避免索引错误。advance()前进一个字符并更新行列号遇到换行时行号加一、列号重置。skip_whitespace_and_comments处理空白、单行注释和块注释块注释未闭合时抛异常。next_token是主入口先跳过空白和注释然后根据首字符分派。这里有个细节peek返回\0作为哨兵但源代码里如果真的有\0字符会误判。实际工程中可以用None或者单独判断pos len(source)。我为了代码简洁用了\0你在生产环境里最好改掉。3.3 标识符和关键字的扫描查表法比 if-else 更稳标识符扫描的逻辑是吃字母、数字、下划线直到遇到其他字符。然后查关键字表如果在表里就返回对应的关键字类型否则返回IDENTIFIER。def scan_identifier(self) - Token: start_line, start_col self.line, self.column start_pos self.pos while self.peek().isalnum() or self.peek() _: self.advance() lexeme self.source[start_pos:self.pos] token_type self.keywords.get(lexeme, TokenType.IDENTIFIER) return Token(token_type, lexeme, start_line, start_col)参数说明start_line和start_col记录 Token 起始位置start_pos记录在源代码中的起始索引。isalnum()判断字母或数字加上下划线就是完整的标识符字符集。keywords.get用字典查表比一长串if-else更清晰也更容易扩展。注意这里没有处理 Unicode 标识符。如果你的语言支持中文变量名需要把isalnum()换成更宽泛的判断。但大多数编译器只支持 ASCII 标识符所以这个实现够用。3.4 数字字面量的扫描整数、小数和进制的边界处理数字扫描是最容易出 bug 的地方。整数、小数、科学计数法、十六进制、八进制、二进制每种都有边界情况。下面是一个支持十进制整数和小数的实现def scan_number(self) - Token: start_line, start_col self.line, self.column start_pos self.pos # 整数部分 while self.peek().isdigit(): self.advance() # 小数部分 if self.peek() . and self.peek(1).isdigit(): self.advance() while self.peek().isdigit(): self.advance() # 指数部分 if self.peek() in eE: self.advance() if self.peek() in -: self.advance() if not self.peek().isdigit(): raise SyntaxError(fInvalid number at line {self.line}) while self.peek().isdigit(): self.advance() lexeme self.source[start_pos:self.pos] return Token(TokenType.NUMBER, lexeme, start_line, start_col)参数说明先吃整数部分然后判断小数点。注意self.peek() . and self.peek(1).isdigit()这个条件如果只判断小数点遇到1..2这种写法会误吃。指数部分要处理正负号并且要求后面至少有一位数字否则报错。这里没有处理十六进制0x前缀。如果你需要可以在开头加一个判断如果peek() 0且peek(1) in xX就进入十六进制扫描分支。但要注意0x后面必须至少有一位十六进制数字否则报错。3.5 运算符的最长匹配两个字符的运算符怎么不漏运算符扫描的核心是最长匹配。遇到时要看下一个字符是不是如果是就返回GE否则返回GT。下面是一个支持单字符和双字符运算符的实现def scan_operator(self) - Token: start_line, start_col self.line, self.column ch self.advance() single { : TokenType.PLUS, -: TokenType.MINUS, *: TokenType.STAR, /: TokenType.SLASH, (: TokenType.LPAREN, ): TokenType.RPAREN, {: TokenType.LBRACE, }: TokenType.RBRACE, ;: TokenType.SEMICOLON, ,: TokenType.COMMA, } if ch in single: return Token(single[ch], ch, start_line, start_col) # 双字符运算符 if ch : if self.peek() : self.advance() return Token(TokenType.EQ, , start_line, start_col) return Token(TokenType.ASSIGN, , start_line, start_col) if ch !: if self.peek() : self.advance() return Token(TokenType.NEQ, !, start_line, start_col) raise SyntaxError(fUnexpected character ! at line {self.line}) if ch : if self.peek() : self.advance() return Token(TokenType.LE, , start_line, start_col) return Token(TokenType.LT, , start_line, start_col) if ch : if self.peek() : self.advance() return Token(TokenType.GE, , start_line, start_col) return Token(TokenType.GT, , start_line, start_col) raise SyntaxError(fUnexpected character {ch!r} at line {self.line})参数说明single字典处理单字符运算符直接查表返回。双字符运算符逐个判断先看当前字符再看下一个字符是否匹配。注意!单独出现时直接报错因为大多数语言里!只用于!或逻辑非这里为了简化只支持!。这个实现里/被当作除法运算符但注释已经在skip_whitespace_and_comments里处理了所以不会冲突。如果你要支持/需要在scan_operator里加判断。3.6 把 Token 流跑起来一个最小可用的测试用例把上面的代码拼起来写一个测试用例def tokenize(source: str): lexer Lexer(source) tokens [] while True: tok lexer.next_token() tokens.append(tok) if tok.type TokenType.EOF: break return tokens if __name__ __main__: code int main() { int a 10; float b 3.14; if (a b) { return a b; } return 0; } for tok in tokenize(code): print(tok)运行这段代码你会看到每个 Token 的类型、原始文本和位置。如果遇到报错根据行号和列号去源代码里找对应位置。这个测试用例覆盖了关键字、标识符、数字、运算符和分隔符基本能验证扫描器的正确性。4. 词法分析避坑那些只有跑过才知道的翻车点4.1 现象块注释未闭合导致程序卡死原因块注释扫描时如果源代码里没有*/while 循环会一直读到文件末尾然后peek()返回\0但循环条件没有检查\0导致死循环。解决在块注释循环里加\0检查遇到文件末尾直接抛异常。上面的skip_whitespace_and_comments已经处理了这一点但很多新手会漏掉。4.2 现象数字1.被识别成两个 Token原因小数点判断条件写成了if self.peek() .没有检查小数点后面是否跟着数字。结果1.被切成1和.语法分析器看到.直接报错。解决小数点判断必须同时检查下一个字符是数字即self.peek() . and self.peek(1).isdigit()。如果语言支持1.这种写法需要单独处理但大多数语言要求小数点后必须有数字。4.3 现象运算符被拆成和原因运算符扫描时遇到直接返回GT没有看下一个字符。这是最长匹配原则没落实。解决所有可能组成双字符运算符的字符都要先看下一个字符。上面的scan_operator已经处理了、、、!但如果你要支持、-、*、/也需要加对应判断。4.4 现象字符串里的转义字符导致扫描错位原因字符串扫描时遇到\直接当成字符串结束导致后面的内容被当成代码扫描。比如hello \ world会被切成hello \和world和。解决字符串扫描要处理转义字符。遇到\时跳过下一个字符不管它是什么。下面是一个简单的字符串扫描实现def scan_string(self) - Token: start_line, start_col self.line, self.column start_pos self.pos self.advance() # 跳过开头的引号 while self.peek() ! : if self.peek() \\: self.advance() # 跳过转义符 if self.peek() \0: raise SyntaxError(fUnterminated string at line {self.line}) if self.peek() \0: raise SyntaxError(fUnterminated string at line {self.line}) self.advance() self.advance() # 跳过结尾的引号 lexeme self.source[start_pos:self.pos] return Token(TokenType.STRING, lexeme, start_line, start_col)参数说明self.advance()跳过开头的引号然后循环直到遇到结尾引号。遇到\时跳过转义符和下一个字符。如果遇到\0说明字符串没闭合抛异常。4.5 现象行号和列号在 Tab 字符后错位原因advance()里对 Tab 字符按一个字符处理但编辑器里 Tab 通常显示为 4 个或 8 个空格。报错时列号对不上用户找不到位置。解决要么在advance()里把 Tab 算作多个字符要么在报错信息里只给行号不给列号。我一般选择后者因为列号在 Tab 混用时本来就不准行号足够定位问题。5. 词法分析的进阶技巧用 DFA 表驱动替代手写分支手写扫描器虽然直观但规则一多代码会变得很长而且容易漏掉某些字符组合。进阶做法是把 DFA 的转移表存成二维数组用表驱动的方式扫描。这样扫描逻辑只有十几行所有规则都体现在表里改规则只需要改表。具体做法先定义所有字符的类别比如字母、数字、空白、运算符字符等然后构造一个状态 × 字符类别 → 下一状态的二维表。每个状态有一个标记表示是否接受状态以及接受哪个 Token 类型。扫描时从起始状态出发每读一个字符就查表跳转直到进入死状态或接受状态。下面是一个简化的表驱动扫描器示例# 字符类别映射 def char_class(ch): if ch.isalpha() or ch _: return 0 # 字母 if ch.isdigit(): return 1 # 数字 if ch in \t\r\n: return 2 # 空白 if ch \0: return 3 # 结束 return 4 # 其他 # 转移表状态 × 字符类别 - 下一状态 # 状态 0起始1标识符2数字3接受标识符4接受数字5死状态 TRANS [ [1, 2, 0, 3, 5], # 状态 0 [1, 1, 3, 3, 3], # 状态 1 [5, 2, 4, 4, 4], # 状态 2 [5, 5, 5, 5, 5], # 状态 3接受 [5, 5, 5, 5, 5], # 状态 4接受 [5, 5, 5, 5, 5], # 状态 5死 ] ACCEPT { 3: TokenType.IDENTIFIER, 4: TokenType.NUMBER, }参数说明char_class把字符映射到类别编号TRANS是转移表行是状态列是字符类别。ACCEPT定义哪些状态是接受状态以及对应的 Token 类型。扫描时维护当前状态和起始位置每读一个字符就查表跳转如果下一状态是死状态就回退到最后一个接受状态生成 Token。这个表驱动方法的优点是扫描逻辑和规则分离加新规则只需要改表和ACCEPT。缺点是表是手工维护的容易写错。实际工程中可以用脚本从正则生成这张表避免手写出错。验证表驱动扫描器是否正确可以用一组覆盖所有 Token 类型的测试用例对比手写扫描器和表驱动扫描器的输出。如果两者完全一致说明表是对的。我一般会写一个compare_lexers函数随机生成一些源代码片段跑两个扫描器断言输出相同。这个习惯帮我省了很多调试时间。最后说一个我自己的教训词法分析器写完只是第一步真正难的是错误恢复。用户输入错误时扫描器不能直接崩掉要能跳过非法字符继续扫描尽量多报几个错误。我早期写的扫描器遇到非法字符就抛异常用户改一个错编译一次体验很差。后来改成收集错误、跳过非法字符继续扫描一次能报出所有词法错误效率高很多。希望帮到你。本文还有配套的精品资源点击获取