当前位置：首页 > news >正文

实现一个简单的正则表达式引擎

news 2026/4/29 20:56:44

文章目录

实现一个简单的正则表达式引擎 🚀
- 正则表达式基础 📖
- 实现思路 🧠
- 实现解析器（Parser）🔍
- 构建NFA 🏗️
- 实现匹配算法 ⚡
- 整合引擎 🧩
- 性能优化 💨
- 扩展功能 🔧
- 总结 📝

实现一个简单的正则表达式引擎 🚀

正则表达式是计算机科学中一种强大的文本处理工具，它允许我们通过一种简洁的语法来描述、匹配和操作字符串。从验证电子邮件地址到在大型日志文件中搜索模式，正则表达式无处不在。今天，我们将一起探索如何从零开始构建一个简单的正则表达式引擎！通过这个过程，你不仅能加深对正则表达式工作原理的理解，还能提升自己的编程和算法设计能力。

正则表达式基础 📖

在我们深入实现之前，让我们快速回顾一下正则表达式的基本概念。正则表达式（regex）是一种用于描述字符串模式的语法。它由普通字符（如字母和数字）和特殊字符（称为元字符）组成，这些元字符赋予了正则表达式强大的匹配能力。

一些常见的元字符包括：

.- 匹配任意单个字符
*- 匹配前一个字符零次或多次
+- 匹配前一个字符一次或多次
?- 匹配前一个字符零次或一次
|- 表示"或"关系
^- 匹配字符串的开始
$- 匹配字符串的结束

如果你想了解更多关于正则表达式的基础知识，可以参考正则表达式指南，这是一个非常全面的正则表达式资源网站。

实现思路 🧠

要实现一个正则表达式引擎，我们需要将正则表达式转换为一种能够进行模式匹配的数据结构。最常用的方法是先将正则表达式转换为非确定性有限自动机（NFA），然后使用NFA来匹配字符串。

上面的流程图展示了我们正则表达式引擎的基本工作流程。接下来，我们将逐步实现每个组件。

实现解析器（Parser）🔍

首先，我们需要将正则表达式字符串解析成一个抽象语法树（AST）。AST是一种树状数据结构，它表示正则表达式的结构，使我们能够更容易地处理操作符的优先级和分组。

classASTNode:def__init__(self,type,value=None,children=None):self.type=typeself.value=value self.children=childrenor[]classRegexParser:def__init__(self,pattern):self.pattern=pattern self.index=0self.length=len(pattern)defparse(self):returnself._parse_expr()def_parse_expr(self):# 解析表达式（|操作符）node=self._parse_term()whileself.index<self.lengthandself.pattern[self.index]=='|':self.index+=1right=self._parse_term()node=ASTNode('|',children=[node,right])returnnodedef_parse_term(self):# 解析项（连接）node=self._parse_factor()while(self.index<self.lengthandself.pattern[self.index]notin'|)'):right=self._parse_factor()node=ASTNode('concat',children=[node,right])returnnodedef_parse_factor(self):# 解析因子（*+?操作符）node=self._parse_atom()ifself.index<self.lengthandself.pattern[self.index]in'*+?':op=self.pattern[self.index]self.index+=1node=ASTNode(op,children=[node])returnnodedef_parse_atom(self):# 解析原子（字符、分组等）ifself.index>=self.length:raiseValueError("Unexpected end of pattern")char=self.pattern[self.index]ifchar=='(':self.index+=1node=self._parse_expr()ifself.index>=self.lengthorself.pattern[self.index]!=')':raiseValueError("Unclosed parenthesis")self.index+=1returnnodeelifchar==')':raiseValueError("Unexpected closing parenthesis")elifchar=='\\':self.index+=1ifself.index>=self.length:raiseValueError("Unexpected end of pattern after backslash")char=self.pattern[self.index]self.index+=1returnASTNode('char',value=char)else:self.index+=1returnASTNode('char',value=char)

这个解析器能够处理基本的正则表达式语法，包括字符匹配、分组、以及*、+、?和|操作符。

构建NFA 🏗️

接下来，我们需要将AST转换为非确定性有限自动机（NFA）。NFA是一种状态机，它可以同时处于多个状态，这使得它能够高效地处理正则表达式中的不确定性（如*和|操作符）。

