尧图网站建设 
正则表达式是怎么匹配的NFA 与 DFA你写的正则表达式a(b|c)*程序怎么在毫秒内判断一个字符串是否匹配背后是编译原理的经典理论正则 → NFA → 匹配。今天讲透它——理解之后你写正则的能力会上一个台阶。一、正则表达式一种有限自动机的描述正则表达式不是随便发明的语法糖它对应一个严格的数学对象正则语言——可以用有限自动机Finite Automaton识别的语言。正则: a(b|c)* 意思: 一个 a, 后面跟任意多个 b 或 c编译器/工具处理它的两步正则 → NFA非确定性有限自动机Thompson 构造O(n) 复杂度NFA 匹配用集合模拟所有可能状态避免回溯爆炸二、NFA 与 DFA 的区别NFA非确定性同一输入可能有多个后继状态选择分支。模拟时用状态集合同时跟踪所有可能DFA确定性每个状态输入唯一确定后继。匹配 O(1) 每字符但可能状态爆炸工程上的选择先构造 NFA简单、O(n) 大小再按需转 DFA子集构造法或用 NFA 模拟消耗低、速度够。三、为什么不用回溯实现正则很多人以为正则匹配是回溯试错Python 的re模块就是回溯实现。回溯的问题是指数级最坏情况(a|a)*b 匹配 aaaa...a无 b 回溯实现: 尝试所有组合 - 2^n 次 NFA 模拟: O(n*m) 线性这就是正则拒绝服务攻击ReDoS的根源——恶意构造的正则能让服务器 CPU 打满。Google 的 RE2 引擎改用 NFA/DFA 模拟从根本上免疫 ReDoS。四、代码演示NFA 匹配# 正则 a(b|c)* 的 NFAThompson 构造的简化表示# 状态转移表: {状态: {输入字符: [后继状态]}}states{0:{a:[1]},# 起始: 读 a 到状态 11:{b:[2],c:[2],eps:[3]},# b 或 c 到 2; 或 eps 跳 3(接受)2:{eps:[1,3]},# 回到 1 (循环) 或到 3 (结束)3:{},# 接受态}defnfa_match(s,states,start0,accept3):current{start}# 当前状态集合forchins:nxtset()forstincurrent:# 直接转移fortinstates.get(st,{}).get(ch,[]):nxt.add(t)# eps 闭包后再转移fortinstates.get(st,{}).get(eps,[]):fort2instates.get(t,{}).get(ch,[]):nxt.add(t2)currentnxtifnotcurrent:returnFalse# 接受态检查含 eps 闭包finalset(current)forstinlist(current):final.update(states.get(st,{}).get(eps,[]))returnacceptinfinalforsin[ab,ac,abcb,ad,abc]:print(f {s}:{匹配 ✓ifnfa_match(s,states)else不匹配})运行输出ab: 匹配 ✓ ac: 匹配 ✓ abcb: 匹配 ✓ ad: 不匹配 abc: 匹配 ✓a后跟任意多个b/c都能匹配ab、ac、abcb、abcad因为 d 不在字符集里被拒绝。整个过程是状态集合并行推进没有任何回溯——所以最坏情况也是线性复杂度。五、避坑清单回溯引擎有 ReDoS 风险避免嵌套量词如(a)b或改用 RE2 类线性引擎量词要明确贪婪/懒惰*默认贪婪尽量多匹配*?懒惰——写错结果差很远锚点别忘^...$才表示整串匹配否则子串匹配也算成功NFA 转 DFA 可能状态爆炸指数级膨胀是真实风险工程上常用混合策略正则不是万能的嵌套结构如括号配对、JSON不是正则语言——用解析器下推自动机六、想系统学编译原理本文精选自ima 知识号【Kruptos】《编译原理与工具链》订阅库第 011 期正则表达式与词法规则、第 012 期从正则到 NFA Thompson 构造等 100 期系统教程从词法分析、语法分析到中间表示、代码生成贯穿用 Python 手写迷你编译器每期配可运行代码。 完整系列 100 期 配套代码已在 ima 知识号发布本文只是系列的一个切片。完整系列100 期系统教程 每期可运行代码在 ima 知识号【Kruptos】持续更新中 68 技术知识库信号与系统、SDR 软件无线电、数字信号处理、操作系统、AI Agent、大模型微调……几乎覆盖全部软硬件技术栈 8 款 AI 技能系列生产、知识库管理、CMMI 受管开发、自进化 Agent 等已在 ima 技能广场上架即装即用✅ 全部免费订阅后续更新自动推送 订阅方式打开 ima腾讯智能工作台→ 搜索「Kruptos」→ 一键订阅。或在 ima 内直接搜索《编译原理与工具链》等知识库名称。 你写过最复杂的正则是什么踩过 ReDoS 吗评论区聊聊——想看 NFA 转 DFA 还是语法分析点赞高的安排。作者Kruptos西电毕业13 年无线通信/DSP/嵌入式科研原创内容转载注明出处 正则表达式是怎么匹配的？NFA 与 DFA
正则表达式是怎么匹配的NFA 与 DFA你写的正则表达式a(b|c)*程序怎么在毫秒内判断一个字符串是否匹配背后是编译原理的经典理论正则 → NFA → 匹配。今天讲透它——理解之后你写正则的能力会上一个台阶。一、正则表达式一种有限自动机的描述正则表达式不是随便发明的语法糖它对应一个严格的数学对象正则语言——可以用有限自动机Finite Automaton识别的语言。正则: a(b|c)* 意思: 一个 a, 后面跟任意多个 b 或 c编译器/工具处理它的两步正则 → NFA非确定性有限自动机Thompson 构造O(n) 复杂度NFA 匹配用集合模拟所有可能状态避免回溯爆炸二、NFA 与 DFA 的区别NFA非确定性同一输入可能有多个后继状态选择分支。模拟时用状态集合同时跟踪所有可能DFA确定性每个状态输入唯一确定后继。匹配 O(1) 每字符但可能状态爆炸工程上的选择先构造 NFA简单、O(n) 大小再按需转 DFA子集构造法或用 NFA 模拟消耗低、速度够。三、为什么不用回溯实现正则很多人以为正则匹配是回溯试错Python 的re模块就是回溯实现。回溯的问题是指数级最坏情况(a|a)*b 匹配 aaaa...a无 b 回溯实现: 尝试所有组合 - 2^n 次 NFA 模拟: O(n*m) 线性这就是正则拒绝服务攻击ReDoS的根源——恶意构造的正则能让服务器 CPU 打满。Google 的 RE2 引擎改用 NFA/DFA 模拟从根本上免疫 ReDoS。四、代码演示NFA 匹配# 正则 a(b|c)* 的 NFAThompson 构造的简化表示# 状态转移表: {状态: {输入字符: [后继状态]}}states{0:{a:[1]},# 起始: 读 a 到状态 11:{b:[2],c:[2],eps:[3]},# b 或 c 到 2; 或 eps 跳 3(接受)2:{eps:[1,3]},# 回到 1 (循环) 或到 3 (结束)3:{},# 接受态}defnfa_match(s,states,start0,accept3):current{start}# 当前状态集合forchins:nxtset()forstincurrent:# 直接转移fortinstates.get(st,{}).get(ch,[]):nxt.add(t)# eps 闭包后再转移fortinstates.get(st,{}).get(eps,[]):fort2instates.get(t,{}).get(ch,[]):nxt.add(t2)currentnxtifnotcurrent:returnFalse# 接受态检查含 eps 闭包finalset(current)forstinlist(current):final.update(states.get(st,{}).get(eps,[]))returnacceptinfinalforsin[ab,ac,abcb,ad,abc]:print(f {s}:{匹配 ✓ifnfa_match(s,states)else不匹配})运行输出ab: 匹配 ✓ ac: 匹配 ✓ abcb: 匹配 ✓ ad: 不匹配 abc: 匹配 ✓a后跟任意多个b/c都能匹配ab、ac、abcb、abcad因为 d 不在字符集里被拒绝。整个过程是状态集合并行推进没有任何回溯——所以最坏情况也是线性复杂度。五、避坑清单回溯引擎有 ReDoS 风险避免嵌套量词如(a)b或改用 RE2 类线性引擎量词要明确贪婪/懒惰*默认贪婪尽量多匹配*?懒惰——写错结果差很远锚点别忘^...$才表示整串匹配否则子串匹配也算成功NFA 转 DFA 可能状态爆炸指数级膨胀是真实风险工程上常用混合策略正则不是万能的嵌套结构如括号配对、JSON不是正则语言——用解析器下推自动机六、想系统学编译原理本文精选自ima 知识号【Kruptos】《编译原理与工具链》订阅库第 011 期正则表达式与词法规则、第 012 期从正则到 NFA Thompson 构造等 100 期系统教程从词法分析、语法分析到中间表示、代码生成贯穿用 Python 手写迷你编译器每期配可运行代码。 完整系列 100 期 配套代码已在 ima 知识号发布本文只是系列的一个切片。完整系列100 期系统教程 每期可运行代码在 ima 知识号【Kruptos】持续更新中 68 技术知识库信号与系统、SDR 软件无线电、数字信号处理、操作系统、AI Agent、大模型微调……几乎覆盖全部软硬件技术栈 8 款 AI 技能系列生产、知识库管理、CMMI 受管开发、自进化 Agent 等已在 ima 技能广场上架即装即用✅ 全部免费订阅后续更新自动推送 订阅方式打开 ima腾讯智能工作台→ 搜索「Kruptos」→ 一键订阅。或在 ima 内直接搜索《编译原理与工具链》等知识库名称。 你写过最复杂的正则是什么踩过 ReDoS 吗评论区聊聊——想看 NFA 转 DFA 还是语法分析点赞高的安排。作者Kruptos西电毕业13 年无线通信/DSP/嵌入式科研原创内容转载注明出处