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

时间:2022-07-25 15:57:33

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普通字符和元字符

普通字符是那些表示自身的字符,例如从azAZ09等;

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

 

1 元字符

元字符

特殊意义

^

匹配输入字符串的开始位置。要匹配 "^" 字符本身,请使用 "/^"

$

匹配输入字符串的结尾位置。要匹配 "$" 字符本身,请使用 "/$"

.

匹配除了换行符(/n)以外的任意一个字符。要匹配小数点本身,请使用 "/."

*

修饰匹配次数为 0 次或任意次。要匹配 "*" 字符本身,请使用 "/*"

+

修饰匹配次数为至少 1 次。要匹配 “+” 字符本身,请使用 “/+”

?

修饰匹配次数为 0 次或 1 次。要匹配 “?” 字符本身,请使用 “/?”

=

用于前向引用或向后引用

!

用于前向引用或向后引用

:

用于前向引用或向后引用

|

用于前向引用或向后引用

/

转义用

/

用于前向引用或向后引用

()

标记一个子表达式的开始和结束位置。要匹配小括号,请使用 “/(“ “/)”

[]

用来自定义能够匹配多种字符的表达式。要匹配中括号,请使用 “/[“ “/]”

{}

修饰匹配次数的符号。要匹配大括号,请使用 “/{“ “/}”

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

 

B)字符类

单个的字符可以组成字符类,其语法为用’[’’]’组成,例如[abcA-Z79]表示可以匹配abcAZ79的字符

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

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

其他的特殊字符如下表:

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

预定义字符类

特殊意义

^

