★ FEATURED ARTICLE 简介面向计算机专业学生与编译原理初学者这份北京邮电大学课程实验一的词法分析器实现材料围绕编译器前端扫描器展开聚焦从字符流中识别标识符、关键字、常量与运算符等词素帮助读者理解词法规则定义、分词逻辑、符号栈管理与错误恢复等关键环节。压缩包共4个文件约10KB以2个txt文本和1个h头文件、1个cpp源文件为主文本可承载实验说明与测试输入头文件与源文件则对应规则声明、输入读取及扫描实现的主体代码。已有1000人学习下载适合配合课程进度做代码阅读与实验复盘。读者可据此梳理词法分析器的基本结构观察规则如何映射到词素类型并借鉴测试用例与报错处理方式为后续语法分析与语义分析学习打基础。1. 词法分析器为什么它的难点从来不是“认出 token”多数人第一次做编译原理课程实验一会觉得词法分析器是整个编译器里最容易的部分——不过就是一堆if-else认几个单词。真写下去才会发现麻烦的地方根本不在这里难点是把“最长匹配、回退、错误恢复、行列号追踪、缓冲区边界”这几件互相牵连的事情同时塞进一个确定性状态机里并且保证它对任意字节流不崩、不死循环、不吞字符。它是整条编译链上唯一直接面对“任意输入”的环节后面语法分析、语义分析全都默认它吐出的 token 流是干净的。这个契约一旦破了后面所有阶段的报错都会指向错误的位置排查成本成倍上升。搞懂它的底层机制比把实验跑通更值钱。2. 词法分析器的契约Token 到底该带哪些字段2.1 输入是字节流输出是带位置的 token 序列先把边界划清楚词法分析器接收的是一段字节输出的是一条 token 序列没有别的。它不建语法树不做类型检查也尽量不修改全局状态。这个“只做一件事”的定位决定了它的接口长什么样——一个next_token()函数每次调用消费若干个字符返回一个 token直到返回EOF为止。语法分析器拿着这个迭代器往前推需要回看几个 token 就自己在外面做缓冲。这里有个容易被忽略的设计点token 里必须带位置。位置信息的价值不在于好看而在于它是唯一的错误定位来源。语法分析器发现“这里应该有个分号”时它能拿到的只有 token 上的行列号如果词法层没记后面就得靠数换行符来反推那是血泪经验级别的错误做法。所以line和column是 token 的一等公民不是可选项。常见的实现思路是把位置记录拆成两件事扫描器内部维护line、line_start两个游标token 的列号用start - line_start 1现算。这样每次消费字符只需要在遇到\n时更新一次不必逐字符递增列号省掉大量自增操作。2.2 为什么 lexeme 和 value 必须分开新手最容易把 token 设计成一个char*加一个类型然后所有 token 的“值”都去解析这个字符串。这在标识符上没问题但在数字和字符字面量上会重复解析语法分析阶段要算一次atoi语义分析阶段可能还要再算一次。合理的结构是“原文切片 解析后的值”双轨制。原文切片用start指针加length表示指向源缓冲区不做拷贝解析后的值放在 union 里只有需要的时候才填。typedef enum { TOK_EOF, TOK_IDENT, TOK_KEYWORD, TOK_INT, TOK_FLOAT, TOK_STRING, TOK_CHAR, TOK_OP, TOK_PUNCT, TOK_ERROR } TokenKind; typedef struct { TokenKind kind; const char *start; /* 指向源缓冲区零拷贝 */ int length; /* lexeme 字节数不含结尾 */ int line; /* 起始行号1-based */ int column; /* 起始列号1-based */ union { long long ival; /* TOK_INT 有效 */ double fval; /* TOK_FLOAT 有效 */ int op; /* TOK_OP运算符表下标 */ } value; } Token;start是指针而不是数组前提是源文件被整块读进内存并在整个编译期间保持存活。这个前提必须写进注释否则某天有人改成流式读取所有 token 的 lexeme 会瞬间全部悬空。op存的是运算符表下标而不是字符串因为运算符的识别在词法层已经完成了后面语法分析只需要比较整数比字符串比较快一个数量级。注意length不要用strlen(start)代替。字符串字面量里可能含有\0转义strlen会截断。2.3 驱动循环一次读一个字符真的够吗最朴素的扫描器是每次getchar()一个字符。逻辑正确但在真实文件上性能很差——函数调用和缓冲区检查的开销远超实际的状态转移。工业实现几乎都用双缓冲两块固定大小的缓冲区轮流填充扫描指针在一块内滑动滑到边界时把剩余部分搬到另一块开头再读入新数据。再进一步是哨兵技巧每块缓冲区末尾放一个EOF字符真正的EOF或\0这样内层循环就不需要每次检查“是否到缓冲区末尾”只在读到哨兵时才走慢路径。这个技巧的收益在内层while里非常明显因为省掉的分支判断恰好是最热的那条路径。真正把这几件事串起来的是主循环Token next_token(Scanner *s) { for (;;) { skip_whitespace(s); /* 空白不产生 token */ if (peek(s) / peek2(s) /) { skip_line_comment(s); continue; } if (peek(s) / peek2(s) *) { skip_block_comment(s); continue; } break; } if (peek(s) \0) return make_eof(s); return scan_token(s); /* 分发到标识符/数字/运算符等分支 */ }外层for(;;)的作用是“跳过不产生 token 的东西后重新判断”注释和空白都走这条路。这里的continue不能写成递归调用否则一个几千行的注释文件就能把栈打穿。skip_*系列函数必须是消费型的保证每次循环至少前进一个字符这是后面防死循环的第一道保险。3. 从正则到 DFAThompson 构造和子集构造到底在做什么3.1 每种 token 都是一条正则正则先变成 NFA 片段词法规则的本质是一组正则表达式标识符是[A-Za-z_][A-Za-z0-9_]*十进制整数是[0-9]浮点是[0-9]\.[0-9]。把这些正则直接翻译成代码当然可以但那样每种 token 一套手写逻辑规则一多就难以维护且很难证明“没有遗漏”。正规的做法是走一遍经典管线正则 → NFA → DFA → 最小化 DFA → 转移表。中间每一步都有明确的算法可以机械执行出错概率低。Thompson 构造的核心思想是“片段可拼接”每个正则片段是一个带唯一入口start和唯一出口accept的子图出口通过 ε 边连接到后续片段。字符、连接、选择、闭包四种构造各有固定模板class NFA: def __init__(self): self.trans [] # trans[state][sym] [dst...]symNone 表示 ε self.start None self.accept None def new_state(self): self.trans.append({}) return len(self.trans) - 1 def add(self, src, sym, dst): self.trans[src].setdefault(sym, []).append(dst) def char(self, c): # 单字符片段 s, a self.new_state(), self.new_state() self.add(s, c, a) return s, a def concat(self, f1, f2): # 连接f1 的出口 ε 到 f2 的入口 s1, a1 f1; s2, a2 f2 self.add(a1, None, s2) return s1, a2 def alt(self, f1, f2): # 选择新入口分叉出口合并 s1, a1 f1; s2, a2 f2 s, a self.new_state(), self.new_state() self.add(s, None, s1); self.add(s, None, s2) self.add(a1, None, a); self.add(a2, None, a) return s, a def star(self, f): # 闭包出口回到入口同时允许跳过 s1, a1 f s, a self.new_state(), self.new_state() self.add(s, None, s1); self.add(s, None, a) self.add(a1, None, s1); self.add(a1, None, a) return s, atrans用字典而不是二维数组是因为 NFA 的转移天然稀疏一个状态最多两三条出边。symNone承担 ε 边的角色这个约定后面eps_closure会反复用到。star那四行是整套构造里最容易写错的地方——出口既要有回边继续匹配又要有跳边零次匹配少一条就会漏掉空串或漏掉重复。3.2 ε-closure 与子集构造把“猜”变成“确定”NFA 的问题是它需要“猜”。站在某个状态上读入一个字符后可能同时存在多条可行路径机器没法决定走哪条。子集构造解决的就是这个问题把一个 NFA 状态集合当成 DFA 的单个状态凡是集合内所有状态能到达的下一批状态合并成新的 DFA 状态。这样“猜”变成了“同时走所有路”结果确定。前置操作是 ε-closure从一个状态集合出发沿 ε 边能免费到达的所有状态。它必须用显式栈做迭代不能递归——ε 环在star构造里是常态递归会直接栈溢出。def eps_closure(nfa, states): stack, out list(states), set(states) while stack: s stack.pop() for t in nfa.trans[s].get(None, ()): # None 即 ε 边 if t not in out: out.add(t) stack.append(t) return frozenset(out) def subset_construction(nfa, alphabet): d0 eps_closure(nfa, {nfa.start}) ids, order, rows {d0: 0}, [d0], [] queue [d0] while queue: cur queue.pop(0) row {} for sym in alphabet: nxt set() for s in cur: nxt.update(nfa.trans[s].get(sym, ())) # 只沿非 ε 边移动 if not nxt: continue # 空集即死状态整列省略 cl eps_closure(nfa, nxt) if cl not in ids: ids[cl] len(order) order.append(cl) queue.append(cl) row[sym] ids[cl] rows.append((ids[cur], row)) return order, rowsids把状态集合映射成整数编号靠的是frozenset可哈希。nxt为空时省略整列这样得到的 DFA 是“部分转移函数”死状态不占表项——工程上比补全死状态省很多空间。queue.pop(0)在 Python 里是 O(n)写成collections.deque的popleft()更好这里为了可读性保留。子集构造有个常被忽略的副产品它天然支持“多个 token 的接受状态合并”。把所有 token 的正则用alt拼成一个大 NFA一个 DFA 就能同时识别全部 token接受状态上标注“这个状态接受哪个/哪些 token”。如果有多个 token 同时接受比如和的中间状态就在状态上挂一个集合运行时按最长匹配规则裁决。3.3 状态表怎么落地成代码二维数组、等价类与行压缩DFA 到手后落地方式直接决定运行速度和表的大小。最直白的是二维数组dfa_trans[state][char]行数是状态数列数是 256按字节。几千个状态乘 256 就是几十万项每项一个int表能到几 MB对课程实验无所谓对真实编译器就太肥了。常见的压缩手段有两级。第一级是字符等价类把所有字节按“在任何状态下的转移目标是否一致”划分成若干类常见结果是十几类而不是 256 类。构建方式是先按“出现在哪些转移里”给字符打签名签名相同的合并。这一步能把表宽直接砍掉一个数量级。第二级是行合并或默认转移如果两行的转移完全一致指向同一个状态就合并成一行或者给每个状态指定一个默认目标表里只存例外项。/* 压缩后的转移表char_class 把 256 字节映射到十几个等价类 */ static const unsigned char char_class[256] { /* ... */ }; static const short dfa_trans[DFA_STATE_COUNT][CLASS_COUNT] { /* 状态 0起始状态 */ { 1, 2, 3, 4, 0, /* ... */ }, /* ... */ };short在状态数少于 32767 时够用比int省一半。char_class的初值必须覆盖全部 256 项否则遇到非 ASCII 字节会读到 0被当成某个合法类产生莫名其妙的 token——这是真实踩过的坑。表做完之后最好写一个自检随机生成一批字符串同时跑“表驱动”和“朴素正则匹配”比对结果一致才认为表是对的。4. 最长匹配为什么扫描器必须留一颗“后悔药”4.1 maximal munch为什么要回退到最后一个接受状态DFA 驱动扫描的循环里最关键的不是状态转移而是“记住最后一次接受”。原因是 token 之间是前缀关系和共享前缀1和1.5共享前缀.和...共享前缀。扫描器读到时无法判断这是完整 token 还是更长 token 的开头只能继续往前读读到时才知道应该是但如果读到的是a那就得退回去只认。这个“退回去”就是常说的后悔药形式化名字叫 maximal munch在所有可能的匹配中取最长的那一个。实现上只需要两个变量——最后一个接受状态、以及到达该状态时的输入位置。Token scan_by_dfa(Scanner *s) { int state DFA_START; TokenKind last_accept TOK_NONE; const char *last_pos NULL; const char *p s-cursor; for (;;) { int cls char_class[(unsigned char)*p]; int next dfa_trans[state][cls]; if (next 0) break; /* 无转移停止 */ state next; p; TokenKind k dfa_accept[state]; if (k ! TOK_NONE) { /* 记录可接受位置 */ last_accept k; last_pos p; } } if (last_accept TOK_NONE) { /* 一个字符都认不出 */ s-cursor; /* 必须前进防死循环 */ return make_error_token(s, p); } s-cursor last_pos; /* 回退把多吃的字符还回去 */ return make_token(s, last_accept, last_pos); }last_pos和s-cursor的分离是整个函数的核心。p是探路指针它可以一路吃到后面去s-cursor才是权威位置。函数返回前把s-cursor拉回last_pos等于宣布“刚才多读的字符不算数下次重新扫”。这一行如果漏了会变成加上一个被吞掉的语法分析器报的错会离真正的原因十万八千里。char_class那张表在这里再出现一次说明字符分类是扫描器的公共基础设施不该散落在各个分支里。dfa_accept[state]存接受类型TOK_NONE表示非接受状态这个哨兵值选-1或枚举首项都行但必须和有效 token 类型不重叠。4.2 关键字不是词法规则是标识符表的一次查表一个很自然的想法是把if、while、return也写成正则拼进大 DFA。技术上完全可行工程上通常不这么做。原因在于关键字的数量会变。语言加一个新关键字就要改正则、重建 NFA、重跑子集构造和最小化整张表重新生成。而且关键字和标识符在 DFA 里高度重叠if的状态会和i、in、int的前缀状态纠缠最小化之后状态数反而上升。更常见的做法是DFA 只认“标识符”这一条规则扫出一个完整 lexeme 之后拿整串去哈希表里查一次。命中就改 kind 为TOK_KEYWORD没命中保持TOK_IDENT。Token classify_ident(Scanner *s) { Token t make_token(s, TOK_IDENT, s-cursor); const KeywordEntry *e keyword_lookup(t.start, t.length); /* 带长度的哈希 */ if (e) { t.kind TOK_KEYWORD; t.value.op e-op; } return t; }keyword_lookup必须接受长度参数不能只接受char*然后内部strcmp。因为t.start指向的是源缓冲区内部后面还有别的字符用strcmp会把if后面的内容一起比进去。这个小细节在实验里翻车率极高。注意查表要在“最大匹配”之后做。先查表再匹配ifdef会被拆成if和def两个 token。4.3 注释、除号与未闭合注释三个容易翻车的边界/是词法分析里最不干净的一个字符。它同时是除号、行注释开头、块注释开头。手写扫描器通常用一个两字符前瞻解决看到/就看下一个是/走行注释是*走块注释否则就是除号。这意味着扫描器的某个分支需要 2 个字符的前瞻而不是 DFA 那样的单字符转移——没关系实现上把前瞻做成peek(1)、peek(2)就够了不必强行塞进状态机。真正麻烦的是块注释的收尾。/* ... */里可以出现任意字符包括换行、字符串、/、*。扫描逻辑必须是“读到*再看下一个是不是/”而不是“读到/就结束”否则/* a/b */会在a/处提前终止。同时块注释里的每一个\n都要累加到行号上否则注释之后的全部报错行号整体偏小。未闭合注释是必须显式处理的错误。文件读到EOF还没见到*/正确做法是报一个“块注释未闭合开始于第 N 行”然后把游标推到文件末尾让本次编译干净结束。错误的做法是让扫描循环继续找*/它会一路吃到内存末尾程序崩溃或者产生一条长得离谱的 token 流。最后是嵌套注释。多数语言不支持嵌套扫描器遇到第一个*/就收工简单可靠。如果语言规范要求支持嵌套就必须维护一个深度计数器遇到/*加一、*/减一减到零才结束。这个选择要在文档里写死不能靠“碰巧能跑”。5. 避坑与排查词法分析器最常翻车的五个地方5.1 五条踩坑记录现象、原因、解决第一条死循环。现象是最外层驱动循环永远不返回或者 token 流长度无限增长程序卡死在某个位置再也不动。原因几乎总是同一条错误分支里直接return error_token()忘了推进s-cursor。调用方拿到一个错误 token位置没变下一次调用又走到同一个字符又返回错误 token。解决方法是把“至少前进一个字符”写成不变量所有返回路径都满足Debug 版本加一句assert(s-cursor old_cursor)越界立刻暴露。第二条行号整体偏移。现象是前几个错误行号对得上越往后偏差越大最后能差出几十行。原因是某处消费了\n却没有更新line最常见的是skip_block_comment里用memchr找\n却没统计个数或者用strstr找*/之后忘了扫一遍中间的换行。解决办法是把所有消费字符的动作收敛到一个advance()函数里换行计数只在那一个地方做任何地方都绕不过去。第三条缓冲区边界越界。现象是最后一个 token 后面跟着几个垃圾字符或者在某些文件上偶发崩溃、换个文件就好。原因是peek2()在文件末尾读到了缓冲区之外的内存拿到的值是随机的结果时对时错。解决办法是缓冲区尾部预留至少两个哨兵字节并且保证peek(n)在越界时返回哨兵而不是原始内存。这个坑的隐蔽性在于它和输入内容相关本地跑十个用例都正常交上去评测挂了。第四条关键字被前缀切割。现象是ifdef、integer、whileLoop这类词被识别成关键字加标识符两段。原因是先查关键字表再匹配标识符或者用了strncmp比较前几个字符就返回。解决办法是严格按最大匹配先扫出完整的标识符 lexeme再拿“指针 长度”整串查表长度不等一律不命中。第五条数字字面量的边界。现象是1..10这种数组范围写法被识别成浮点数1.后跟.10或者0x后面没有十六进制数字时被识别成0加标识符x。原因是在数字状态里看到.就无条件进入小数部分没有检查后面是不是数字。解决办法是在[0-9]之后看到.时必须前瞻一个字符确认是数字才进入浮点分支0x分支同理看到0和x之后必须至少消费一个十六进制数字否则整体退化成0加错误。5.2 一套从 token 流倒推问题的排查顺序排查这类问题的顺序比技巧重要。第一步永远是打印 token 四元组——(kind, lexeme, line, column)一行一个把整段输入的 token 流完整看一遍。绝大多数问题在这一步就能定位到“从第几个 token 开始不对”然后只需要看那个 token 往前一小段源码。第二步是做最小化输入。把整段源码二分留下前半段看问题是否复现反复二分直到只剩几行。词法问题几乎都是局部问题缩到十行以内基本就现形了。第三步是对比状态轨迹。给扫描器加一个可选开关把(state, char, next_state)打出来和手工推演的 DFA 走位比对。分叉点就是 bug 所在——通常是某条转移在表里填错了或者字符等价类把两个不该合并的字符合并了。第四步是检查 lookahead 的所有权。谁读了peek2的那两个字符谁负责把它们还回去或者算进 lexeme 长度。跨函数的 lookahead 最容易出现“这个字符到底算谁的”争议一次漏算就是一个 token 的偏移后面全乱。6. 设计取舍表驱动、手写扫描与生成器之间怎么选走完上面这些机制最后一个绕不开的问题是到底该用哪种实现方式。三种方案各有明确的适用边界没有普适答案。方案构建成本规则变更成本运行速度错误信息质量手写扫描函数低低改一个分支即可高最好能带上下文表驱动 DFA中需要构造管线中改规则要重建表最高常量次转移一般只有状态号生成器规则文件驱动高要写规则和骨架最低改规则文件高取决于骨架代码手写扫描的优点是错误信息能做得非常具体比如“字符串字面量在第 12 行第 8 列缺少结束引号”这种信息表驱动很难给因为 DFA 只知道“进了死状态”不知道自己在哪个语义分支里。缺点是规则一多就难维护几十种 token 的分支散在几百行代码里加一条规则要动三处。表驱动最大的价值在于可证明性。规则和代码彻底分离正则改了就重新生成表不会出现“代码和文档不一致”。代价是调试体验差出问题时看到的是状态编号得回头查表才知道对应哪条规则。我一般的判断是课程实验用表驱动因为实验的核心目的就是走通“正则 → NFA → DFA”这条链手写 switch 反而绕过了要考的东西真实项目里如果 token 类型超过三十种用生成器少于十种手写更快更可控。这里还有一个常被低估的取舍到底要不要在词法层处理字符串转义。把a\nb在词法层解成真正的换行符语法分析拿到的就是干净的字符串但报错时无法复现原文只在词法层保证引号闭合、把原始 lexeme 原样传给后面错误处理更简单但后续阶段要自己再解一遍。我倾向后者因为词法层的职责是切分不是解释。从那以后我每次写扫描器都会先强制走一遍“四元组打印 最小输入二分”这两步再开始怀疑状态转移表。这个习惯救过我很多次——绝大多数看起来玄学的 token 错位最后都落在某个advance()忘了记换行、或者某个peek2越界上。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
