词法分析器生成器原理与实践

可视化演示

Lexer生成器通过正则表达式描述词法规则，自动生成高效的词法分析器代码。本文以Lex和Flex为例讲解规则定... 切换模式查看不同维度。

生成器概述

想象你的工厂每天收到一串串字符珠，有英文、数字、符号，彼此没有天然分隔。你要的不是整串珠子，而是按花纹分好的一堆堆记号。手写一台分拣机意味着要为每一颗珠子设计判断逻辑，费时且易错。于是你决定把规则交给自动工厂，让工厂替你造分拣机——这正是 Lexer 生成器的定位。

在编译原理中，这台分拣机叫词法分析器，它读入源代码字符流，输出 Token 流。Token 由“类型 + 原文”组成，例如 (IF, "if")、(NUMBER, "42")。Lex 和 Flex 是生成器的代表：开发者用正则表达式描述规则，生成器自动生成 C/C++ 扫描代码。开发者不再手写状态机，而是像填写规则册子一样描述“什么花纹算什么记号”。

回到珠子工厂，你不再关心传送带怎么拐弯，只要把规则册子交给工厂，机器会自动装配好。这就是生成器对工程师最大的价值：把复杂的自动机设计变成声明式描述。

正则表达式基础

规则册子不是自然语言，而是一种极简的花纹语言。它只有五种基本笔画：空笔画、单个珠、连续、二选一、圈起来重复。你写“红色珠 + 蓝色珠”，分拣机就明白要先看到红再看到蓝；你写“红珠或蓝珠”，分拣机就知道两条传送带都允许。

在生成器内部，这套花纹语言就是正则表达式。字符 \(a\) 表示匹配字符本身，· 表示连接，| 表示选择，* 表示零次或多次重复。括号用来改变优先级。Lex/Flex 支持更丰富的简写，比如 [0-9] 表示数字集合，+ 表示一次或多次，但它们的底层仍然可以拆解成这五种基本运算。

有了这五种笔画，工厂就能把任何复杂花纹拆成装配图纸。你写的每一条正则，最终都会变成自动机上的一个一个“机关”。

Lex规则语法

规则册子通常分三栏：第一栏准备材料，第二栏写核心规则，第三栏放收尾代码。Lex 源文件也遵循同样的三段式结构：定义区、规则区、用户代码区。定义区可以放宏、起始状态声明和选项；规则区是 pattern { action } 的列表；用户代码区放需要原样嵌入生成文件的辅助函数。

规则区的每一条都像是分拣机上的一个传感器：pattern 描述应该抓住哪种花纹，action 是抓住之后要做的动作。动作里最常用的是 return TOKEN;，意思是“把这个花纹放进对应盒子”。Flex 还会提供 yytext 变量，里面装着当前匹配到的原文，方便你进一步处理。

册子里的每一行，都是分拣机上的一处机关。你不必亲手焊接每个机械臂，只要把“看到什么花纹、放进哪个盒子”写清楚，工厂就能完成组装。

状态管理策略

当珠子进入“注释垃圾”段时，分拣机要暂时切换到另一档：此时字母、数字都不再是普通珠子，而是要吞掉的废料，直到看见结束符才切回正常档位。这种“档位”思想，对应 Flex 中的起始状态。

Flex 用 %s NAME 声明一个起始状态，用 BEGIN(NAME); 切换状态，用 <NAME> 前缀限定某条规则只在该状态下生效。比如处理 /* ... */ 注释时，进入注释状态后，普通规则不再参与竞争，只有以 <COMMENT> 开头的规则会执行，直到遇见 */ 再 BEGIN(INITIAL); 回到普通状态。

档位切换让同一台分拣机可以干多份工。遇到注释就吞料，遇到字符串就进字符串模式，遇到普通代码就正常分拣，一台机器不再需要拆成三台。

冲突与优先级

一颗珠子串同时符合红花纹和蓝花纹怎么办？分拣机有两条铁规矩：第一，永远先抓最长的一整串；第二，如果两串一样长，就按规则册子页码靠前的盒子来分。这样机器永远不会犹豫。

Flex 的默认行为正是如此：如果多条规则都能从当前位置匹配出一段字符串，它选择最长的那个词素；当最长长度相同时，选择声明顺序最早的那条规则。例如关键字 int 和标识符 [a-z]+ 同时匹配 intx 时，由于标识符能匹配完整的 intx 长度 4，比关键字长，所以最终结果是标识符 intx，而不是先切出 int 再切出 x。

这一规矩避免分拣机犹豫，也保证了行为可预测。无论规则怎么堆叠，只要依照“最长优先、同长先声明”的规则，任何输入都能得到唯一的切分结果。

NFA构造

