正则表达式的原理和实践

正则表达式学习与实践讲解人：冷荣秋引言：当今各种文本信息急剧增长，有固定格式的、没有固定格式的或者是在两者之间。有时由于应用的需要，有待对已有的数据进行计算机软件自动化信息提取或者人为地加工整理。面对海量的文本数据，可能要耗费许多人宝贵的时间，夜以继日地工作进行整理，期间可能还会产生无数的人为错误。而机器加工的好处就是只要它能够被正确的识别就不会产生误差，且速度也快的惊人。这就是强大的正则表达式所表现出来的神奇效果，我们对一部书本厚达2000多页的txt文本的牛津词典进行过加工，通过调试正则表达式代码来达到加工的目的，工作效率得以大幅度提升。正则表达式解释器主要有3部分组成，分别是解析、编译与执行。

正则表达式可以用来：验证字符串是否符合指定特征，比如验证是否是合法的邮件地址。用来查找字符串，从一个长的文本中查找符合指定特征的字符串，比查找固定字符串更加灵活方便。

用来替换，比普通的替换更强大。

非确定有穷自动机（NDFA）：

KenThompson利用非确定有穷自动机（NDFA）构造了正则表达式。NDFA是一个有向图，其每个节点代表一个状态，每条边用字母或符号（代表空字符串）标记。自动机有一个初始状态并可能有多个终止或接受状态。正则表达式匹配过程中使用了NDFA，如果在NDFA中，从初始状态到接受状态结束的路径上的字母能匹配文本中的每一个字符串，就表明找到了文本中的匹配。正则表达式定义如下：字母表中的所有字母均为正则表达式。若r和s是正则表达式，那么r|s、（r）、r*和rs也是正则表达式。正则表达式r|s代表正则表达式r或s。正则表达式r*（也称作克林闭包）代表r的任意有穷序列：r，rr，rrr，……..正则表达式rs代表r和s的连接。（r）代表正则表达式r。NDFA的构造过程:空字的构造方法。自动机由

-转移连接两个节点而组成。单字符a的构造方法，它与空词的构造方法类化，只不过转移是使用字符来标识，而不是空字符串。NDFA的构造过程(续):连接节点的构造法。两个子节点vl和vr对应的Thompson自动机合并，即第一个自动机和终止状态成为第二个自动机的初始状态。并节点的构造法：就像电路图中的并联一样，必须通过两个子节点对应的自动机vl和vr中的一个。这种构造需要-转移，在构造中，要添加二个状态，一个初始状态I，从它有二个-转移分别到Th(vl)和Th(vr)的初始状态；另一个是终止状态F，从自动机Th(vl)和Th(vr)的终止状态分别由-转移到达终止状态F。NDFA的构造过程(续):星节点的构造法：因为节点的唯一子节点v*可以被重复任意多次，所以需要创建一个从自动机Th(v*)的终止状态指向其初始状态的-转移。但是，星符号也意味着自动机Th(v*)也可能被忽略。因此，需要创建初始节点I和终结节点F，并用一个-转移将他们连接起来。另外，再创建两条-转移分别用来从节点I指向Th(v*)的初始状态以及从Th(v*)的终止状态指向F。如右图：有限状态机（FiniteAutomation）

状态机是一个有一组不同状态的集合的系统。有一个特殊状态――它描述了系统的初始状态。而其他的一个或多个状态为终止状态；当一个事件将我们带到这样的一些状态时，状态机将退出。状态是与转换相关联的，每个转换都标注有输入事件的名称。当事件发生时，我们将随着相关的转换从当前状态移动到新的状态。一个有限状态机包含一组状态集（states）、一个起始状态（startstate）、一组输入符号集（alphabet）、一个映射输入符号和当前状态到下一状态的转换函数（transitionfunction）的计算模型。当输入符号串，模型随即进入起始状态。它要改变到新的状态，依赖于转换函数。

假定一个输入符号(symbol)，可以得到2个或者2个以上的可能状态，那么这个finiteautomaton就是不确定的，反之就是确定的。有限状态机（FiniteAutomation）单个字符

两个状态的连接e1e2e?e1|e2e*e+不确定有限状态机（NFA）

例如要匹配abab|abbb,其NFA的状态是确定性有限状态机（DFA）

例如要匹配abab|abbb,其DFA的状态是NFA执行过程：abbb字符串的匹配过程如下：

一种高效的NFA执行过程：同步匹配两者

利用正则表达式来扫描要匹配的字符串，又由于此时是不确定状态机，所以利用试探与backing的方式来做匹配的。NFA是由正则来做驱动匹配的。这就像一个过程语言，控制了解析器在匹配中的try/fail。

