一． 簡介

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

二． 引擎的構建

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

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

b. 以一個字符a構建一個NFA

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

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

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

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

在具體的程序中，可以以下面的BNF為結構來實現。（具體見源程序regexp.cpp）


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

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

3. 匹配
每匹配成功一個字符則DFA移動到下個相應的結點。

三． 改進

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

四． 代碼下載

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

或 regexp.rar