diff options
Diffstat (limited to 'javascripts/Nfa2Dfa.js')
-rw-r--r-- | javascripts/Nfa2Dfa.js | 101 |
1 files changed, 39 insertions, 62 deletions
diff --git a/javascripts/Nfa2Dfa.js b/javascripts/Nfa2Dfa.js index cbdd766..0e889f8 100644 --- a/javascripts/Nfa2Dfa.js +++ b/javascripts/Nfa2Dfa.js @@ -2,31 +2,37 @@ * 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.acceptingState = nfa.getAcceptingState(); + this.startState = nfa.getStartState(); + this.finalState = nfa.getFinalState(); } -Nfa2Dfa.prototype.getStartState = function() { return this.startState } -Nfa2Dfa.prototype.getAcceptingState = function() { return this.acceptingState } +// +Nfa2Dfa.prototype.getStartState = function() { return this.startState; }; +Nfa2Dfa.prototype.getFinalState = function() { return this.finalState; }; -ttable = new Object(); +// +var ttable = new Object(); Nfa2Dfa.prototype.do = function() { var dfaStates = new Stack(); var q = new Stack(); @@ -34,12 +40,8 @@ Nfa2Dfa.prototype.do = function() { var p = this.epsclosure(q) var q = p.copy(); dfaStates.push(p); - document.write('S '+p.str()+'<br />'); - - var done = new Array(); - - //var ttable = new Object(); - + //document.write('S '+p.str()+'<br />'); + var done = new Array(); var ds = null; var j = 0; while (!dfaStates.isEmpty()) { @@ -56,39 +58,37 @@ Nfa2Dfa.prototype.do = function() { 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.getAcceptingState().id) >= 0) { + 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 />'); + //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; @@ -104,17 +104,16 @@ Nfa2Dfa.prototype.epsclosure = function(q) { 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()) { @@ -123,29 +122,7 @@ Nfa2Dfa.prototype.move = function(str, p) { if (s.symbol == str) { s.getFollowUp(0).mark(true); q.push(s.getFollowUp(0)); - } - } + }; + }; return q; -} - - -/* - * DfaStates - * - */ -function DfaState(nfaStates) { - this.nfaStates = nfaStates; - this.marked = false; -} - -DfaState.prototype.compare = function(b) { - -} - -DfaState.prototype.str = function() { - res = ''; - for (var i=0; i < this.nfaStates.length; i++) { - res += this.nfaStates[i].id + ' ' - } - return res -}
\ No newline at end of file +}; |