some advancement

10 files changed, 319 insertions, 111 deletions

diff --git a/javascripts/; b/javascripts/;
deleted file mode 100644
index 958b6fd..0000000
--- a/javascripts/;
+++ /dev/null
@@ -1,32 +0,0 @@
-function RegexParser(str) {
-    this.str    = str;
-}
-
-RegexParser.prototype.parse = function() {
-    for (var i = 0; i < this.str.length; i++) {
-        switch(this.str[i]) {
-            case '(':
-                break;
-            case '|':
-                break;
-            case ')':
-                break
-            case '*':
-                break
-            
-            default:
-                //alert(this.str[i]);
-        }
-    };
-}
-
-
-function State() {
-
-}
-
-function Nfa {
-
-}
-
-
diff --git a/javascripts/Nfa.js b/javascripts/Nfa.js
new file mode 100644
index 0000000..1fd1991
--- /dev/null
+++ b/javascripts/Nfa.js
@@ -0,0 +1,56 @@
+/*
+ * Nfa
+ *
+ */
+function Nfa(symbol) {
+    this.startState;
+    this.acceptingState;
+
+    if (symbol) {
+        this.setStartState(new State(symbol));
+        this.setAcceptingState(new State(false));
+        this.getStartState().setFollowUp(0, this.getAcceptingState());
+    }
+}
+
+Nfa.prototype.getStartState     = function() { return this.startState }
+Nfa.prototype.setStartState     = function(s) { this.startState = s }
+Nfa.prototype.getAcceptingState = function() { return this.acceptingState }
+Nfa.prototype.setAcceptingState = function(s) { this.acceptingState = s }
+
+Nfa.prototype.concatenation = function(nfa) {
+    this.getAcceptingState().setFollowUp(0, nfa.getStartState());
+    this.setAcceptingState(nfa.getAcceptingState());
+    return this;
+}
+
+Nfa.prototype.union = function(nfa) {
+    var s = new State();
+    var t = new State();
+
+    s.setFollowUp(0, this.getStartState());
+    s.setFollowUp(1, nfa.getStartState());
+    
+    this.getAcceptingState().setFollowUp(0, t);
+    nfa.getAcceptingState().setFollowUp(0, t);
+    
+    this.setStartState(s);
+    this.setAcceptingState(t);
+}
+
+Nfa.prototype.star = function() {
+    var s = new State();
+    var t = new State();
+
+    s.setFollowUp(0, this.getStartState());
+    s.setFollowUp(1, t);
+
+    this.getAcceptingState().setFollowUp(0, this.getStartState());
+    this.getAcceptingState().setFollowUp(1, t);
+
+    this.setStartState(s);
+    this.setAcceptingState(t);
+
+    return this;
+}
+
diff --git a/javascripts/NfaSimulator.js b/javascripts/NfaSimulator.js
new file mode 100644
index 0000000..fd5677e
--- /dev/null
+++ b/javascripts/NfaSimulator.js
@@ -0,0 +1,77 @@
+/*
+ * NfaSimulator
+ *
+ */
+function NfaSimulator(nfa) {
+    this.q = new Queue;
+    this.p = new Queue;
+    this.startState = nfa.getStartState();
+    this.acceptingState = nfa.getAcceptingState();
+}
+
+NfaSimulator.prototype.getStartState = function() {
+    return this.startState;   
+}
+
+NfaSimulator.prototype.getAcceptingState = function() {
+    return this.acceptingState;
+}
+
+NfaSimulator.prototype.run = function(word) {
+    this.word = word;
+    this.str  = '';
+    this.accepted = false;
+    
+    this.getStartState().mark(true);
+    this.q.push(this.getStartState());
+
+    this.str += '$';
+    
+    for (var i = 0; i < word.length; i++) {
+        this.accepted = this.epsclosure();
+        this.str = this.word.substring(i, i+1);
+        this.move(this.str);
+    }
+
+    return accepted;
+}
+
+
+NfaSimulator.prototype.epsclosure = function() {
+    var s, t;
+    accepted = false;
+
+    while(!this.q.empty()) {
+        s = this.q.pop();
+        this.p.push(s);
+        accepted = accepted || s == this.getAcceptingState();
+
+        if(s.symbol == '&') {
+            for (var i = 0; i < 2; i++) {
+                t = s.getFollowUp(i);
+                if (t!=null) {
+                    if(!t.marked) {
+                        t.mark(true);
+                        this.q.push(t);
+                    }
+                }
+            }
+        }
+    }
+    return accepted;
+}
+
+
+NfaSimulator.prototype.move = function(str) {
+    var s;
+
+    while(!this.p.empty()) {
+        s = this.q.pop();
+        s.mark(false);
+        if (s.symbol == str) {
+            s.getFollowUp(0).mark(true);
+            this.q.push(s.getFollowUp(0));
+        }
+    }
+}
+
diff --git a/javascripts/Queue.js b/javascripts/Queue.js
new file mode 100644
index 0000000..795c433
--- /dev/null
+++ b/javascripts/Queue.js
@@ -0,0 +1,46 @@
+/*
+ * Item
+ *
+ */
+
+function Item() {
+    var obj;
+    var nxt;
+}
+
+
+/*
+ * Queue
+ *
+ */
+function Queue() {
+    var topItem;
+    var botItem;
+}
+
+Queue.prototype.empty = function() {
+    return this.topItem == null;
+}
+
+Queue.prototype.push = function(p) {
+    var b = new Item();
+
+    if (this.empty()) {
+        this.topItem = b;
+    } else {
+        this.botItem.next = b;
+    }
+    this.botItem = b;
+    this.botItem.obj = p;
+}
+
+
+Queue.prototype.pop = function() {
+    if (this.empty()) {
+        throw('Queue empty');
+    }
+    var b = this.topItem;
+    this.topItem = b.nxt;
+    return b.obj;
+}
+
diff --git a/javascripts/RegexParser.js b/javascripts/RegexParser.js
new file mode 100644
index 0000000..f2dd168
--- /dev/null
+++ b/javascripts/RegexParser.js
@@ -0,0 +1,108 @@
+/*
+ * RegexParser
+ *
+ */
+function RegexParser() {
+    this.alphabet         = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUWXYZ';
+    this.str = this.regex = '';
+    this.errorMessage     = 'Ok'
+    this.errorPosition    = -1;
+}
+
+
+RegexParser.prototype.lookahead = function() {
+    if (this.str.length > 0) {
+        return this.str.substring(0,1);
+    }
+    return '';
+}
+
+RegexParser.prototype.consume = function(symbol) {
+    this.str = this.str.substring(1);
+}
+
+RegexParser.prototype.trymatch = function(symbol) {
+    if (this.str.substring(0, 1) == symbol) {
+        this.consume(symbol);
+        return true;
+    }
+    return false;
+}
+
+RegexParser.prototype.match = function(symbol) {
+    if (!this.trymatch(symbol)) {
+        throw('Expected symbol '+symbol);
+    }
+}
+
+RegexParser.prototype.isLetter = function(symbol) {
+    return this.alphabet.indexOf(symbol) >= 0;
+}
+
+RegexParser.prototype.literal = function() {
+    var symbol = this.lookahead();
+    if(this.isLetter(symbol)) {
+        this.consume(symbol);
+        return new Nfa(symbol);
+    }
+    throw('Expected symbol or %.'); 
+}
+
+RegexParser.prototype.atom = function() {
+    if(this.trymatch('(')) {
+        var nfa = this.expr();
+        this.match(')');
+        return nfa;
+    }
+    return this.literal();
+}
+
+RegexParser.prototype.factor = function() {
+    return this.stars(this.atom());
+}
+
+RegexParser.prototype.stars = function(nfa) {
+    if (this.trymatch('*')) {
+        return this.stars(nfa.star());
+    }
+    return nfa;
+}
+
+RegexParser.prototype.term = function() {
+    var nfa = this.factor();
+    var symbol = this.lookahead();
+    if (this.isLetter(symbol) || (symbol == '(')) {
+        return nfa.concatenation(this.term());
+    }
+    return nfa;
+}
+
+RegexParser.prototype.expr = function() {
+    var nfa = this.term();
+    if (this.trymatch('|')) {
+        return nfa.union(this.expr());
+    }
+    return nfa;
+}
+
+RegexParser.prototype.parse = function(str) {
+    var nfa;
+    this.str = this.regex = str;
+
+    //try {
+        nfa = this.expr();
+        if(this.str.length>0) {
+            throw('Supernumerous symbols');
+        }
+    //} catch(e) {
+    //    this.errorMessage = e;
+    //    this.errorPosition = str.length - this.str.length;        
+    //    nfa = null;
+    //}
+    return nfa;
+}
+
+RegexParser.prototype.getRegex = function() { return this.regex }
+RegexParser.prototype.getErrorMessage = function() { return this.errorMessage }
+RegexParser.prototype.getErrorPosition = function() { return this.errorPosition }
+
diff --git a/javascripts/RegexVis.js b/javascripts/RegexVis.js
deleted file mode 100644
index c14f52f..0000000
--- a/javascripts/RegexVis.js
+++ /dev/null
@@ -1,77 +0,0 @@
-/*
- * RegexParser
- *
- */
-function RegexParser(str) {
-    this.str = str;
-}
-
-RegexParser.prototype.parse = function() {
-    for (var i = 0; i < this.str.length; i++) {
-        switch(this.str[i]) {
-            case '(':
-                break;
-            case '|':
-                break;
-            case ')':
-                break
-            case '*':
-                break
-            
-            default:
-                //alert(this.str[i]);
-        }
-    };
-}
-
-
-/*
- * State
- *
- */
-function State(symbol) {
-    if(!symbol) {
-        symbol = '#';
-    }
-    this.symbol    = symbol;
-    this.followUps = [];
-    this.marked    = false;
-}
-
-State.prototype.mark = function(b) {
-    this.marked = b;
-}
-
-State.prototype.setFollowUp = function(index, state) {
-    if (!((index == 0) || (index==1)) ) return;
-    this.followUps[index] = state;
-}
-
-
-/*
- * Nfa
- *
- */
-function Nfa(symbol) {
-    this.startState;
-    this.endState;
-    if (symbol) {
-        this.startState = new State(symbol);
-        this.endState   = new State(false);
-        this.startState.setFollowUp(0, this.endState);
-    }
-}
-
-Nfa.prototype.concatination = function(nfa) {
-    this.endState.setFollowUp(0, nfa);
-    this.endState = nfa.endState;
-}
-
-Nfa.prototype.union = function(nfa) {
-    var s0 = new State();
-    var s1 = new State();
-
-    s0.setFollowUp(0, );
-    s1.setFollowUp(1, );
-}
-
diff --git a/javascripts/State.js b/javascripts/State.js
new file mode 100644
index 0000000..75258e7
--- /dev/null
+++ b/javascripts/State.js
@@ -0,0 +1,20 @@
+/*
+ * State
+ *
+ */
+function State(symbol) {
+    if(!symbol) {
+        symbol = EPSILON;
+    }
+    this.symbol    = symbol;
+    this.followUps = [];
+    this.marked    = false;
+}
+
+State.prototype.mark = function(mark) { this.marked = mark }
+State.prototype.getFollowUp = function(index) { return this.followUps[index] }
+State.prototype.setFollowUp = function(index, state) {
+    if (!((index == 0) || (index==1)) ) return;
+    this.followUps[index] = state;
+}
+
diff --git a/javascripts/globals.js b/javascripts/globals.js
new file mode 100644
index 0000000..f48fd74
--- /dev/null
+++ b/javascripts/globals.js
@@ -0,0 +1,3 @@
+var EPSILON = '~';
+var DELIMITER = '$';
+
diff --git a/javascripts/init.js b/javascripts/init.js
deleted file mode 100644
index d405f2c..0000000
--- a/javascripts/init.js
+++ /dev/null
@@ -1,2 +0,0 @@
-var a = new RegexParser('(a|b)*');
-a.parse();
diff --git a/javascripts/run.js b/javascripts/run.js
new file mode 100644
index 0000000..35dd392
--- /dev/null
+++ b/javascripts/run.js
@@ -0,0 +1,9 @@
+// parse regular expression
+var parser = new RegexParser();
+var nfa    = parser.parse('(a|b)*');
+alert(parser.getErrorMessage());
+
+// simulate
+//var simulator = new NfaSimulator(nfa);
+//alert(simulator.run('aaaa'));
+