一． 簡介

    該正則表達式暫時能識別 *,|,(,)等特殊符號，如(a|b)*abc。不過擴展到其他符號（如?）也相對比較容易，修改NFA中的構(gòu)建規(guī)則即可。

二． 引擎的構(gòu)建

    該正則表達式引擎的構(gòu)建以《Compilers Principles,Techniques & Tools》3.7節(jié)為依據(jù)，暫時只能識別*,|,(,)這幾個特殊的字符，其工作過程為：構(gòu)建NFA -> 根據(jù)NFA構(gòu)建DFA -> 用DFA匹配。

1. 構(gòu)建NFA
該NFA的構(gòu)建以2條基本規(guī)則和3條組合規(guī)則為基礎(chǔ)，采用歸納的思想構(gòu)建而成。
1）2條基本的規(guī)則是:
a. 以一個空值ε構(gòu)建一個NFA

b. 以一個字符a構(gòu)建一個NFA

2) 3條組合規(guī)則是：
a. r = s | t （其中s和t都是NFA）

b. r = s t（其中s和t都是NFA）

c. r = s *（其中s為NFA）

3) 如果需要識別如”?”等特殊符號，則可再加一些組合規(guī)則。

在具體的程序中，可以以下面的BNF為結(jié)構(gòu)來實現(xiàn)。（具體見源程序regexp.cpp）


2. 構(gòu)建DFA
主要是求ε閉包的過程，從一個集合的ε閉包轉(zhuǎn)移到一個集合的ε閉包。
以a*c為例，其NFA圖如下所示（用dot畫的）

為例:
起始結(jié)點3的ε閉包集為 A = {3,1,4}
A遇上字母a的轉(zhuǎn)移為MOV(A,a) = { 2 }，其ε閉包集為B = { 2,1,4 }
A遇上字母c的轉(zhuǎn)移為MOV(A,c) = { 6 }，其ε閉包集為B = { 6 }
同理可求出其他轉(zhuǎn)移集合，最后得到的DFA如下所示:

3. 匹配
每匹配成功一個字符則DFA移動到下個相應(yīng)的結(jié)點。

三． 改進

1. 如龍書中所說，有時候模擬NFA而不是直接構(gòu)建DFA可能達到更好的效果。
2. 每次匹配不成功都需要回溯，這個地方也可以借鑒KMP算法（不過KMP對此好像有點不適用）
3. 其他改進方法可以看看《柔性字符串匹配》和龍書《Compilers Principles,Techniques & Tools》3.7節(jié)。

四． 代碼下載

svn checkout http://regexp.googlecode.com/svn/trunk/ regexp-read-only

或 regexp.rar