（转）正则表达式解释器实现原理

转自：http://blog.csdn.net/qipnx/archive/2007/10/22/1836596.aspx

正则表达式可以用来：

（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 被包含于字符集合