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

正则表达式解释器实现原理1以JavaScript正则为例Author:tuiye@  正则表达式可以用来:(1)验证字符串是否符合指定特征,比如验证是否是合法的邮件地址。(2)用来查找字符串,从一个长的文本中查找符合指定特征的字符串,比查找固定字符串更加灵活方便。(3)用来替换,比普通的替换更强大。对于一个正则表达式一般有2种方式,以JS为例其一为使用正则表达式文字常量:varre=/^[Jj]ava[Ss]cript/i;其二为使用RegExp构造函数:varre=newRegExp(“^[Jj]ava[Ss]cript”,”i”); 而一个正则表达式解释器主要有3部分组成,分别是解析(parse)、pile)与执行(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 数字字符/DD大写,可以匹配任何一个非数字字符/s可以匹配空格、制表符、换页符等空白字符的其中任意一个/SS大写,可以匹配任何一个空白字符以外的字符/w可以匹配任何一个字母或者数字或者下划线/WW大写,可以匹配任何一个字母或者数字或者下划线以外的字符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 定位符限定符特殊意义^匹配输入字符