1. 从“找茬”游戏到正则表达式为什么我们需要形式语言如果你用过任何一个文本编辑器里的“查找”功能或者在网上搜索时用过通配符比如*代表任意字符那你其实已经和形式语言打过交道了。形式语言听起来很学术但说白了它就是一套严谨的规则用来定义什么样的字符串是“合法”的什么样的不是。比如一个用来描述“所有由字母a和b组成的字符串”的语言它的规则就是“字符串里只能有a和b”。为什么程序员、编译器工程师甚至网络安全专家都要关心这个因为计算机本质上就是个“规则执行器”。当你写下一行代码int x 10;编译器需要判断这串字符是否符合C语言或Java的语法规则。这个判断的第一步就是词法分析——把一长串源代码字符切割成一个个有意义的“单词”也叫token比如int、x、、10、;。这个过程就像玩一个超级复杂的“找茬”游戏而游戏规则最初就是用正则表达式来描述的。正则表达式就是描述这类规则最直观、最强大的工具之一。比如描述“一个合法的变量名”可能是以字母或下划线开头后面跟着零个或多个字母、数字或下划线。用正则表达式写出来大概像[a-zA-Z_][a-zA-Z0-9_]*。你看它用[]表示“选择”用*表示“重复零次或多次”非常直观。但问题来了计算机怎么“理解”并“执行”这个规则呢计算机可看不懂[a-zA-Z_]*这种符号。它需要一个更机械、更底层的模型来一步步处理输入。这就引出了我们今天的两位主角正则表达式和有限自动机。简单来说正则表达式是给人看的“设计图纸”而有限自动机是给计算机跑的“流水线机器”。接下来的内容我会带你亲手把图纸变成机器看看这背后的魔法是如何实现的以及它在真实世界里比如写一个简易的词法分析器到底有多好用。2. 正则表达式不只是“.*”的文本匹配利器很多人对正则表达式的印象停留在“复杂的文本匹配工具”觉得那一串神秘符号 (\d\.\d) 让人头大。其实剥开语法糖衣它的核心思想非常简单就是一种通过代数运算来组合语言的方法。理解这一点是连接它与有限自动机的关键。2.1 正则表达式的“原子操作”与代数定律正则表达式建立在三个最基本的“原子”上空串 ε表示只包含一个空字符串的语言{ε}。空集 ∅表示一个字符串都不包含的空语言{}。单个符号 a表示只包含一个符号a的语言{a}。有了原子我们就可以用三种运算来组合出复杂的语言并集 (Union,|或)R|S表示属于语言R或属于语言S的字符串。比如a|b描述的语言是{a, b}。连接 (Concatenation)RS表示一个字符串前半部分属于R后半部分属于S。比如(a|b)(c|d)描述的语言是{ac, ad, bc, bd}。注意连接像乘法通常不写符号。克林星号 (Kleene Star,*)R*表示将R中的字符串连接零次或任意多次。这是实现“重复”的关键。a*就是{ε, a, aa, aaa, ...}。这就像做代数题一样正则表达式也满足一些定律利用它们可以化简表达式结合律(R|S)|T R|(S|T)(RS)T R(ST)。分配律R(S|T) RS | RT(S|T)R SR | TR。幂等律R|R R。零元R∅ ∅R ∅任何语言连接空语言还是空语言R|∅ R。单位元Rε εR R。我刚开始学的时候总觉得记这些定律很枯燥。直到有一次我写了一个匹配版本号的正则表达式v\d\.\d(\.\d)*看起来没问题。但同事指出它无法匹配单纯的v1或v1.0。我原本想改成v\d(\.\d)*但突然想到分配律\d(\.\d)*其实可以看作\d和(\.\d)*的连接而(\.\d)*包含了零次的情况即ε。所以v\d(\.\d)*确实能匹配v1此时(\.\d)*匹配ε。这个例子让我明白这些代数定律不是摆设而是我们理解和构造正确、高效表达式的工具箱。2.2 从正则表达式到实际应用场景让我们看几个更贴近开发的例子感受一下正则表达式的描述能力匹配整数可以是正数、负数或零。-?(\d)。-?表示负号出现零次或一次\d表示一个或多个数字。匹配IP地址简化版一个点分十进制的IP。(\d{1,3}\.){3}\d{1,3}。\d{1,3}匹配1到3位数字(…){3}表示前面的分组重复3次最后再来一组不带点的数字。匹配邮箱地址极度简化版仅示意[a-zA-Z0-9._%-][a-zA-Z0-9.-]\.[a-zA-Z]{2,}。这里用到了字符集[]、量词和{2,}。在实际编程中比如Python的re模块JavaScript的/pattern/字面量都是直接使用正则表达式引擎来处理这些模式。当你调用re.match(pattern, string)时底层引擎所做的工作本质上就是在模拟一个有限自动机的运行。接下来我们就来看看这个藏在引擎底下的“机器”到底长什么样。3. 有限自动机理解正则表达式背后的“状态机”有限自动机是计算机科学中最美妙、最实用的抽象模型之一。它就像一个拥有有限内存即状态的小机器人从左到右读取输入字符串上的每一个符号并根据当前状态和读到的符号决定下一步跳到哪个状态。当字符串读完如果机器人停在了“接受状态”那么这个字符串就被认为符合规则。3.1 确定性有限自动机一条路走到黑确定性有限自动机是最简单的版本简称DFA。它的特点就两个字确定。在任何一个状态读到一个输入符号有且只有一条转移路径可走。它不会“分心”也没有“随机选择”。一个DFA可以用一个五元组严格定义M (Q, Σ, δ, q0, F)。别被符号吓到我们拆开看Q所有状态的集合。比如{q0, q1, q2}。Σ输入字母表。比如{0, 1}。δ转移函数。这是DFA的“大脑”是一个查表规则δ(当前状态, 输入符号) 下一个状态。q0初始状态。机器启动的地方。F接受状态终结状态的集合。机器停在这里就算成功。举个例子我们设计一个DFA用来识别“所有以01结尾的二进制串由0和1组成”。状态设计我们需要记住关于已读前缀的“关键信息”。q0初始状态表示还没看到任何与模式01相关的有效后缀。或者刚读到一个1因为1不能作为01的开头。q1表示刚刚读到了一个0这可能是模式01的开头。q2表示已经读到了01即模式匹配成功。这是一个接受状态。转移规则在q0读0- 转到q1看到了开头读1- 留在q01无效重置。在q1读0- 留在q1新的0覆盖旧的仍是潜在开头读1- 转到q2完成了01。在q2读0- 转到q1新开始读1- 转到q0读1破坏了01结尾因为...011并不以01结尾最后一个字符是1。图形化表示转移图0 1 0 (q0) -- (q1) -- ((q2)) ^ | | |1 |0 |1 |________| | 1 v ------- (q0)双圈((q2))表示接受状态。你可以拿字符串11001试试从q0开始依次读入1,1,0,0,1状态变化是q0-q0-q0-q1-q1-q2最终停在接受状态q2所以接受。试试101q0-q1-q2-q0最终停在非接受状态q0拒绝。DFA非常直观但设计起来有时很繁琐。比如要识别“包含连续三个1的二进制串”你需要至少4个状态来计数。它的优势是运行效率极高时间复杂度是O(n)n是输入长度因为每一步都是确定的查表操作。3.2 非确定性有限自动机并行宇宙的探索者非确定性有限自动机则提供了更大的设计灵活性简称NFA。它允许“不确定性”在一个状态读到一个输入符号甚至是空串ε可以有多条转移路径可选。或者没有转移路径机器“死掉”。你可以想象机器同时分裂出多个副本探索所有可能的路径。只要至少有一个副本在读完输入后到达接受状态整个NFA就接受这个字符串。NFA的定义和DFA类似但关键区别在转移函数δδ(当前状态, 输入符号) 一个状态的集合可能为空集。它返回的不是一个状态而是一堆可能的状态。为什么需要NFA因为它通常更易于设计还是“以01结尾”的例子用NFA可以设计得更简洁状态q0初始状态。状态q1读到一个0后可能进入的状态。状态q2接受状态读到一个1后可能进入的状态前提是前一个状态是q1。 转移规则可以设计为δ(q0, 0) {q0, q1}读0时可以留在原地也可以进入“可能匹配”状态δ(q0, 1) {q0}δ(q1, 1) {q2}关键只有从q1读1才能到接受态δ(q2, 任何符号) ∅接受后不再转移或者设计成循环这个NFA看起来没那么“确定”但它和之前的DFA是等价的识别的是同一种语言。NFA的优势在于它将“记忆”任务比如“我是否刚刚看到了一个0”部分交给了“并行探索”机制从而简化了状态设计。对于连接、并集、星号这些运算NFA的构造有非常直接和优美的算法这为后面“从正则表达式到NFA”的转换铺平了道路。4. 等价转换的核心从正则表达式到有限自动机这是形式语言理论中最漂亮的部分之一克林定理证明了正则表达式、DFA、NFA三者描述的语言能力是完全等价的即正则语言。这意味着任何能用正则表达式描述的规则都能被一台DFA或NFA识别反之亦然。而将正则表达式转换为自动机是编译器词法分析器生成如Lex工具的核心步骤。4.1 构造法正则表达式 - ε-NFA我们有一种系统性的方法可以将任何正则表达式递归地构建成一个等价的、带空转移的NFA。空转移ε允许不消耗输入符号就跳转状态这让构造过程更模块化。构造规则汤普森构造法基础规则空串 ε构造一个只有两个状态开始和接受的自动机用一条ε边连接。(start) --ε-- ((accept))符号 a构造一个只有两个状态的自动机用一条标记为a的边连接。(start) --a-- ((accept))空集 ∅构造一个开始状态和接受状态不连通的自动机。归纳规则并集 R|S新建一个开始状态和一个接受状态。用ε边将新开始状态分别连接到R和S子自动机的开始状态将R和S子自动机的接受状态分别用ε边连接到新的接受状态。注意R和S子自动机原有的接受状态不再作为接受状态。连接 RS将R子自动机的接受状态和S子自动机的开始状态用ε边连接起来。整体的开始状态是R的开始状态整体的接受状态是S的接受状态。克林星号 R*新建一个开始状态和一个接受状态。首先用ε边将新开始状态连接到R的开始状态以及连接到新的接受状态代表重复0次。然后用ε边将R的接受状态连接到R的开始状态代表重复多次同时也连接到新的接受状态。这个过程完全是机械的、可编程实现的。我最早在实现一个简单的正则表达式引擎时就手动编码了这个构造过程。虽然最终生成的ε-NFA状态数会比较多因为每一步都引入了新的状态但它结构清晰完美对应了正则表达式的递归结构。4.2 化简与确定化ε-NFA - NFA - DFA汤普森构造法产生的是ε-NFA它有很多ε边运行效率低。我们需要把它转化成更高效的DFA。这个过程分两步第一步消除ε转移ε闭包ε闭包是指从某个状态出发只通过ε边所能到达的所有状态的集合包括自身。消除ε转移的算法是对于原自动机的每一个状态计算它的ε闭包。然后构建新的NFA无ε转移其中新状态就是原状态的ε闭包。新转移规则是如果原NFA中状态集A中的某个状态s通过一个非ε符号a可以到达状态t那么在新NFA中状态集A通过符号a就可以到达状态t的ε闭包。第二步子集构造法NFA - DFA这是最核心的步骤。NFA的不确定性在于一个状态读一个符号可能去到多个状态。DFA要求只有一个状态。子集构造法的思想非常巧妙让DFA的每个状态对应原NFA的一个状态集合。DFA的初始状态就是原NFA初始状态的ε闭包。对于DFA中的某个状态即一个NFA状态集合S和输入符号a计算这个集合S中所有状态通过a能到达的所有NFA状态的并集再对这个并集求ε闭包。这个结果就构成了DFA中从状态S出发、输入a所到达的新状态。重复这个过程直到没有新的DFA状态产生。DFA的接受状态是那些包含了至少一个原NFA接受状态的DFA状态即状态集合。实战举例假设我们有一个简单的正则表达式a(b|c)*。先用汤普森构造法得到ε-NFA然后通过上述两步转化为DFA。你会发现最终得到的DFA可能有好几个状态每个状态都精确记录了“在读取了部分输入后原NFA所有可能的活跃状态是什么”。这个DFA就是最终可以高效执行匹配的机器。在编译原理中Lex/Flex这类词法分析器生成器内部就是先把你写的正则表达式规则转换成NFA再通过子集构造法生成一个优化的DFA状态转移表最后输出成可执行的C代码。你平时用的grep、sed等工具底层也是类似的原理。5. 实践解析动手实现一个简易词法分析器理论说得再多不如动手做一遍。让我们用上面学到的知识尝试为一个超简化的编程语言比如只能处理整数和加法写一个词法分析器的核心部分。我们不会用到Lex而是手动模拟这个过程加深理解。目标将输入字符串如x 42 y分解成一系列词法单元token标识符变量名x,y赋值运算符整数常量42加法运算符步骤1用正则表达式定义词法单元我们先为每种token定义一个正则表达式标识符[a-zA-Z_][a-zA-Z0-9_]*字母或下划线开头后接零个或多个字母、数字、下划线整数\d一个或多个数字赋值符加号\加号在正则中是特殊字符需要转义空白符\s一个或多个空格、制表符等需要被忽略步骤2构建整合的NFA我们可以为每个正则表达式单独构建NFA使用汤普森构造法然后将它们用“并集”的方式组合成一个大NFA。这个大NFA可以识别以上任意一种token。但这里有个关键当输入42时它既能匹配“整数”规则\d其前缀4也能匹配“整数”规则吗是的但我们需要最长匹配。在并集构造时我们需要为每个子NFA的接受状态打上标签返回的token类型。步骤3模拟DFA运行核心算法我们不需要显式生成所有DFA状态图可以直接用子集构造法的思想进行“在线”模拟也就是著名的最长匹配算法def tokenize(input_string): tokens [] i 0 n len(input_string) # 定义每个token规则对应的NFA这里用DFA模拟思想 # 实践中这里会是预编译好的DFA状态转移表。 # 我们简化用函数模拟匹配过程。 def match(pattern, start_pos): # 这是一个简化模拟。真实情况是运行该pattern对应的DFA。 # 假设我们有一个函数 run_dfa(pattern, input, pos) 返回匹配长度。 # 这里用正则库模拟DFA效果。 import re m re.match(pattern, input_string[start_pos:]) return m.end() if m else 0 patterns [ (IDENTIFIER, r[a-zA-Z_][a-zA-Z0-9_]*), (INTEGER, r\d), (ASSIGN, r), (PLUS, r\), (WHITESPACE, r\s), ] while i n: if input_string[i].isspace(): # 快速跳过空白 i 1 continue longest_match_len 0 matched_type None for token_type, pattern in patterns: length match(pattern, i) if length longest_match_len: longest_match_len length matched_type token_type if longest_match_len 0: raise SyntaxError(fUnexpected character at position {i}: {input_string[i]}) if matched_type ! WHITESPACE: # 忽略空白符 lexeme input_string[i:ilongest_match_len] tokens.append((matched_type, lexeme)) i longest_match_len return tokens # 测试 input_code x 42 y print(tokenize(input_code)) # 输出: [(IDENTIFIER, x), (ASSIGN, ), (INTEGER, 42), (PLUS, ), (IDENTIFIER, y)]这个简易的tokenize函数其核心思想就是并行运行所有token规则对应的DFA在代码中我们用re.match模拟了每个DFA并选择匹配最长的那个规则作为当前token。这其实就是对整合NFA进行子集构造后DFA运行时的“最长匹配”准则。在实际的Lex中这一步是通过精心设计的DFA状态机和优先级规则来实现的效率极高。通过这个例子你应该能清晰地看到从正则表达式描述规则到有限自动机执行规则再到具体的词法分析应用整个链条是如何打通的。理解了这个过程你再去看Flex的.l文件或者思考如何优化一个复杂文本模式的匹配性能思路就会清晰很多。正则表达式不再是黑魔法有限自动机也不再是枯燥的数学概念它们是你解决实际文本处理问题的强大工具箱。