1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
/*
* Nfa2Dfa
* Convert a NFA to a DFA utilizing epsilon closure.
*/
// Compare two NfaStates for equality.
function StateCmp(a, b) {
if (a.id == b.id) {
return true
};
return false
};
// Compare two stacks filled with NfaStates for equality.
function NfaStackCmp(x, y) {
var b = true;
if (x.length != y.length) { return false }
for (var i=0; i < x.length; i++) {
b = b && StateCmp(x.get(i), y.get(i));
};
return b;
};
function Nfa2Dfa(nfa) {
this.startState = nfa.getStartState();
this.finalState = nfa.getFinalState();
}
// Accessor functions.
Nfa2Dfa.prototype.getStartState = function() { return this.startState; };
Nfa2Dfa.prototype.getFinalState = function() { return this.finalState; };
// Do conversion.
Nfa2Dfa.prototype.convert = function() {
var dfaStates = new Stack();
var q = new Stack();
q.push(this.getStartState());
var p = this.epsclosure(q)
var q = p.copy();
dfaStates.push(p);
var done = new Array();
var ds, j = 0;
while (!dfaStates.isEmpty()) {
ds = dfaStates.pop();
for (var i = 0; i < ALPHABET.length; i++) {
symbol = ALPHABET.substring(i, i+1);
var dsCopy = ds.copy();
next = this.epsclosure(this.move(symbol, ds));
ds = dsCopy;
var alreadyDone = false;
for (var k = 0; k < done.length; k++) {
if(NfaStackCmp(done[k], next)) {
alreadyDone = true;
break;
};
};
var dsStr = ds.str().replace(/ /g, '_');
if (!ttable[dsStr]) {
ttable[dsStr] = new Object();
if(dsStr.split('_').indexOf(''+this.getFinalState().id) >= 0) {
ttable[dsStr].isFinal = true;
} else {
ttable[dsStr].isFinal = false;
};
};
var nextStr = next.str().replace(/ /g, '_');
ttable[dsStr][symbol] = nextStr;
if (next.length > 0 && !alreadyDone) {
dfaStates.push(next);
};
};
done.push(ds);
j++;
};
};
// Reachable states over epsilon transitions.
Nfa2Dfa.prototype.epsclosure = function(q) {
var s, t, p = new Stack();
while(!q.isEmpty()) {
s = q.pop();
p.push(s);
if(s.symbol == EPSILON) {
for (var i = 0; i < 2; i++) {
t = s.getFollowUp(i);
if (t != null) {
q.push(t);
};
};
};
};
return p;
};
// Reachable states over transitions with symbol.
Nfa2Dfa.prototype.move = function(str, p) {
var s, q = new Stack();
while(!p.isEmpty()) {
s = p.pop();
s.mark(false);
if (s.symbol == str) {
s.getFollowUp(0).mark(true);
q.push(s.getFollowUp(0));
};
};
return q;
};
|
