编译原理实战3手搓正则引擎与字节码虚拟机参考宫文学《编译原理》课程「算法篇 / 扩展篇」。本文所有代码均在华为云 ECSUbuntu 24.04Python 3.12上真实运行所有输出均为机器实测结果代码见文末仓库路径。正则与虚拟机是编译原理里看得见摸得着的两块硬骨头。正则引擎是词法分析器lexer的核心字节码虚拟机则是几乎所有脚本语言Python、Lua、JVM的运行底座。这一篇我们不抄库、不画饼从零实现一条正则 → AST → NFA → DFA → 最小化 DFA的流水线再实现一个栈式字节码虚拟机 递归下降编译器并把真实的运行数据贴出来。这正是宫文学老师在课程里反复强调的动手主义算法看懂不算会能在机器上跑出正确的状态数和轨迹才算真正吃透。下面每一段都配有可在 ECS 上复现的代码与输出。一、正则引擎从字符串到状态机1.1 整体流水线一条正则表达式要经过四步才能用来匹配字符串regex 字符串 → 解析递归下降 → AST → Thompson 构造 → NFA带 ε 转移 → 子集构造 → DFA无 ε每字符唯一转移 → 划分细化 → 最小化 DFA合并等价状态为什么不直接用 NFA 匹配因为 NFA 有 ε 转移、一个字符可能走到多个状态匹配时需要维护一组活跃状态子集模拟。DFA 没有这些麻烦每个状态读一个字符有唯一去处匹配就是一路查表。最小化 DFA 则把冗余状态压到最少是词法分析器生成器的标准收尾动作。1.2 正则 AST 与递归下降解析我们用一个最小的递归下降解析器把正则拆成 AST 节点Char / AnyChar / CharClass原子、Concat / Alt / Star / Plus / Quest组合。文法大致是alt → concat (| concat)* concat → repeat* repeat → atom (* | | ?)* atom → ( alt ) | [ class ] | . | \ esc | char处理函数parse_repeat里有个容易踩的坑当peek()返回None已到串尾时若直接写while self.peek() in *?会抛出TypeError: argument of type NoneType is not iterable。正确写法是先判空# regex_ast.py 片段whileself.peek()isnotNoneandself.peek()in*?:node{*:Star,:Plus,?:Quest}[self.peek()](node)self.advance()1.3 Thompson 构造法Thompson 构造的核心思想每个 AST 节点都构造成一个 (start, accept) 两状态的片段片段之间用 ε 转移我们用None标记拼接。比如连接Concat就是把前一段的 accept 用 ε 接到后一段的 startStar则新增一对起止状态允许跳过或循环回来。# nfa.py 片段Star 的构造ifisinstance(node,Star):snfa.add_state();anfa.add_state()s1,a1_build(nfa,node.child)nfa.add_edge(s,EPS,s1)# 进入循环nfa.add_edge(s,EPS,a)# 或跳过nfa.add_edge(a1,EPS,s1)# 循环回来nfa.add_edge(a1,EPS,a)# 或退出returns,aNFA 的匹配用子集模拟维护当前所有活跃状态集合每读一个字符就把集合沿非 ε 边推进再补上 ε-闭包。空集合即匹配失败。ε-闭包是整个 NFA 模拟的基石从一组状态出发沿 ε 边能到达的所有状态都算活跃。实现就是一次 DFS/BFS# nfa.py 片段ε-闭包defepsilon_closure(nfa,states):stacklist(states)closureset(states)whilestack:sstack.pop()for(label,t)innfa.edges[s]:iflabelisNoneandtnotinclosure:# 只沿 ε 边closure.add(t)stack.append(t)returnclosure子集模拟每读一个字符做两件事① 对当前活跃集合里每个状态沿能匹配该字符的非 ε 边走到下一拨状态② 对这些下一拨状态再求一次 ε-闭包得到新的活跃集合。如果某一步活跃集合变空说明没有路径能继续直接判失败。1.4 子集构造与最小化子集构造把NFA 状态的集合当作一个 DFA 状态frozenset作字典键去重。难点在于字母表必须有限——我们把正则中出现过的具体字符含字符类的展开、通配符.的展开收集成字母表字母表外的字符一律视为不匹配。最小化用经典的划分细化法Moore 算法先按接受态 / 非接受态粗分再对每个分组依据读每个字符后落到哪个分组做签名签名不同的拆开直到分组不再变化。等价状态被合并。直觉上两个状态等价当且仅当它们都是接受态或都不是且对任意输入字符它们转移到的下一状态也等价。这个定义是自指的所以用迭代细化的方式逼近每轮都试图把行为不同的状态拆开直到再也无法拆开收敛到的就是最小等价类划分。这也是为什么(a|b)*a(a|b)能从 5 个 DFA 态压到 4 个——其中有两个状态对所有字符的下一步分组完全一致被判定为等价而合并。1.6 工程启示字母表与死状态实现时有两处容易翻车。其一是字母表必须有限NFA 里.和取反类[^0-9]理论上匹配除某集合外的所有字符是无限的我们用可打印 ASCII32–126作为 UNIVERSE 来截出有限字母表匹配时遇到字母表外字符直接判失败行为才与 NFA 一致。其二是死状态子集构造中某些字符可能无去处我们直接跳过视作匹配失败但严谨实现应补一个显式死状态避免 DFA 查表时漏判。1.5 真实运行数据直接在机器上跑 6 个例子状态数对比一目了然NFA 态数 / DFA 态数 / 最小化 DFA 态数正则NFADFA最小化 DFAa(b|c)*d1253[a-z]322[a-z0-9.][a-z]\.[a-z]1366[^0-9]322(a|b)*a(a|b)1654a?b*c1043几个值得玩味的点a(b|c)*d在 NFA 有 12 个状态子集构造后塌成 5 个 DFA 状态再最小化到3个——因为b和c在已读 a、未到结尾的语境下完全等价合并后只剩 {起、中间、终} 三态。邮箱正则 DFA6 且无法再压最小化前后都是 6因为、.、域名段各自承担了不可合并的语义。(a|b)*a(a|b)从 16 个 NFA 态压到 4 个最小化态它识别的是至少含一个 a 的 {a,b} 串。匹配正确性也做了三器一致性校验assertNFA、DFA、最小化 DFA 结果完全一致实测节选正则: a(b|c)*d 状态数 NFA12 DFA5 最小化DFA3 匹配 ad - True 匹配 abcbcd - True 匹配 abc - False 正则: [a-z0-9.][a-z]\.[a-z] 匹配 aliceexample.com - True 匹配 not-an-email - False二、字节码虚拟机栈式执行与编译器2.1 指令集我们设计一套类 JVM 的栈式指令集操作数放在操作数栈上函数局部变量放在**帧Frame**的局部槽里PUSH/STORE/LOAD 操作数栈与局部变量 ADD/SUB/MUL/DIV/MOD/EQ/NE/LT/GT/LE/GE/DUP 算术与比较 JMP/JZ 控制流JZ 弹栈为 0 则跳转 CALL/RET 函数调用与返回 PRINT/HALT 输出与停机2.2 栈式 VM 与 CALL/RETVM 维护三个东西指令列表code、操作数栈stack、调用栈frames。全局代码也有一个全局帧。最关键的CALL/RET约定参数从操作数栈弹出后按顺序放入新帧的局部槽 0…n并把调用点下一条指令地址记为返回地址RET把返回值压回操作数栈弹出当前帧并把pc恢复到返回地址。这里有个真实的坑值得单独记一笔。最初的RET实现是elifopRET:retself.stack.pop()self.frames.pop()self.stack.append(ret)# 漏了 self.pc frame.ret_pc RET只弹了帧、压了返回值却没把pc恢复到调用者返回地址。而run()主循环在调用_execute之前已经pc 1于是RET之后pc指向的是函数体内部下一条指令递归调用fact会一路重新进入函数体、返回值被反复压栈、永不收敛——机器上直接把output.txt写到36GB把磁盘撑满才被我们发现。修复只有一行却直击本质elifopRET:retself.stack.pop()frameself.frames.pop()self.pcframe.ret_pc# 回到调用者的下一条指令self.stack.append(ret)修好后fact(3)的执行轨迹缩进表示调用栈深度完美收敛到 6pc14 CALL (4, 1) 栈[3, 2] 帧局部{0: 3} # 递归调用 fact(2) pc4 LOAD 0 栈[3] 帧局部{0: 2} ...fact(2) 内部又 CALL fact(1)fact(1) 又 CALL fact(0) pc8 PUSH 1 栈[3, 2, 1] 帧局部{0: 0} # 到达基例 n0 pc9 RET 栈[3, 2, 1, 1] # 返回 1 pc15 MUL 栈[3, 2, 1, 1] 帧局部{0: 1} # 1 * fact(0) pc16 RET 栈[3, 2, 1] # 返回 1 pc15 MUL 栈[3, 2, 1] 帧局部{0: 2} # 2 * fact(1) pc16 RET 栈[3, 2] # 返回 2 pc15 MUL 栈[3, 2] 帧局部{0: 3} # 3 * fact(2) pc16 RET 栈[6] # 返回 6 pc2 PRINT 栈[6] 6验证fact(4)24、fact(5)120与数学结果一致。2.3 递归下降编译器到字节码光有手工字节码不过瘾我们再写一个微型语言的编译器支持let变量、while、if/else、赋值与算术比较源程序经词法→语法→代码生成吐出上面的字节码。代码生成的关键在跳转回填while的条件判断后先留一个JZ占位循环体末尾生成JMP回条件处再把两个跳转地址回填。例如let sum0; let i1; while (i10){sumsumi; ii1;} print sum;编译器吐出的字节码节选自真实反汇编0 PUSH 0 1 STORE 0 # sum 0 2 PUSH 1 3 STORE 1 # i 1 4 LOAD 1 5 PUSH 10 6 LE # i 10 ? 7 JZ 17 # 不满足则跳出地址 17 为 print 8 LOAD 0 9 LOAD 1 10 ADD 11 STORE 0 # sum sum i 12 LOAD 1 13 PUSH 1 14 ADD 15 STORE 1 # i i 1 16 JMP 4 # 回到条件判断 17 LOAD 0 18 PRINT # 输出 55实测输出55正是 1…10 的累加和。if/else示例let x7; if (x5){print 1;}else{print 0;}输出1——JZ把基例分支与打印分支缝合得干干净净。2.4 调用约定参数是怎么进帧的CALL (addr, n)把参数个数n编码进指令。VM 从操作数栈依次弹出n个参数用dict(enumerate(args))建新帧的局部槽——也就是说第 0 号参数落在新帧的局部槽 0正好对应我们手写fact里反复LOAD 0取n。返回值则通过RET压回调用者的操作数栈调用者紧接着的MUL/PRINT就能拿到它。这套约定和真实语言 VM 高度一致Python 的CALL_FUNCTION、JVM 的invoke都是参数先入操作数栈、被调者开新帧、返回值压栈。区别只在于真实实现还要处理多返回值、变长参数、闭包捕获环境等但骨架就是眼前这几十行。理解了它再去看 CPython 的frame结构或 Lua 的luaV_execute会觉得原来如此。三、小结这一篇我们把编译原理里前端收尾、后端起步的两块拼图亲手拼了一遍正则引擎递归下降解析 → Thompson NFA → 子集构造 DFA → 划分法最小化。实测状态数对比说明确定性化与最小化能大幅压缩状态规模这正是 lex 类工具高效的根基。字节码虚拟机栈式指令集 调用栈 CALL/RET返回地址约定配合递归下降编译器把高级语言语句变成可执行的字节码。一行的RET修复既解决了递归死循环也顺手暴露了日志无脑打印会撑爆磁盘的工程教训。整套代码纯 Python、零依赖在华为云 ECS 上一键bash run_all.sh即可复现全部输出。如果你也想动手最推荐的路径是先自己实现epsilon_closure和subset_construct对着本文的状态数表格逐条核对再给 VM 加一条CALL故意漏写self.pc frame.ret_pc亲自感受一次栈无限增长 磁盘被日志撑爆的翻车现场——踩过这个坑你对返回地址的理解会牢固十倍。代码仓库机器 m3 真实路径/root/compiler/vm/正则regex_ast.py、nfa.py、dfa.py、regex_engine.py虚拟机bytecode.py、vm.py、compiler.py示例与一键运行examples/、run_all.sh输出见output.txt下一篇计划进入语法分析器专题——手写递归下降与 LL/LR 的碰撞。 编译原理实战（3）：手搓正则引擎与字节码虚拟机
编译原理实战3手搓正则引擎与字节码虚拟机参考宫文学《编译原理》课程「算法篇 / 扩展篇」。本文所有代码均在华为云 ECSUbuntu 24.04Python 3.12上真实运行所有输出均为机器实测结果代码见文末仓库路径。正则与虚拟机是编译原理里看得见摸得着的两块硬骨头。正则引擎是词法分析器lexer的核心字节码虚拟机则是几乎所有脚本语言Python、Lua、JVM的运行底座。这一篇我们不抄库、不画饼从零实现一条正则 → AST → NFA → DFA → 最小化 DFA的流水线再实现一个栈式字节码虚拟机 递归下降编译器并把真实的运行数据贴出来。这正是宫文学老师在课程里反复强调的动手主义算法看懂不算会能在机器上跑出正确的状态数和轨迹才算真正吃透。下面每一段都配有可在 ECS 上复现的代码与输出。一、正则引擎从字符串到状态机1.1 整体流水线一条正则表达式要经过四步才能用来匹配字符串regex 字符串 → 解析递归下降 → AST → Thompson 构造 → NFA带 ε 转移 → 子集构造 → DFA无 ε每字符唯一转移 → 划分细化 → 最小化 DFA合并等价状态为什么不直接用 NFA 匹配因为 NFA 有 ε 转移、一个字符可能走到多个状态匹配时需要维护一组活跃状态子集模拟。DFA 没有这些麻烦每个状态读一个字符有唯一去处匹配就是一路查表。最小化 DFA 则把冗余状态压到最少是词法分析器生成器的标准收尾动作。1.2 正则 AST 与递归下降解析我们用一个最小的递归下降解析器把正则拆成 AST 节点Char / AnyChar / CharClass原子、Concat / Alt / Star / Plus / Quest组合。文法大致是alt → concat (| concat)* concat → repeat* repeat → atom (* | | ?)* atom → ( alt ) | [ class ] | . | \ esc | char处理函数parse_repeat里有个容易踩的坑当peek()返回None已到串尾时若直接写while self.peek() in *?会抛出TypeError: argument of type NoneType is not iterable。正确写法是先判空# regex_ast.py 片段whileself.peek()isnotNoneandself.peek()in*?:node{*:Star,:Plus,?:Quest}[self.peek()](node)self.advance()1.3 Thompson 构造法Thompson 构造的核心思想每个 AST 节点都构造成一个 (start, accept) 两状态的片段片段之间用 ε 转移我们用None标记拼接。比如连接Concat就是把前一段的 accept 用 ε 接到后一段的 startStar则新增一对起止状态允许跳过或循环回来。# nfa.py 片段Star 的构造ifisinstance(node,Star):snfa.add_state();anfa.add_state()s1,a1_build(nfa,node.child)nfa.add_edge(s,EPS,s1)# 进入循环nfa.add_edge(s,EPS,a)# 或跳过nfa.add_edge(a1,EPS,s1)# 循环回来nfa.add_edge(a1,EPS,a)# 或退出returns,aNFA 的匹配用子集模拟维护当前所有活跃状态集合每读一个字符就把集合沿非 ε 边推进再补上 ε-闭包。空集合即匹配失败。ε-闭包是整个 NFA 模拟的基石从一组状态出发沿 ε 边能到达的所有状态都算活跃。实现就是一次 DFS/BFS# nfa.py 片段ε-闭包defepsilon_closure(nfa,states):stacklist(states)closureset(states)whilestack:sstack.pop()for(label,t)innfa.edges[s]:iflabelisNoneandtnotinclosure:# 只沿 ε 边closure.add(t)stack.append(t)returnclosure子集模拟每读一个字符做两件事① 对当前活跃集合里每个状态沿能匹配该字符的非 ε 边走到下一拨状态② 对这些下一拨状态再求一次 ε-闭包得到新的活跃集合。如果某一步活跃集合变空说明没有路径能继续直接判失败。1.4 子集构造与最小化子集构造把NFA 状态的集合当作一个 DFA 状态frozenset作字典键去重。难点在于字母表必须有限——我们把正则中出现过的具体字符含字符类的展开、通配符.的展开收集成字母表字母表外的字符一律视为不匹配。最小化用经典的划分细化法Moore 算法先按接受态 / 非接受态粗分再对每个分组依据读每个字符后落到哪个分组做签名签名不同的拆开直到分组不再变化。等价状态被合并。直觉上两个状态等价当且仅当它们都是接受态或都不是且对任意输入字符它们转移到的下一状态也等价。这个定义是自指的所以用迭代细化的方式逼近每轮都试图把行为不同的状态拆开直到再也无法拆开收敛到的就是最小等价类划分。这也是为什么(a|b)*a(a|b)能从 5 个 DFA 态压到 4 个——其中有两个状态对所有字符的下一步分组完全一致被判定为等价而合并。1.6 工程启示字母表与死状态实现时有两处容易翻车。其一是字母表必须有限NFA 里.和取反类[^0-9]理论上匹配除某集合外的所有字符是无限的我们用可打印 ASCII32–126作为 UNIVERSE 来截出有限字母表匹配时遇到字母表外字符直接判失败行为才与 NFA 一致。其二是死状态子集构造中某些字符可能无去处我们直接跳过视作匹配失败但严谨实现应补一个显式死状态避免 DFA 查表时漏判。1.5 真实运行数据直接在机器上跑 6 个例子状态数对比一目了然NFA 态数 / DFA 态数 / 最小化 DFA 态数正则NFADFA最小化 DFAa(b|c)*d1253[a-z]322[a-z0-9.][a-z]\.[a-z]1366[^0-9]322(a|b)*a(a|b)1654a?b*c1043几个值得玩味的点a(b|c)*d在 NFA 有 12 个状态子集构造后塌成 5 个 DFA 状态再最小化到3个——因为b和c在已读 a、未到结尾的语境下完全等价合并后只剩 {起、中间、终} 三态。邮箱正则 DFA6 且无法再压最小化前后都是 6因为、.、域名段各自承担了不可合并的语义。(a|b)*a(a|b)从 16 个 NFA 态压到 4 个最小化态它识别的是至少含一个 a 的 {a,b} 串。匹配正确性也做了三器一致性校验assertNFA、DFA、最小化 DFA 结果完全一致实测节选正则: a(b|c)*d 状态数 NFA12 DFA5 最小化DFA3 匹配 ad - True 匹配 abcbcd - True 匹配 abc - False 正则: [a-z0-9.][a-z]\.[a-z] 匹配 aliceexample.com - True 匹配 not-an-email - False二、字节码虚拟机栈式执行与编译器2.1 指令集我们设计一套类 JVM 的栈式指令集操作数放在操作数栈上函数局部变量放在**帧Frame**的局部槽里PUSH/STORE/LOAD 操作数栈与局部变量 ADD/SUB/MUL/DIV/MOD/EQ/NE/LT/GT/LE/GE/DUP 算术与比较 JMP/JZ 控制流JZ 弹栈为 0 则跳转 CALL/RET 函数调用与返回 PRINT/HALT 输出与停机2.2 栈式 VM 与 CALL/RETVM 维护三个东西指令列表code、操作数栈stack、调用栈frames。全局代码也有一个全局帧。最关键的CALL/RET约定参数从操作数栈弹出后按顺序放入新帧的局部槽 0…n并把调用点下一条指令地址记为返回地址RET把返回值压回操作数栈弹出当前帧并把pc恢复到返回地址。这里有个真实的坑值得单独记一笔。最初的RET实现是elifopRET:retself.stack.pop()self.frames.pop()self.stack.append(ret)# 漏了 self.pc frame.ret_pc RET只弹了帧、压了返回值却没把pc恢复到调用者返回地址。而run()主循环在调用_execute之前已经pc 1于是RET之后pc指向的是函数体内部下一条指令递归调用fact会一路重新进入函数体、返回值被反复压栈、永不收敛——机器上直接把output.txt写到36GB把磁盘撑满才被我们发现。修复只有一行却直击本质elifopRET:retself.stack.pop()frameself.frames.pop()self.pcframe.ret_pc# 回到调用者的下一条指令self.stack.append(ret)修好后fact(3)的执行轨迹缩进表示调用栈深度完美收敛到 6pc14 CALL (4, 1) 栈[3, 2] 帧局部{0: 3} # 递归调用 fact(2) pc4 LOAD 0 栈[3] 帧局部{0: 2} ...fact(2) 内部又 CALL fact(1)fact(1) 又 CALL fact(0) pc8 PUSH 1 栈[3, 2, 1] 帧局部{0: 0} # 到达基例 n0 pc9 RET 栈[3, 2, 1, 1] # 返回 1 pc15 MUL 栈[3, 2, 1, 1] 帧局部{0: 1} # 1 * fact(0) pc16 RET 栈[3, 2, 1] # 返回 1 pc15 MUL 栈[3, 2, 1] 帧局部{0: 2} # 2 * fact(1) pc16 RET 栈[3, 2] # 返回 2 pc15 MUL 栈[3, 2] 帧局部{0: 3} # 3 * fact(2) pc16 RET 栈[6] # 返回 6 pc2 PRINT 栈[6] 6验证fact(4)24、fact(5)120与数学结果一致。2.3 递归下降编译器到字节码光有手工字节码不过瘾我们再写一个微型语言的编译器支持let变量、while、if/else、赋值与算术比较源程序经词法→语法→代码生成吐出上面的字节码。代码生成的关键在跳转回填while的条件判断后先留一个JZ占位循环体末尾生成JMP回条件处再把两个跳转地址回填。例如let sum0; let i1; while (i10){sumsumi; ii1;} print sum;编译器吐出的字节码节选自真实反汇编0 PUSH 0 1 STORE 0 # sum 0 2 PUSH 1 3 STORE 1 # i 1 4 LOAD 1 5 PUSH 10 6 LE # i 10 ? 7 JZ 17 # 不满足则跳出地址 17 为 print 8 LOAD 0 9 LOAD 1 10 ADD 11 STORE 0 # sum sum i 12 LOAD 1 13 PUSH 1 14 ADD 15 STORE 1 # i i 1 16 JMP 4 # 回到条件判断 17 LOAD 0 18 PRINT # 输出 55实测输出55正是 1…10 的累加和。if/else示例let x7; if (x5){print 1;}else{print 0;}输出1——JZ把基例分支与打印分支缝合得干干净净。2.4 调用约定参数是怎么进帧的CALL (addr, n)把参数个数n编码进指令。VM 从操作数栈依次弹出n个参数用dict(enumerate(args))建新帧的局部槽——也就是说第 0 号参数落在新帧的局部槽 0正好对应我们手写fact里反复LOAD 0取n。返回值则通过RET压回调用者的操作数栈调用者紧接着的MUL/PRINT就能拿到它。这套约定和真实语言 VM 高度一致Python 的CALL_FUNCTION、JVM 的invoke都是参数先入操作数栈、被调者开新帧、返回值压栈。区别只在于真实实现还要处理多返回值、变长参数、闭包捕获环境等但骨架就是眼前这几十行。理解了它再去看 CPython 的frame结构或 Lua 的luaV_execute会觉得原来如此。三、小结这一篇我们把编译原理里前端收尾、后端起步的两块拼图亲手拼了一遍正则引擎递归下降解析 → Thompson NFA → 子集构造 DFA → 划分法最小化。实测状态数对比说明确定性化与最小化能大幅压缩状态规模这正是 lex 类工具高效的根基。字节码虚拟机栈式指令集 调用栈 CALL/RET返回地址约定配合递归下降编译器把高级语言语句变成可执行的字节码。一行的RET修复既解决了递归死循环也顺手暴露了日志无脑打印会撑爆磁盘的工程教训。整套代码纯 Python、零依赖在华为云 ECS 上一键bash run_all.sh即可复现全部输出。如果你也想动手最推荐的路径是先自己实现epsilon_closure和subset_construct对着本文的状态数表格逐条核对再给 VM 加一条CALL故意漏写self.pc frame.ret_pc亲自感受一次栈无限增长 磁盘被日志撑爆的翻车现场——踩过这个坑你对返回地址的理解会牢固十倍。代码仓库机器 m3 真实路径/root/compiler/vm/正则regex_ast.py、nfa.py、dfa.py、regex_engine.py虚拟机bytecode.py、vm.py、compiler.py示例与一键运行examples/、run_all.sh输出见output.txt下一篇计划进入语法分析器专题——手写递归下降与 LL/LR 的碰撞。