算法的具体说明可以看
这里。
今天花了一个晚上完成并测试了从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) 阅读(2712)
评论(8) 编辑 收藏 引用 所属分类:
VL++3.0开发纪事