summaryrefslogtreecommitdiff
path: root/javascripts/Nfa2Dfa.js
diff options
context:
space:
mode:
Diffstat (limited to 'javascripts/Nfa2Dfa.js')
-rw-r--r--javascripts/Nfa2Dfa.js101
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
+};