正则表达式解释器实现原理1 以JavaScript正则为例 Author:tuiye@126.com 正则表达式可以用来：

（1）验证字符串是否符合指定特征，比如验证是否是合法的邮件地址。 （2）用来查找字符串，从一个长的文本中查找符合指定特征的字符串，比查找固定字符串更加灵活方便。 （3）用来替换，比普通的替换更强大。 对于一个正则表达式一般有2种方式，以JS为例 其一为使用正则表达式文字常量： var re = /^[Jj]ava[Ss]cript/i; 其二为使用RegExp构造函数： var re = new RegExp(“^[Jj]ava[Ss]cript”,”i”);

而一个正则表达式解释器主要有3部分组成，分别是解析（parse）、编译（compile）与执行（execute）。

1 解析 正则的表达式的词法与语法比较简单，基本语法如下： A）普通字符和元字符 普通字符是那些表示自身的字符，例如从a到z，A到Z，0到9等； 元字符具有特殊意义，如‘.’，表示除了‘/n’外的所有字符，其他具有此功能的有

表1 元字符 元字符 特殊意义

^ 匹配输入字符串的开始位置。要匹配 "^" 字符本身，请使用 "/^" $ 匹配输入字符串的结尾位置。要匹配 "$" 字符本身，请使用 "/$" . 匹配除了换行符（/n）以外的任意一个字符。要匹配小数点本身，请使用 "/." * 修饰匹配次数为 0 次或任意次。要匹配 "*" 字符本身，请使用 "/*" + 修饰匹配次数为至少 1 次。要匹配“+” 字符本身，请使用 “/+” ? 修饰匹配次数为 0 次或 1 次。要匹配 “?” 字符本身，请使用 “/?” = 用于前向引用或向后引用 ! 用于前向引用或向后引用 : 用于前向引用或向后引用 | 用于前向引用或向后引用 / 转义用 / 用于前向引用或向后引用 () 标记一个子表达式的开始和结束位置。要匹配小括号，请使用 “/(“和 “/)” [] 用来自定义能够匹配 „多种字符‟的表达式。要匹配中括号，请使用“/[“ 和 “/]” {} 修饰匹配次数的符号。要匹配大括号，请使用 “/{“ 和 “/}” 元数据如要表示自身，那么需要用‟/‟来辅助转义

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

^ 在紧跟‟[‟表示取反，表示自身要

转义 - 在字符间，表示连字符，如要表

示自身，须紧接在‟[‟或‟[^‟之后 . 小数点可以匹配除了换行符（/n）

以外的任意一个字符 /d 可以匹配任何一个 0~9 数字字

符 /D D大写，可以匹配任何一个非数

字字符 /s 可以匹配空格、制表符、换页符

等空白字符的其中任意一个 /S S大写，可以匹配任何一个空白

字符以外的字符 /w 可以匹配任何一个字母或者数

字或者下划线 /W W大写，可以匹配任何一个字母

或者数字或者下划线以外的字符 JavaScript无POSIX格式 C）限定符（重复） 限定符有2种形式，分别为‟*‟,‟+‟,‟?‟与‟ {‟与‟}‟来表示

表3 限定符 限定符 特殊意义

* 表达式尽可能的多匹配，最少可

以不匹配，相当于 {0, } + 表达式尽可能的多匹配，至少匹

配1次，相当于 {1, } ? 表达式尽可能匹配1次，也可以

不匹配，相当于 {0, 1} {m,n} 表达式尽可能重复n次，至少重

复m次："ba{1,3}"可以匹配"ba"或"baa"或"baaa" {m} 表达式固定重m次，比如：

"/w{2}" 相当于 "/w/w" {m,} 表达式尽可能的多匹配，至少重

复m次："/w/d{2,}"可以匹配"a12","x456"...

在正则中有贪婪与非贪婪之分，默认的情况下，正则是贪婪的 如果要把正则设置为非贪婪有2种方式，一种为设置在原先的限定符加上‟?‟就行，另一种在设置 举例说明，/.+/ 将匹配"abdddd"中的所有字符，/.+?/ 只将匹配"abdddd"中的第一个a，也就是默认的尽可能多的匹配字符，而非贪婪重复则尽可能上的匹配。

D）选择、分组和引用 选择的语法就是设置‟|‟，如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。

E）定位符(锚)和前向引用 定位符如下表所示

表4 定位符 限定符 特殊意义

^ 匹配输入字符串的开始位置。要匹配 "^" 字符本身 $ 匹配输入字符串的结尾位置。要匹配 "$" 字符本身 ? 表达式尽可能匹配1次，也可以

不匹配，相当于 {0, 1} /b 匹配单词边界，例如一个/w和

/W的位置，或者一个/w与字符串的开始和结尾的位置 /B 和上面的想法，匹配一个非单词

边界 如果正则表达式的匹配模式为 MULTILINE 模式，^ 可匹配一行文本的行首，$ 可匹配一行文本的行末。当 /b 被包含于字符集合中时，/b 代表退格符（ASCII码 = 8）。 除了这些预定义的定位符，还可以自定义定位符，这种类型的定位符叫做前向引用(look-ahead anchor)和后向引用(look-behind anchor，JavaScript不支持)。 前向引用使用(?=„)表示正的前向引用，(?!„)表示负的前向引用下面是一个前向引用的例子/Java(?!Script)([A-Z]/w*)/ 其中(?!Script)匹配后面不跟Script的位置，而(?＝Script)匹配后面是Script的位置。

以上讲解了JavaScript的语法规则，下面我们来论述一下解析的过程。 解析的过程是语法分析（Lexical Analysis）与词法分析（Grammar Analysis）。

2 编译 编译（Compile）阶段，主要的工作就是生成字节流（Emit Byte Code）。而生成Byte Code的算法（规则）JS中就是NFA。生成的Byte Code是归于执行（Execute）时做匹配利用。各个状态即为正则中的语义（OPCODE）的表示，各个OPCODE以一定的格式与关系住成了状态机，JS中是组成NFA的状态机。 下面介绍下在流行的两种算法NFA（Nondeterministic Finite Automaton）与DFA（Deterministic Finite automaton），Perl，Python，JS等都是NFA的，而awk与grep等用的是DFA，两种算法的具体实现如下： 1）有限状态机（Finite Automation） 状态机是一个有一组不同状态的集合的系统。有一个特殊状态――它描述了系统的初始状态。而其他的一个或多个状态为终止状态；当一个事件将我们带到这样的一些状态时，状态机将退出。状态是与转换相关联的，每个转换都标注有输入事件的名称。当事件发生时，我们将随着相关的转换从当前状态移动到新的状态。 一个有限状态机包含一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）、一个映射输入符号和当前状态到下一状态的转换函数（transition function）的计算模型。当输入符号串，模型随即进入起始状态。它要改变到新的状态，依赖于转换函数。 假定一个输入符号(symbol)，可以得到2个或者2个以上的可能状态，那么这个finite automaton就是不确定的，反之就是确定的。 一个正则可以与一个FA等同，其转化的规律如下 对于单个字符的 两个状态的连接e1e2 对于e?

对于e1|e2 对于e* 对于e+ 2）不确定有限状态机（NFA） 例如要匹配abab|abbb,其NFA的状态是

3）确定性有限状态机（DFA） 以上例子的DFA如下

其中s1-s10为各个的状态对应于NFA中的s1-s10 3 执行 1）NFA 那么一个abbb字符串的匹配过程如下：