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

 正则表达式可以用来：

（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元字符

元数据如要表示自身，那么需要用’\’来辅助转义

B）字符类

单个的字符可以组成字符类，其语法为用’[’与’]’组成，例如[abcA-Z79]表示可以匹配a，b，c与A到Z，7，9的字符

其中’-’为连字符，表示字符的跨度。

‘^’在”[]”间也是特殊字符，表示取反

其他的特殊字符如下表：

表2字符类中的预定义字符类

Javascrīpt无POSIX格式

C）限定符（重复）

限定符有2种形式，分别为’*’,’+’,’?’与’ {’与’}’来表示

表3限定符

在正则中有贪婪与非贪婪之分，默认的情况下，正则是贪婪的

如果要把正则设置为非贪婪有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定位符