DFA执行过程DFA与NFA不同，由于对于相应的输入都有一定的状态的迁移，所以总的来说，DFA的匹配效率要高一些。DFA是由字符串作驱动来匹配的，在每个字符串中的每个字符只被扫描一次。这种方式就是尝试此状态时可能的每种输入同时进行匹配。普通字符和元字符

：普通字符是那些表示自身的字符，例如从a到z，A到Z，0到9等；

元字符具有特殊意义，如‘.’，表示除了‘\n’外的所有字符，其他具有此功能的有

(元字符加‘\’转义):字符类

：单个的字符可以组成字符类，其语法为用’[’与’]’组成，例如[abcA-Z79]表示可以匹配a，b，c与A到Z，7，9的字符，其中’-’为连字符，表示字符的跨度。‘^’在”[]”间也是特殊字符，表示取反其他的特殊字符如右表：

限定符（重复）

：

限定符有2种形式，分别为’*’,’+’,’?’与’{’与’}’来表示在正则中有贪婪与非贪婪之分，默认的情况下，正则是贪婪的。非贪婪的2种方式：在原先的限定符加上’?’（/.+?/只将匹配"abdddd"中的第一个a

）；对软件的正则匹配功能进行设置

选择、分组和引用

：选择的语法就是设置’|’，如a|bc，那么要么a或bc都可以匹配，如果(a|b)c则为匹配ac或bc。如果我们在上例中设置了”()”，那么这就是分组，每个分组都可以被引用，如(a|b)c*(e|f)\1\2，\1与\2就是引用的语法，\1表示引用了(a|b)，\2表示引用(e|f)，依此类推。这里要说明的是(a|b)c*(e|f)\1\2与(a|b)c*(e|f)(a|b)(e|f)乍一看两者等同，但实际上，前一个不可以匹配acebf，而后一个可以。究其原因就是引用处的配平必须与被引用处一致，此例中与之匹配的可以是aceac。后向引用(补充)：后向引用用于重复搜索前面某个分组匹配的文本。后向引用中的括号中的表达式如下表：定位符(锚)

：如果正则表达式的匹配模式为MULTILINE模式，^可匹配一行文本的行首，$可匹配一行文本的行末。当\b被包含于字符集合中时，\b代表退格符（ASCII码=8）。断言：断言用于用于查找在某些内容(但并不包括这些内容，如下面几个式子中的括号中的内容)之前或之后的东西，当断言为真时才会继续进行匹配。exp1(?=exp2)正预测先行断言，exp1后面出现exp2。eg:\b\w+(?=ing\b)能匹配“I‘msingingwhileyou’redancing.”的sing和danc。exp1(?!exp2)：exp1后面不能出现exp2。例如：\b((?!abc)\w)+\b匹配不包含连续字符串abc的单词

(?<=exp1)exp2正回顾后行断言，exp2前面出现exp1。eg:(?<=\bre)\w+\b能匹配“readingabook”的ading。(?<!exp1)exp2：exp2前面不能出现exp1。(?<=exp1)exp2(?=exp3)两向断言,exp2前面出现exp1且后面出现exp3。eg:(?<=\s)\d+(?=\s)匹配以空白间隔的数字。(?<=<(\w+)>).*(?=<\/\1>)匹配不包含属性的简单HTML标签内里的内容。注释：小括号的另一种用途是通过语法(?#comment)来包含注释。eg：2[0-4]\d(?#200-249)|25[0-5](?#250-255)|[01]?\d\d?(?#0-199)。

要包含注释的话，最好是启用“忽略模式里的空白符”选项，这样在编写表达式时能任意的添加空格，Tab，换行，而实际使用时这些都将被忽略。启用这个选项后，在#后面到这一行结束的所有文本都将被当成注释忽略掉。eg:(?<= #断言要匹配的文本的前缀<(\w+)>#查找尖括号括起来的字母或数字(即HTML/XML标签)) #前缀结束.*#匹配任意文本(?=#断言要匹配的文本的后缀

<\/\1>#查找尖括号括起来的内容：前面是一个“/”，后面是先前捕获的标签)#后缀结束平衡组/递归匹配:有办法能让正则表达式匹配xx<aa<bbb><bbb>aa>yy

吗？语法构造：

(?'group')把捕获的内容命名为group,并压入堆栈(Stack)

(?‘-group’)从堆栈上弹出最后压入堆栈的名为group的捕获内容，如果堆栈本来为空，则本分组的匹配失败(?(group)yes|no)如果堆栈上存在以名为group的捕获内容的话，继续匹配yes部分的表达式，否则继续匹配no部分(?!)零宽负向先行断言，由于没有后缀表达式，试图匹配总是失败Eg：< #最外层的左括号[^<>]* #最外层的左括号后面的不是括号的内容(((?‘Open’<)