From ec3f1801c258dbba07dfccbd9864f9b2de0bfae6 Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Thu, 13 May 2010 03:19:48 +0200 Subject: some advancement --- javascripts/; | 32 ------------- javascripts/Nfa.js | 56 +++++++++++++++++++++++ javascripts/NfaSimulator.js | 77 +++++++++++++++++++++++++++++++ javascripts/Queue.js | 46 +++++++++++++++++++ javascripts/RegexParser.js | 108 ++++++++++++++++++++++++++++++++++++++++++++ javascripts/RegexVis.js | 77 ------------------------------- javascripts/State.js | 20 ++++++++ javascripts/globals.js | 3 ++ javascripts/init.js | 2 - javascripts/run.js | 9 ++++ regexvis.html | 12 +++-- 11 files changed, 328 insertions(+), 114 deletions(-) delete mode 100644 javascripts/; create mode 100644 javascripts/Nfa.js create mode 100644 javascripts/NfaSimulator.js create mode 100644 javascripts/Queue.js create mode 100644 javascripts/RegexParser.js delete mode 100644 javascripts/RegexVis.js create mode 100644 javascripts/State.js create mode 100644 javascripts/globals.js delete mode 100644 javascripts/init.js create mode 100644 javascripts/run.js 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 @@ - + RegexVis - - + + + + + + + + -- cgit v1.2.3