1. 概述
本章介绍正则表达式的规范和正则表达式的识别算法,其中包含非确定状态自动机的构造。需要用到前置知识有向图。
2. 正则表达式介绍
2.1. 含义
正则表达式是一种描述某种模式的字符串。通常可以用于子字符串查找中检查匹配以及检查输入的合法性等。
2.2. 形式
我们此处的正则表达式,它由3种基本操作和操作数构成。
1.连接操作:例如AB,就是A和B连接起来。
2.或操作:例如A|B,指{A,B},代指其中一个。
3.包闭操作:指模式的部分可以多次重复任意次数。使用*标记。例如A*B代表0个或者多个A和一个B连接的模式。
4.括号:不属于操作,只改变优先级。
5.空字符是:$\epsilon$
例子:
正则表达式 | 匹配字符串 |
---|---|
A(B|C)*D | AD ABD ACD ABCDD |
缩略写法:
我们可以用’.’来代表任意字符,包含在方括号中的一系列字符代表其中任意一个。这一系列字符可以用一个范围来表示,如果开头为’^’,则表示不是方括号中的字符中的任意一个。并且支持转义序列,以及指定重复序列:’+’号代表至少重复一次,’?’号代表重复0或1次,用写在’{}’中的数字代表重复次数。
例子:
正则表达式 | 原始写法 | 匹配字符串 |
---|---|---|
(AB)+ | (AB)(AB)* | AB ABABAB |
(AB)? | $\epsilon$|AB | $\epsilon$ AB |
(AB){3} | (AB)(AB)(AB) | ABABAB |
(AB){1-2} | (AB)|(AB)(AB) | AB ABAB |
3. 正则表达式识别
3.1. 非确定有限状态自动机(NFA)
这种自动机和上个博客的DFA有很大相同之处,但我们现在使用结点来储存字符了,其他与DFA的特征大致相同,但是这里不确定其转换方式是否是解所需的转换,因为有例如’|’的存在,我们在某个结点可能会有一种随机性的转换,可以说每次转换是一个随机过程。
如下图:
对于上图中的红色边对应的转换不需要匹配就能发生,称为空转换($\epsilon$-转换),黑色的边对应的转换是字符匹配就可以发生。我们对于匹配的字符只需要利用模式储存的字符串的顺序储存结构就可以达成,而空转换边可以用有向图来完成。
那么问题来了,如何解决这种随机过程?我们只需要暴力遍历所有可能性即可。对于初始状态,我们使用dfs
就可以得到所有空转换能达到的点,和第一个文本字符对比,有符合就把其对应的下一个模式结点加入待dfs
的集合中,然后再对这些符合的字符使用dfs
,不断重复,并把符合匹配结点加入结果集合中,不断更新之,如果最后其中有结束的状态,则找到。
3.2. 代码实现
1 | class NFA |
3.3 性质
1. 对于构造模式长度为$M$的正则表达式的DFA,最坏情况下与M成正比。
2. 对于对应正则表达式长度为$M$的DFA,识别长度为$N$的文本最坏情况下时间与$MN$成正比。