算法的具體說明可以看
這里。
今天花了一個(gè)晚上完成并測試了從NFA到DFA的代碼。NFA到DFA的主要過程就是構(gòu)造出一個(gè)等價(jià)于NFA的狀態(tài)機(jī)，使得從任何一個(gè)狀態(tài)出去的狀態(tài)轉(zhuǎn)換都不具有相同的條件。這個(gè)約束就是“確定性”的含義，給定一個(gè)狀態(tài)和一個(gè)輸入，最多只能跳轉(zhuǎn)到一個(gè)目標(biāo)狀態(tài)。于是知道了這個(gè)過程，代碼就很好寫了：
1 Automaton::Ref NfaToDfa(Automaton::Ref source, IGroup<State*, State*>& dfaStateMap)
2 {
3 Automaton::Ref target=new Automaton;
4 Group<Transition*, Transition*> nfaTransitions;
5 CopyFrom(target->captureNames.Wrap(), source->captureNames.Wrap());
6 State* startState=target->NewState();
7 target->startState=startState;
8 dfaStateMap.Add(startState, source->startState);
9
10 for(int i=0;i<target->states.Count();i++)
11 {
12 State* currentState=target->states[i].Obj();
13 nfaTransitions.Clear();
14
15 //對該DFA狀態(tài)的所有等價(jià)NFA狀態(tài)進(jìn)行遍歷
16 const IReadonlyList<State*>& nfaStates=dfaStateMap[currentState];
17 for(int j=0;j<nfaStates.Count();j++)
18 {
19 State* nfaState=nfaStates[j];
20 //對每一個(gè)NFA狀態(tài)的所有轉(zhuǎn)換進(jìn)行遍歷
21 for(int k=0;k<nfaState->transitions.Count();k++)
22 {
23 Transition* nfaTransition=nfaState->transitions[k];
24 //檢查該NFA轉(zhuǎn)換類型是否已經(jīng)具有已經(jīng)被記錄
25 Transition* transitionClass=0;
26 for(int l=0;l<nfaTransitions.Keys().Count();l++)
27 {
28 Transition* key=nfaTransitions.Keys()[l];
29 if(AreEqual(key, nfaTransition))
30 {
31 transitionClass=key;
32 break;
33 }
34 }
35 //不存在則創(chuàng)建一個(gè)轉(zhuǎn)換類型
36 if(transitionClass==0)
37 {
38 transitionClass=nfaTransition;
39 }
40 //注冊轉(zhuǎn)換
41 nfaTransitions.Add(transitionClass, nfaTransition);
42 }
43 }
44
45 //遍歷所有種類的NFA轉(zhuǎn)換
46 for(int j=0;j<nfaTransitions.Count();j++)
47 {
48 const IReadonlyList<Transition*>& transitionSet=nfaTransitions.GetByIndex(j);
49 //對所有轉(zhuǎn)換的NFA目標(biāo)狀態(tài)集合進(jìn)行排序
50 SortedList<State*> transitionTargets;
51 for(int l=0;l<transitionSet.Count();l++)
52 {
53 State* nfaState=transitionSet[l]->target;
54 if(!transitionTargets.Contains(nfaState))
55 {
56 transitionTargets.Add(nfaState);
57 }
58 }
59 //判斷轉(zhuǎn)換類的所有轉(zhuǎn)換的NFA目標(biāo)狀態(tài)組成的集合是否已經(jīng)有一個(gè)對應(yīng)的DFA狀態(tài)
60 State* dfaState=0;
61 for(int k=0;k<dfaStateMap.Count();k++)
62 {
63 //將DFA的等價(jià)NFA狀態(tài)集合進(jìn)行排序
64 SortedList<State*> relativeStates;
65 CopyFrom(relativeStates.Wrap(), dfaStateMap.GetByIndex(k));
66 //比較兩者是否相等
67 if(relativeStates.Count()==transitionTargets.Count())
68 {
69 bool equal=true;
70 for(int l=0;l<relativeStates.Count();l++)
71 {
72 if(relativeStates[l]!=transitionTargets[l])
73 {
74 equal=false;
75 break;
76 }
77 }
78 if(equal)
79 {
80 dfaState=dfaStateMap.Keys()[k];
81 break;
82 }
83 }
84 }
85 //不存在等價(jià)DFA狀態(tài)則創(chuàng)建一個(gè)
86 if(!dfaState)
87 {
88 dfaState=target->NewState();
89 for(int k=0;k<transitionTargets.Count();k++)
90 {
91 dfaStateMap.Add(dfaState, transitionTargets[k]);
92 if(transitionTargets[k]->finalState)
93 {
94 dfaState->finalState=true;
95 }
96 }
97 }
98 //將該轉(zhuǎn)換復(fù)制到新狀態(tài)機(jī)里
99 Transition* transitionClass=nfaTransitions.Keys()[j];
100 Transition* newTransition=target->NewTransition(currentState, dfaState);
101 newTransition->capture=transitionClass->capture;
102 newTransition->index=transitionClass->index;
103 newTransition->range=transitionClass->range;
104 newTransition->type=transitionClass->type;
105 }
106 }
107
108 return target;
109 }
這里頻繁使用了Group和IGroup作為數(shù)據(jù)結(jié)構(gòu)來計(jì)算。Group是一個(gè)多對多映射，也就是說Group<K, V>的內(nèi)部結(jié)構(gòu)等價(jià)于Map<K, List<V>>。從NFA到DFA轉(zhuǎn)換的同時(shí)，這個(gè)函數(shù)還記錄了每一個(gè)DFA對象所對應(yīng)的NFA對象集合。
接下來就要分兩步走了，第一個(gè)先做純匹配的正則表達(dá)式，然后接著做貪婪匹配（包含捕獲、預(yù)查和指向捕獲的匹配等高級功能）。根據(jù)Vczh Library++2.0的經(jīng)驗(yàn)，純匹配的正則表達(dá)式用來實(shí)現(xiàn)詞法分析器的時(shí)候，不亞于純手寫的詞法分析器，這一點(diǎn)令他的應(yīng)用范圍變廣。
posted on 2009-11-03 08:34
陳梓瀚(vczh) 閱讀(2748)
評論(8) 編輯 收藏 引用 所屬分類:
VL++3.0開發(fā)紀(jì)事