失眠网 > 【模式串匹配】正则表达式与正则表达式匹配

【模式串匹配】正则表达式与正则表达式匹配

时间：2023-02-06 05:55:36

正则表达式是理论计算机科学和形式语言理论中的一个基本概念，由美国数学家Stephen Cole Kleene提出。

正则表达式定义

正则表达式 (Regular Expression) 是符合正则文法的字符串, 它由三种基本的操作符(连接操作符“·”、选择操作符“|”‘、重复操作符“*”’）进行递归定义而成。正则表达式的形式化定义如下:

正则表达式：定义在符号集合Σ∪{ϵ,⋅,∣,∗,(,)}\Sigma \cup\{\epsilon, \cdot, \mid, *,(,)\}Σ∪{ϵ,⋅,∣,∗,(,)}的字符串, 递归定义如下: 空字符 ϵ\epsilonϵ 是正则表达式。任意字符 a∈Σa \in \Sigmaa∈Σ 是正则表达式;如果 r1r_{1}r1 和 r2r_{2}r2 都是正则表达式, 则 (r1)、(r1⋅r2)、(r1∣r2)\left(r_{1}\right) 、\left(r_{1} \cdot r_{2}\right) 、\left(r_{1} \mid r_{2}\right)(r1)、(r1⋅r2)、(r1∣r2) 和 (r1∗)\left(r_{1} *\right)(r1∗) 亦是正则表达式。

正则表达式的语言

正则表达式表示有穷或无穷多个字符串的集合, 具有比精确字符串更强大的描述能力。称正则表达式表示的字符串集合为正则表达式的语言。正则表达式 rrr 的语言用 L(r)L(r)L(r) 表示, 定义如下:

正则表达式的语言: 正则表达式 rrr 所表示的语言 L(r)L(r)L(r) 是字母表 Σ\SigmaΣ 上的字符串的集合。根据正则表达式 rrr 的结构, 递归定义如下: 如果 r=ϵr=\epsilonr=ϵ, 则 L(r)={ϵ}L(r)=\{\epsilon\}L(r)={ϵ}, 即 rrr 表示空字符串。如果 r=a（a∈Σ)r=a （ a \in \Sigma)r=a（a∈Σ), 则 L(r)={a}L(r)=\{a\}L(r)={a}, 即 rrr 表示一个长度为 1 的字符串 “ aaa ”。如果 rrr 是 (r1)\left(r_{1}\right)(r1) 这种形式, 则 L(r)=L(r1)L(r)=L\left(r_{1}\right)L(r)=L(r1) 。如果 rrr 是 (r1⋅r2)\left(r_{1} \cdot r_{2}\right)(r1⋅r2) 这种形式, 则 L(r)={w1w2∣w1∈L(r1),w2∈L(r2)}L(r)=\left\{w_{1} w_{2} \mid w_{1} \in L\left(r_{1}\right), w_{2} \in L\left(r_{2}\right)\right\}L(r)={w1w2∣w1∈L(r1),w2∈L(r2)} 。其中 w1w2w_{1} w_{2}w1w2 表示由字符串 w1w_{1}w1 和 w2w_{2}w2 连接而成的字符串。“·”被称为链接操作符。如果 rrr 是 (r1∣r2)\left(r_{1} \mid r_{2}\right)(r1∣r2) 这种形式, 则 L(r)=L(r1)∪L(r2)L(r)=L\left(r_{1}\right) \cup L\left(r_{2}\right)L(r)=L(r1)∪L(r2) 。“|”被称为选择操作符。如果 rrr 是 (r1∗)\left(r_{1} *\right)(r1∗) 这种形式, 则 L(r)={w1w2⋯wk∣k≥0,wi∈L(r1),1≤i≤k}L(r)=\left\{w_{1} w_{2} \cdots w_{k} \mid k \geq 0, w_{i} \in L\left(r_{1}\right), 1 \leq i \leq k\right\}L(r)={w1w2⋯wk∣k≥0,wi∈L(r1),1≤i≤k} “*” 被称为重复操作符。

正则表达是匹配

单正则表达式匹配：给定正则表达式 rrr, 对于任意的输入文本 T=t1t2⋯tnT=t_{1} t_{2} \cdots t_{n}T=t1t2⋯tn, 找出 L(r)L(r)L(r) 中的字符串在文本 TTT 中的出现位置，即: occur⁡(r,T)={(i,j)∣t[i,⋯,j]∈L(r)}\operatorname{occur}(r, T)=\{(i, j) \mid t[i, \cdots, j] \in L(r)\}occur(r,T)={(i,j)∣t[i,⋯,j]∈L(r)} 。多正则表达式匹配：给定正则表达式集合 R={r1,r2,⋯,rK}R=\left\{r_{1}, r_{2}, \cdots, r_{K}\right\}R={r1,r2,⋯,rK} ，对于任意的输入文本 T=t1t2⋯tnT=t_{1} t_{2} \cdots t_{n}T=t1t2⋯tn, 找出 L(rk)(1≤k≤K)L\left(r_{k}\right)(1 \leq k \leq K)L(rk)(1≤k≤K) 中的字符串在文本 TTT 中的出现位置, 即: occur⁡(R,T)={(i,j,k)∣t[i,⋯,j]∈L(rk),rk∈R}\operatorname{occur}(R, T)=\left\{(i, j, k) \mid t[i, \cdots, j] \in L\left(r_{k}\right), r_{k} \in R\right\}occur(R,T)={(i,j,k)∣t[i,⋯,j]∈L(rk),rk∈R} 。

