blob: 0e889f8120c73fb53604e9ec121e8a597d1477db (
plain)
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
119
120
121
122
123
124
125
126
127
128
|
/*
* Nfa2Dfa
*
*/
//
function StateCmp(a, b) {
if (a.id == b.id) {
return true
};
return false
};
//
function NfaStackCmp(x, y) {
var ret = true;
if (x.length != y.length) { return false }
for (var i=0; i < x.length; i++) {
ret = ret && StateCmp(x.get(i), y.get(i));
};
return ret;
};
//
function Nfa2Dfa(nfa) {
this.startState = nfa.getStartState();
this.finalState = nfa.getFinalState();
}
//
Nfa2Dfa.prototype.getStartState = function() { return this.startState; };
Nfa2Dfa.prototype.getFinalState = function() { return this.finalState; };
//
var ttable = new Object();
Nfa2Dfa.prototype.do = 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);
//document.write('S '+p.str()+'<br />');
var done = new Array();
var ds = null;
var j = 0;
while (!dfaStates.isEmpty()) {
ds = dfaStates.pop();
for (var i = 0; i < ALPHABET.length; i++) {
a = ALPHABET.substring(i, i+1);
var ds2 = ds.copy();
x = this.epsclosure(this.move(a, ds));
ds = ds2;
var adone = false;
for (var w=0; w < done.length; w++) {
if(NfaStackCmp(done[w], x)) {
adone = true;
break;
};
};
var q = ds.str().replace(/ /g, '_');
var qq = x.str().replace(/ /g, '_');
if (!ttable[q]) {
ttable[q] = new Object();
if(q.split('_').indexOf(''+this.getFinalState().id) >= 0) {
ttable[q].isFinal = true;
} else {
ttable[q].isFinal = false;
};
};
ttable[q][a] = qq;
if (x.length > 0 && !adone) {
for (var h=0; h < j; h++) {
//document.write("\t");
};
//document.write(a+' '+x.str()+'<br />');
dfaStates.push(x);
};
};
done.push(ds);
j++;
};
};
//
Nfa2Dfa.prototype.epsclosure = function(q) {
var s = null;
var t = null;
var 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;
};
//
Nfa2Dfa.prototype.move = function(str, p) {
var s = null;
var 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;
};
|
