一．
簡介 該正則表達式暫時能識別 *,|,(,)等特殊符號，如(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）
r -> r '|' s | r
s -> s t | s
t -> a '*' | a
a -> token | '(' r ')' | ε
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
posted on 2010-06-17 20:50
hex108 閱讀(730)
評論(2) 編輯 收藏 引用 所屬分類:
Program