書接上文，上回說道NFA已經(jīng)可以完全描述正則語言的全部內(nèi)容。那么，我們在這一章探索一下一個(gè)比較復(fù)雜的正則表達(dá)式在用NFA做匹配的時(shí)候會有什么“不足“。

NFA匹配的"不足"

為了言之有物，不妨設(shè)要討論的模式為d?(c(a|b)*)*(b|c+)

圖1-1

效率

從上圖可以明確的看到存在大量的?轉(zhuǎn)換。這些?轉(zhuǎn)換在程序?qū)崿F(xiàn)的時(shí)候就對應(yīng)了大量的回溯入口，即決策點(diǎn)。那么很顯然，這個(gè)時(shí)候一定存在大量的遞歸回溯調(diào)用，自然也就必然會需要

大量時(shí)間來執(zhí)行。

?轉(zhuǎn)換冗余

究其原因，無非就是冗余狀態(tài)太多了

冗余 ≠ 無用

這些看似冗余的轉(zhuǎn)換實(shí)際上對分組捕獲非常有用,因?yàn)樵诜纸M捕獲時(shí)，這些回溯可以記錄當(dāng)前匹配的狀態(tài)還有剩余輸入信息等。但是，如果我們不用分組捕獲，只是要求模式全稱匹配，則這些轉(zhuǎn)換就是冗余的，我們需要通過狀態(tài)壓縮來實(shí)現(xiàn)確定化以避免任何回溯。

狀態(tài)壓縮

從上可知，若要完成狀態(tài)壓縮，則必須消除這些?轉(zhuǎn)換。但是，如何完成這一算法呢？完成后的確定化的結(jié)果仍然自動機(jī)么？當(dāng)然是，并且它有個(gè)與NFA對應(yīng)的名字叫做DFA。

DFA登場

DFA與NFA的區(qū)別

從圖1-1與圖1-2中可以明顯的發(fā)現(xiàn)NFA和DFA在轉(zhuǎn)換邊上的差異,歸納為下表。

	NFA	DFA
?轉(zhuǎn)換	存在	不存在
相同輸入，不同轉(zhuǎn)換	存在	不存在

?轉(zhuǎn)換

closure---克林閉包

消除?轉(zhuǎn)換

function cleenClosure(){// BFSlet espilonSet = [state];let queue = [state];while(queue.length > 0){let q = queue.shift();for(const st of q.epsilonTransitions){if(espilonSet.findIndex(val => st.label === val.label) === -1){queue.push(st);espilonSet.push(st)if(st.isEnd) state.isEnd = st.isEnd}}}return espilonSet; }

Subset-Construction(子集構(gòu)造）

借助上文的消除?轉(zhuǎn)換函數(shù)，我們可以將能夠通過?轉(zhuǎn)換到達(dá)的相連節(jié)點(diǎn)劃分為新DFA的等價(jià)狀態(tài)。

function toDFA(exp) {// 輸入字符集let aplhabets = new Set();// 原始正則表達(dá)式for(const ch of exp){if(ch !== "(" && ch !== "." && ch !== "?" && ch !== ")" && ch !== "*" && ch !== "|") {aplhabets.add(ch)}}const transExp = insertExplicitConcatOperator(exp);// 經(jīng)過后綴改寫的正則表達(dá)式，后綴改寫目的在于解決運(yùn)算符的優(yōu)先級確定const postfixExp = toPostfix(transExp);let nfa = toNFA(postfixExp);//1. 從初始狀態(tài)開始，進(jìn)行下一狀態(tài)等價(jià)集合的構(gòu)造let q0 = createDFAState(false);q0.nfaStateSet = epsilonCleen(nfa.start);q0.isEnd = nfa.start.isEnd;//2. 存儲新發(fā)現(xiàn)等價(jià)狀態(tài)的工作集let workLst = new Array();//3. 存儲已經(jīng)生成等價(jià)狀態(tài)的集合let dfaStates = [q0];workLst.push(q0);//4. 不停增加和刪除等價(jià)狀態(tài)，知道workLst變?yōu)榭占痺hile(workLst.length > 0){let q = workLst.shift();for(const ch of aplhabets) {// 4.1 計(jì)算delta并合并進(jìn)入新狀態(tài)t = epsilonCleenDelta(q,ch);if(t != null) {if(!dfaStatesHas(dfaStates,t)){dfaStates.push(t);workLst.push(t);q.transitions[ch] = t} else {let node = dfaStatesFind(dfaStates,t);node.isEnd = t.isEnd;q.transitions[ch] = node;}}}}return q0; }

圖1-2

總結(jié)

以上是生活随笔為你收集整理的nfa状态转换图正规式_0x02 从NFA到DFA的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。