[Algorithm] 有限状态机实现正则表达式: NFA DFA (ZT)

最近在写语法分析东西。遇到了不是难题，也学到了不是东西。和大家分享一下

 

1.语法分析最笨的办法就是对应位置的对应关键字匹配（模式匹配），这个东西最简单，也最容易实现，这个就是所谓的穷举发。

 

今天我肯定不是来和大家说模式匹配，这个也没有必要说。

 

今天，最成熟的语法分析利器还要算正则表达式了，用户只需要些一些简单的语法，就可以匹配和分析出自己需要的东西。

但是，没有几人知道正则表达式的实现原理（在搜索的时候，基本没有发现将实现原理的）。

 

在大学时代，只要你是学计算机的，应该知道有一门课叫编译原理的，主要就是将语法分析的（我自己也些过几次语法分析器，但时间太久了，全都忘了），我就猜测，正则表达式的实现原理是不是有限状态机。

我查看c和java的源代码，发现他的解析器就是采用的有限状态机实现。

 

所以我在网上找到一篇很不错的文章：

 

正则表达式可以用来：

（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字符串的匹配过程如下：

 

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

 

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

 

       2）DFA

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

 

4 实践

见JS 1.6与PCRE7.2

 

1）JS1.6

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

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

       建立的节点的同时，会调整节点间的关系，主要是ProcessOp()这个函数，调整的关系为两种：一种是OP_CONCAT（连接），另一种为OP_ALT（选择）。OP_CONCAT是指两个OP_FLAT的RENode节点，例如’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_ALT，OP_BACKREF，OP_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
.*		True
.*	x h t t t p p s	True
…	…	…
.*		False
h		False
…	…	…
h		False（则回朔）
h		True
t		True
…	…	…
t		False（则回朔）
p		True
p		True
Done	s	True

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

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

 

2）PCRE7.2

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

PCRE的解析与编译是合而为一的，也就是说，解析编译后生成的OPCODE即为最终的NFA。这里NFA与JS1.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

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

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

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

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

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