需要特别说明的是, 正则表达式匹配 (Regular Expression Matching), 也称正则表达式搜索 (Regular Expression Searching), 它与正则表达式识别 (Regular Expression Recognizing）有显著的不同。

正则表达式匹配是在输入文本 TTT 中搜索所有属于 L(r)L(r)L(r) 的子串t[i,⋯,j]t[i, \cdots, j]t[i,⋯,j],而正则表达式识别是指: 给定正则表达式 rrr, 对于任意的输入文本 TTT, 判断 T∈L(r)T \in L(r)T∈L(r) 或 T∉L(r)T \notin L(r)T∈/L(r) 。

正则表达式的描述能力

正则表达式描述能力强，语法灵活，能够表达更加精确和丰富的过滤规则。在语法能力上，正则表达式的描述能力最强，布尔表达式次之，精确字符串的描述能力最弱。这三种规则表示方法的语法能力具有包含的关系：

精确字符串规则类 ⊂\subset⊂ 布尔表达式规则类 ⊂\subset⊂ 正则表达式规则类

正则表达式匹配的基本理论

正则表达式的研究已经有几十年的历史，根据自动机和计算理论，正则表达式具有与自动机等价的计算能力，因此正则表达式匹配主要依靠有限状态自动机来完成。有限状态自动机分为两类：一类是非确定型有限自动机（Nondeterministic Finite Automaton，简称NFA），另外一类是确定型有限自动机（Deterministic Finite Automaton，简称DFA）。NFA和DFA的区别在于：对于确定的状态和确定的输入，NFA有多个后继状态，而DFA则只有唯一的后继状态。NFA、DFA和正则表达式在计算能力上是等价的。

补充知识：什么是状态自动机？参考：/p/47434856
状态机是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。先来解释什么是“状态”（ State ）。现实事物是有不同状态的，例如一个自动门，就有 open 和 closed 两种状态。我们通常所说的状态机是有限状态机，也就是被描述的事物的状态的数量是有限个，例如自动门的状态就是两个 open 和 closed 。状态机，也就是 State Machine ，不是指一台实际机器，而是指一个数学模型。说白了，一般就是指一张状态转换图。例如，根据自动门的运行规则，我们可以抽象出下面这么一个图。
自动门有两个状态，open 和 closed ，closed 状态下，如果读取开门信号，那么状态就会切换为 open 。open 状态下如果读取关门信号，状态就会切换为 closed 。状态机的全称是有限状态自动机，自动两个字也是包含重要含义的。给定一个状态机，同时给定它的当前状态以及输入，那么输出状态时可以明确的运算出来的。例如对于自动门，给定初始状态 closed ，给定输入“开门”，那么下一个状态时可以运算出来的。

NFA 非确定型自动机

五元组 <Q,Σ,δ:Q×Σ∪{ϵ}↦2Q,q0,F><Q, \Sigma, \delta: Q \times \Sigma \cup\{\epsilon\} \mapsto 2^{Q}, q_{0}, F><Q,Σ,δ:Q×Σ∪{ϵ}↦2Q,q0,F>

Q为限状态集合;Σ\SigmaΣ 为字母表 (也称字符集);δ\deltaδ 为状态转移函数，对于任意的输入字符 c∈Σc \in \Sigmac∈Σ, 状态转移函数将当前状态映射到唯一的后继状态;q0q_{0}q0 为初始状态;FFF 为终止 (接受) 状态集合, 是状态集合 QQQ 的子集。

DFA 确定型自动机

五元组 <Q,Σ,δ:Q×Σ↦Q,q0,F><Q, \Sigma, \delta: Q \times \Sigma \mapsto Q, q_{0}, F><Q,Σ,δ:Q×Σ↦Q,q0,F>

DFA与NFA的区别：

对于字母表的每个符号表示形式，DFA 中只有一个状态转换。NFA 无需指定根据某些符号做出反应。DFA 不能使用空字符串转换。 NFA 可以使用空字符串转换。DFA可以理解为一台机器。 NFA可以理解为同时计算的多台小型机器DFA 明确设置下一个可能的状态。 NFA 中，每对状态和输入符号可以具有许多可能的后续状态。DFA更难构建。NFA更容易构建。如果字符串终止的状态与接受状态不同，则 DFA 将拒绝该字符串。 NFA 在所有分支死亡或拒绝字符串的情况下拒绝字符串。执行输入字符串所需的时间更少。执行输入字符串所需的时间更多。所有DFA都是NFA。并非所有NFA都是DFA。DFA 需要更多空间。NFA 需要的空间比 DFA 少。DFA δ：QxΣ -> Q 即下一个可能的状态属于 Q。 NFA δ：QxΣ -> 2^Q 即下一个可能状态属于 Q 的幂集。