如果直接把正则规则焊进机器，控制台会不知道下一步该往哪走。所以工厂先画一张带“魔法”的装配草图：一个岔路口可以同时走多条传送带，不需要精确到每一步。这张草图的数学名字叫 NFA，全称是非确定有限自动机。

Lexer 生成器通常使用 Thompson 算法把正则表达式变成 NFA。算法非常机械：每个基本字符生成一个只有两条状态的小片段，然后通过空转移把片段拼起来。所谓空转移，就是不需要读入任何珠子的传送带；它让机器能“凭空”从一个片段跳到另一个片段。正是空转移让 NFA 可以同时保留多种可能路径。

这张魔法图纸不需要立刻执行，却把正则的语义完整保存了下来。所有连接、选择和循环，都在这一步变成节点和空转移，后续的 DFA 构建才有原料可用。

DFA生成优化

魔法图纸无法直接焊进机器，因为机器不能同时走两条路。于是工厂把“当前可能在哪一堆状态”打包成一个“确切状态”，用一张一眼就能查表的图替换魔法图。这个打包过程叫子集构造，得到的新机器叫 DFA，每个状态对每个字符只有唯一一条出路。

子集构造的核心操作是 ε 闭包：从一个 NFA 状态集合出发，沿着空转移把所有能到达的状态都收进来；再读入一个字符，收集所有后续状态，再做一次 ε 闭包，得到一个新的 DFA 状态。反复执行，直到不再产生新状态，DFA 转移表就成型了。之后还可以用最小化算法合并行为等价的状态，压缩表格尺寸。

把魔法图变成查表图之后，分拣机就不用再“平行宇宙式”地同时追赶所有传送带；它只需要查表，走一条确定的路。最小化再帮忙删掉重复工序，让表格尽量精简。

实战应用

工厂交付后，保养手册上写着：输入长长一串珠子，分拣机始终用固定节奏工作，因为它只需查一张转移表。实际工程中，Lex/Flex 生成的词法分析器也具有这样的线性复杂度：每个字符最多被处理一次，每次转移通过查表完成，与规则数量无直接关系。

使用 Flex 的流程很简洁：编写 lexer.l 规则文件，运行 flex lexer.l 生成 lex.yy.c，再用 C 编译器编译并链接 -lfl 库。生成后的扫描器从 yylex() 函数开始，每次调用返回一个 Token。若遇到无法匹配的字符，默认会把它复制到输出流，但你可以在规则区补一条 . 规则并调用 yyerror 来报告错误，实现更严谨的容错。

这正是生成器流水线的价值：换订单只要改规则册子，生产线不用重新发明。无论是写编译器、做代码高亮，还是解析配置和日志，Lexer 生成器都能把“手工维护状态机”的体力活，压缩成描述花纹的声明式工作。

AI 应用场景

Python 演示

import re  class Rule:    def __init__(self, name, pattern):        self.name = name        self.pattern = pattern        self.regex = re.compile(pattern)  class LexerGenerator:    def __init__(self):        self.rules = []     def add(self, name, pattern):        self.rules.append(Rule(name, pattern))     def build(self):        def lexer(text):            tokens = []            pos = 0            while pos < len(text):                best_name = None                best_len = 0                for rule in self.rules:                    m = rule.regex.match(text, pos)                    if m and len(m.group(0)) > best_len:                        best_len = len(m.group(0))                        best_name = rule.name                if best_name is None:                    raise ValueError(f"无法识别位置 {pos}: {text[pos:]!r}")                tokens.append((best_name, text[pos:pos + best_len]))                pos += best_len            return tokens         return lexer  def main():    gen = LexerGenerator()    gen.add("关键字", r"if|else")    gen.add("数字", r"[0-9]+")    gen.add("标识符", r"[a-z]+")    gen.add("空白", r"\s+")    lex = gen.build()    tokens = lex("if x42 else")    print(tokens)  if __name__ == "__main__":    main()

1. class LexerGenerator:相当于珠子工厂的厂房对象，负责积累规则并生成分拣机。
2. def add(self, name, pattern):向规则册子追加一条规则，并预编译成正则对象。
3. rule.regex = re.compile(pattern)提前编译正则，避免每次匹配都重新解析规则。
4. def build(self):根据规则册子返回一个可调用的 lexer 函数，这就是“生成”动作。
5. while pos < len(text):扫描头从字符串起点逐步前进，直到整个输入被分拣完毕。
6. for rule in self.rules:遍历所有规则，模拟 DFA 同时考虑所有可能匹配。
7. if m and len(m.group(0)) > best_len:用“只保留更长者”实现最长匹配；若长度相同，因为遍历顺序未变，先声明的规则自然获胜。
8. if best_name is None:找不到任何规则匹配时抛出错误，相当于分拣机遇到未知花纹。
9. tokens.append((best_name, text[pos:pos + best_len]))把“类别 + 原文”的 Token 对放进结果列表。

常见误区

面试题