在紧跟’[’表示取反,表示自身要转义

-

在字符间,表示连字符,如要表示自身,须紧接在’[’’[^’之后

.

小数点可以匹配除了换行符(/n)以外的任意一个字符

/d

可以匹配任何一个 0~9 数字字符

/D

D大写,可以匹配任何一个非数字字符

/s

可以匹配空格、制表符、换页符等空白字符的其中任意一个

/S

S大写,可以匹配任何一个空白字符以外的字符

/w

可以匹配任何一个字母或者数字或者下划线

/W

W大写,可以匹配任何一个字母或者数字或者下划线以外的字符

JavaScriptPOSIX格式

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,那么要么abc都可以匹配,如果(a|b)c则为匹配acbc

如果我们在上例中设置了”()”,那么这就是分组,每个分组都可以被引用,如(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 anchorJavaScript不支持)

前向引用使用(?=)表示正的前向引用,(?!)表示负的前向引用下面是一个前向引用的例子 /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的状态机。

下面介绍下在流行的两种算法NFANondeterministic Finite Automaton)与DFADeterministic Finite automaton),PerlPythonJS等都是NFA的,而awkgrep等用的是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 执行

       1NFA

那么一个abbb字符串的匹配过程如下:

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

一个更加高效的方式是同步匹配两者:

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

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

 

       2DFA

而确定性状态机相反,由于对于相应的输入都有一定的状态的迁移,所以总的来说,DFA的匹配效率要高一些。DFA是由字符串作驱动来匹配的,在每个字符串中的每个字符只被扫描一次。这种方式就是尝试此状态时可能的每种输入同时进行匹配。

 

4 实践

JS 1.6PCRE7.2

 

1JS1.6

       /.*ht*p{0,3}/ 为例来说明JS1.6PCRE7.2NFA组成

       JS1.6中,基本上以一个字符(广义上的字符,比如/n我们认为是回车字符)以一个节点建立RENode。比如例子中,我们建立了7RENode,依次为’.’,’*’,’h’,’t’,’*’,’p’,” {0, 3}”。其中’h’,’t’,’p’分别为REOP_FLAT,而’*’,”{0,3}”REOP_QUANT(RE_STAR)

       建立的节点的同时,会调整节点间的关系,主要是ProcessOp()这个函数,调整的关系为两种:一种是OP_CONCAT(连接),另一种为OP_ALT(选择)。OP_CONCAT是指两个OP_FLATRENode节点,例如’h’’t’是紧挨的,那么我们把他们处理成“连接”关系。“连接”关系一种顺序关系。至于OP_ALT,则额外建立一个OP_ALT节点把两则建立起选择的关系。例如a|b,那么,建立OP_ALT节点,把节点’a’’b’与节点OP_ALT建立选择关系。

解析后RENode节点顺序如下图

*

0

4

.

ENDCHILD

FLAT

h

*

0

5

FLAT

t

END

CHILD

QUANT

0

3

0

5

FLAT1

P

END

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

JS1.6中编译的过程就为生成NFA的过程,主要是调整生成OP_ALTOP_BACKREFOP_STAR等跳转关系

编译后,生成NFA

(注:此例中上下行为父子关系)

REOP_STAR

REOP_FLAT1

REOP_STAR

REOP_QUANT

REOP_DOT ’.’

‘h’

REOP_FLAT ’t’

REOP_FLAT ‘p’

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

       执行(匹配)的过程,我们以匹配字符串”xhtttpps”

匹配中的OPCODE

匹配中的匹配位置与状态

成功与否

Start(保存,MatchBack用)

|x h t t t p p s

 

|

|x h t t t p p s

 

.*

<x h t t t p p s

True

.*

x h t t t p p s

True

.*

<x h t t t p p s|

False

h

<x h t t t p p s|

False

h

<x h |t t t p p s

False(则回朔)

h

<x |h t t t p p s

True

                     t                    

<x h |t t t p p s

True

t

<x h t t t |p p s

False(则回朔)

p

<x h t t t |p p s

True

p

<x h t t t p |p s

True

Done

<x h t t t p p> s

True

注:其中’|’代表匹配所在的位置,’<’代表匹配成功开始,’>’代表匹配成功结束。

所以上述正则可匹配上述字符串中的”xhtttpp”

 

2PCRE7.2

/ht*p{0,2}/为例

PCRE的解析与编译是合而为一的,也就是说,解析编译后生成的OPCODE即为最终的NFA。这里NFAJS1.6中的NFA是形式是一样的,当然细节上有区别。因此其匹配的过程也是相似。

当然PCRE也提供理论部分的DFA作为其状态机。(待续)

以上的正则解析编译后的以如下格式存在。

OP

BRA

0

11

OP

CHAR

h

OP

STAR

t

OP

UPTO

0

2

p

OP

KET

0

11

OP

END

由于其NFAJS有一致性,这里不再重复,倒是其Match时的一个消递归的方式比较不错,下面来做一个小的说明。

       基本思想是这样的,因为我们递归的时候每次都要保存一些变量与“栈”上,这样过多的嵌套就会引起很大的变量于“栈”上,而且由于某些操作系统对“栈”的大小是有限制的,这就在一定的时候会引起“栈”溢出,从而到时程序运行问题,常见的就是Crash

       一般比较常用的消递归的方式主要有2种,其一是无限循环,其二就是自己从“堆”上保存自己的变量。这里用了第二种方式。

       以函数直接调用自身这种方式来说明。那么在此函数中定有一处或几处是调用到自身的,在调用自身处,在“堆”上分配出空间frame,用于保存当前的变量的值,并把当前frame压入自己的frame栈(数据结构中的栈,与上面提到的“栈”不同),并且在此设定一个label(标签,用于RETURN时候的goto到此用)。并且goto至函数的入口处,此时犹如一个函数的新调用,而且可以减少调用函数的开销。

       当函数执行完(比如匹配不成功,需要回退;或者subpattern执行完毕)时候,我们需要做“返回”。返回前,我们必须保存执行到此时的一个“结果”,如函数的返回值类似。然后就是取出要返回的label的位置,用goto到那里,把当前的frame销毁,继续执行上一步中未完成的部分。大体上就是这样。