算法的具體說明可以看
這里。
今天花了一個晚上完成并測試了從NFA到DFA的代碼。NFA到DFA的主要過程就是構造出一個等價于NFA的狀態機，使得從任何一個狀態出去的狀態轉換都不具有相同的條件。這個約束就是“確定性”的含義，給定一個狀態和一個輸入，最多只能跳轉到一個目標狀態。于是知道了這個過程，代碼就很好寫了：
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狀態的所有等價NFA狀態進行遍歷
16 const IReadonlyList<State*>& nfaStates=dfaStateMap[currentState];
17 for(int j=0;j<nfaStates.Count();j++)
18 {
19 State* nfaState=nfaStates[j];
20 //對每一個NFA狀態的所有轉換進行遍歷
21 for(int k=0;k<nfaState->transitions.Count();k++)
22 {
23 Transition* nfaTransition=nfaState->transitions[k];
24 //檢查該NFA轉換類型是否已經具有已經被記錄
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 //不存在則創建一個轉換類型
36 if(transitionClass==0)
37 {
38 transitionClass=nfaTransition;
39 }
40 //注冊轉換
41 nfaTransitions.Add(transitionClass, nfaTransition);
42 }
43 }
44
45 //遍歷所有種類的NFA轉換
46 for(int j=0;j<nfaTransitions.Count();j++)
47 {
48 const IReadonlyList<Transition*>& transitionSet=nfaTransitions.GetByIndex(j);
49 //對所有轉換的NFA目標狀態集合進行排序
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 //判斷轉換類的所有轉換的NFA目標狀態組成的集合是否已經有一個對應的DFA狀態
60 State* dfaState=0;
61 for(int k=0;k<dfaStateMap.Count();k++)
62 {
63 //將DFA的等價NFA狀態集合進行排序
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 //不存在等價DFA狀態則創建一個
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 //將該轉換復制到新狀態機里
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作為數據結構來計算。Group是一個多對多映射，也就是說Group<K, V>的內部結構等價于Map<K, List<V>>。從NFA到DFA轉換的同時，這個函數還記錄了每一個DFA對象所對應的NFA對象集合。
接下來就要分兩步走了，第一個先做純匹配的正則表達式，然后接著做貪婪匹配（包含捕獲、預查和指向捕獲的匹配等高級功能）。根據Vczh Library++2.0的經驗，純匹配的正則表達式用來實現詞法分析器的時候，不亞于純手寫的詞法分析器，這一點令他的應用范圍變廣。
posted on 2009-11-03 08:34
陳梓瀚(vczh) 閱讀(2748)
評論(8) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事