classState:def__init__(self,is_end=False):self.is_end=is_end self.transitions={}# char -> set of statesself.epsilon_transitions=set()# ε-transitionsclassNFA:def__init__(self,start,end):self.start=start self.end=end@staticmethoddeffrom_ast(node):ifnode.type=='char':returnNFA._compile_char(node.value)elifnode.type=='concat':returnNFA._compile_concat(node.children)elifnode.type=='|':returnNFA._compile_alternation(node.children)elifnode.type=='*':returnNFA._compile_star(node.children[0])elifnode.type=='+':returnNFA._compile_plus(node.children[0])elifnode.type=='?':returnNFA._compile_optional(node.children[0])else:raiseValueError(f"Unknown node type:{node.type}")@staticmethoddef_compile_char(char):start=State()end=State(is_end=True)start.transitions[char]={end}returnNFA(start,end)@staticmethoddef_compile_concat(nodes):ifnotnodes:returnNFA._compile_empty()first_nfa=NFA.from_ast(nodes[0])current_nfa=first_nfafornodeinnodes[1:]:next_nfa=NFA.from_ast(node)current_nfa.end.epsilon_transitions.add(next_nfa.start)current_nfa.end.is_end=Falsecurrent_nfa=NFA(current_nfa.start,next_nfa.end)returncurrent_nfa@staticmethoddef_compile_alternation(nodes):ifnotnodes:returnNFA._compile_empty()start=State()end=State(is_end=True)fornodeinnodes:nfa=NFA.from_ast(node)start.epsilon_transitions.add(nfa.start)nfa.end.epsilon_transitions.add(end)nfa.end.is_end=FalsereturnNFA(start,end)@staticmethoddef_compile_star(node):nfa=NFA.from_ast(node)start=State()end=State(is_end=True)start.epsilon_transitions.add(nfa.start)start.epsilon_transitions.add(end)nfa.end.epsilon_transitions.add(nfa.start)nfa.end.epsilon_transitions.add(end)nfa.end.is_end=FalsereturnNFA(start,end)@staticmethoddef_compile_plus(node):nfa=NFA.from_ast(node)start=State()end=State(is_end=True)start.epsilon_transitions.add(nfa.start)nfa.end.epsilon_transitions.add(nfa.start)nfa.end.epsilon_transitions.add(end)nfa.end.is_end=FalsereturnNFA(start,end)@staticmethoddef_compile_optional(node):nfa=NFA.from_ast(node)start=State()end=State(is_end=True)start.epsilon_transitions.add(nfa.start)start.epsilon_transitions.add(end)nfa.end.epsilon_transitions.add(end)nfa.end.is_end=FalsereturnNFA(start,end)@staticmethoddef_compile_empty():start=State()end=State(is_end=True)start.epsilon_transitions.add(end)returnNFA(start,end)

NFA的构建过程是递归的：每个AST节点类型都有对应的编译方法，这些方法创建适当的状态和转换。

实现匹配算法 ⚡

有了NFA后，我们需要实现一个匹配算法。由于NFA可以同时处于多个状态，我们使用一个包含当前所有可能状态的集合，并随着输入字符的处理更新这个集合。

classMatcher:def__init__(self,nfa):self.nfa=nfadefmatch(self,string):current_states=self._epsilon_closure({self.nfa.start})forcharinstring:next_states=set()forstateincurrent_states:ifcharinstate.transitions:next_states|=state.transitions[char]current_states=self._epsilon_closure(next_states)returnany(state.is_endforstateincurrent_states)def_epsilon_closure(self,states):closure=set(states)stack=list(states)whilestack:state=stack.pop()fornext_stateinstate.epsilon_transitions:ifnext_statenotinclosure:closure.add(next_state)stack.append(next_state)returnclosure

匹配算法的工作原理是：

从NFA的起始状态开始，通过ε闭包获取所有可能的状态
对于输入字符串中的每个字符，从当前状态集合中通过该字符转换到新的状态集合
再次通过ε闭包获取所有可能的状态
处理完所有字符后，检查当前状态集合中是否包含接受状态

整合引擎 🧩

现在我们将所有组件整合在一起，创建一个完整的正则表达式引擎：

classRegexEngine:def__init__(self,pattern):self.pattern=pattern parser=RegexParser(pattern)ast=parser.parse()self.nfa=NFA.from_ast(ast)self.matcher=Matcher(self.nfa)defmatch(self,string):returnself.matcher.match(string)# 使用示例if__name__=="__main__":# 测试一些简单的正则表达式test_cases=[("a","a",True),("a","b",False),("a*","",True),("a*","aaa",True),("a+","",False),("a+","aaa",True),("a|b","a",True),("a|b","b",True),("a|b","c",False),("(ab)*","ababab",True),("(ab)*","aba",False),]forpattern,string,expectedintest_cases:engine=RegexEngine(pattern)result=engine.match(string)print(f"Pattern:{pattern}, String:{string}, Expected:{expected}, Got:{result}")assertresult==expected,f"Failed for pattern '{pattern}' and string '{string}'"print("All tests passed! 🎉")

性能优化 💨

我们实现的引擎功能完整，但在处理复杂正则表达式时可能性能不佳。以下是一些优化思路：

将NFA转换为DFA：确定性有限自动机（DFA）每个状态在给定输入字符下只能转换到一个状态，这可以使匹配过程更高效。可以使用子集构造算法将NFA转换为DFA。
缓存ε闭包：预计算和缓存状态的ε闭包，避免重复计算。
懒评估DFA：只在需要时计算DFA状态，避免状态爆炸问题。

如果你想深入了解正则表达式引擎的优化技术，可以查阅正则表达式匹配原理这篇文章，它详细介绍了多种高效的正则表达式实现技术。

扩展功能 🔧

我们的基础引擎可以进一步扩展以支持更多功能：

字符类：支持[a-z]、[0-9]等字符类
转义序列：支持\d、\w、\s等预定义字符类
锚点：完整支持^和$锚点
捕获组：支持提取匹配的子字符串
反向引用：支持引用先前匹配的组

# 字符类扩展示例def_parse_atom(self):ifself.index>=self.length:raiseValueError("Unexpected end of pattern")char=self.pattern[self.index]ifchar=='[':self.index+=1# 解析字符类negate=Falseifself.index<self.lengthandself.pattern[self.index]=='^':negate=Trueself.index+=1ranges=[]whileself.index<self.lengthandself.pattern[self.index]!=']':ifself.index+2<self.lengthandself.pattern[self.index+1]=='-':start=self.pattern[self.index]end=self.pattern[self.index+2]ranges.append((start,end))self.index+=3else:ranges.append((self.pattern[self.index],self.pattern[self.index]))self.index+=1ifself.index>=self.lengthorself.pattern[self.index]!=']':raiseValueError("Unclosed character class")self.index+=1returnASTNode('char_class',value=(negate,ranges))# 其余代码保持不变...