summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPatrick Simianer <p@simianer.de>2010-05-13 03:19:48 +0200
committerPatrick Simianer <p@simianer.de>2010-05-13 03:19:48 +0200
commitec3f1801c258dbba07dfccbd9864f9b2de0bfae6 (patch)
tree95397dc4e009ddd8c6e5a361e9d0df9e06bff1d6
parent072e9069333ce9fdf7f575b5f9fd54277a76912f (diff)
some advancement
-rw-r--r--javascripts/;32
-rw-r--r--javascripts/Nfa.js56
-rw-r--r--javascripts/NfaSimulator.js77
-rw-r--r--javascripts/Queue.js46
-rw-r--r--javascripts/RegexParser.js108
-rw-r--r--javascripts/RegexVis.js77
-rw-r--r--javascripts/State.js20
-rw-r--r--javascripts/globals.js3
-rw-r--r--javascripts/init.js2
-rw-r--r--javascripts/run.js9
-rw-r--r--regexvis.html12
11 files changed, 328 insertions, 114 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'));
+
diff --git a/regexvis.html b/regexvis.html
index f68ac53..40be644 100644
--- a/regexvis.html
+++ b/regexvis.html
@@ -3,15 +3,21 @@
<head>
<!-- 2010-05-07 -->
<meta http-equiv='Content-Type' content='text/html; charset=utf-8' />
- <meta http-equiv='Content-Language' content='de_DE' />
+ <meta http-equiv='Content-Language' content='en_EN' />
<meta name='author' content='Patrick Simianer' />
<title>RegexVis</title>
<link rel='stylesheet' type='text/css' href='stylesheets/RegexVis.css' />
- <script type='text/javascript' src='javascripts/RegexVis.js'></script>
- <script type='text/javascript' src='javascripts/init.js'></script>
+ <script type='text/javascript' src='javascripts/globals.js'></script>
+ <script type='text/javascript' src='javascripts/Queue.js'></script>
+ <script type='text/javascript' src='javascripts/State.js'></script>
+ <script type='text/javascript' src='javascripts/Nfa.js'></script>
+ <script type='text/javascript' src='javascripts/RegexParser.js'></script>
+ <script type='text/javascript' src='javascripts/NfaSimulator.js'></script>
+
+ <script type='text/javascript' src='javascripts/run.js'></script>
</head>
<body>