From 3d9e4d9737fdb534b07638ff5d47b0e74922fe7b Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Sun, 23 May 2010 04:29:05 +0200 Subject: implemented labels, arrow heads and began animation; things a little slower now --- javascripts/Nfa.js | 10 +++--- javascripts/Nfa2Dfa.js | 80 +++++++++++++++++++------------------------- javascripts/NfaSimulator.js | 9 ++--- javascripts/NfaState.js | 5 +-- javascripts/RegexParser.js | 30 +++++++++-------- javascripts/Stack.js | 14 ++++---- javascripts/globals.js | 4 +++ javascripts/graph.js | 57 ++++++++++++++++++++++++------- javascripts/uifunc.js | 56 ++++++++++++++++++++++++------- regexvis.html | 4 +-- resources/raphael.png | Bin 0 -> 8091 bytes resources/urls.txt | 7 ++++ 12 files changed, 170 insertions(+), 106 deletions(-) create mode 100644 resources/raphael.png diff --git a/javascripts/Nfa.js b/javascripts/Nfa.js index 2edc4b7..a214700 100644 --- a/javascripts/Nfa.js +++ b/javascripts/Nfa.js @@ -1,6 +1,6 @@ /* * Nfa - * + * NFA consisting of several NfaStates, following Thompson's algorithm. */ function Nfa(symbol) { this.startState = null; @@ -13,13 +13,13 @@ function Nfa(symbol) { }; }; -// +// Accessor functions. Nfa.prototype.getStartState = function() { return this.startState; }; Nfa.prototype.setStartState = function(s) { this.startState = s; }; Nfa.prototype.getFinalState = function() { return this.finalState; }; Nfa.prototype.setFinalState = function(s) { this.finalState = s; }; -// +// Concatenations: ab Nfa.prototype.concat = function(nfa) { this.getFinalState().setFollowUp(0, nfa.getStartState()); this.setFinalState(nfa.getFinalState()); @@ -27,7 +27,7 @@ Nfa.prototype.concat = function(nfa) { return this; }; -// +// Union: (a|b) Nfa.prototype.union = function(nfa) { var s = new NfaState(); var t = new NfaState(); @@ -44,7 +44,7 @@ Nfa.prototype.union = function(nfa) { return this; }; -// +// Kleene Star: a* Nfa.prototype.kleene = function() { var s = new NfaState(); var t = new NfaState(); diff --git a/javascripts/Nfa2Dfa.js b/javascripts/Nfa2Dfa.js index 0e889f8..f38b2cf 100644 --- a/javascripts/Nfa2Dfa.js +++ b/javascripts/Nfa2Dfa.js @@ -1,9 +1,9 @@ /* * Nfa2Dfa - * + * Convert a NFA to a DFA utilizing epsilon closure. */ -// +// Compare two NfaStates for equality. function StateCmp(a, b) { if (a.id == b.id) { return true @@ -11,28 +11,26 @@ function StateCmp(a, b) { return false }; -// +// Compare two stacks filled with NfaStates for euqality. function NfaStackCmp(x, y) { - var ret = true; + var b = 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)); + b = b && StateCmp(x.get(i), y.get(i)); }; - return ret; + return b; }; -// function Nfa2Dfa(nfa) { this.startState = nfa.getStartState(); this.finalState = nfa.getFinalState(); } -// +// Accessor functions. Nfa2Dfa.prototype.getStartState = function() { return this.startState; }; Nfa2Dfa.prototype.getFinalState = function() { return this.finalState; }; -// -var ttable = new Object(); +// Do conversion. Nfa2Dfa.prototype.do = function() { var dfaStates = new Stack(); var q = new Stack(); @@ -40,47 +38,41 @@ Nfa2Dfa.prototype.do = function() { var p = this.epsclosure(q) var q = p.copy(); dfaStates.push(p); - //document.write('S '+p.str()+'
'); + var done = new Array(); - var ds = null; - var j = 0; + var ds, j = 0; while (!dfaStates.isEmpty()) { ds = dfaStates.pop(); for (var i = 0; i < ALPHABET.length; i++) { - a = ALPHABET.substring(i, i+1); - var ds2 = ds.copy(); - x = this.epsclosure(this.move(a, ds)); - ds = ds2; + symbol = ALPHABET.substring(i, i+1); + var dsCopy = ds.copy(); + next = this.epsclosure(this.move(symbol, ds)); + ds = dsCopy; - var adone = false; - for (var w=0; w < done.length; w++) { - if(NfaStackCmp(done[w], x)) { - adone = true; + var alreadyDone = false; + for (var k = 0; k < done.length; k++) { + if(NfaStackCmp(done[k], next)) { + alreadyDone = 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.getFinalState().id) >= 0) { - ttable[q].isFinal = true; + var dsStr = ds.str().replace(/ /g, '_'); + if (!ttable[dsStr]) { + ttable[dsStr] = new Object(); + if(dsStr.split('_').indexOf(''+this.getFinalState().id) >= 0) { + ttable[dsStr].isFinal = true; } else { - ttable[q].isFinal = false; + ttable[dsStr].isFinal = false; }; }; - ttable[q][a] = qq; + var nextStr = next.str().replace(/ /g, '_'); + ttable[dsStr][symbol] = nextStr; - if (x.length > 0 && !adone) { - for (var h=0; h < j; h++) { - //document.write("\t"); - }; - //document.write(a+' '+x.str()+'
'); - dfaStates.push(x); + if (next.length > 0 && !alreadyDone) { + dfaStates.push(next); }; }; done.push(ds); @@ -88,12 +80,9 @@ Nfa2Dfa.prototype.do = function() { }; }; -// +// Reachable states over epsilon transitions. Nfa2Dfa.prototype.epsclosure = function(q) { - var s = null; - var t = null; - - var p = new Stack(); + var s, t, p = new Stack(); while(!q.isEmpty()) { s = q.pop(); @@ -102,7 +91,7 @@ Nfa2Dfa.prototype.epsclosure = function(q) { if(s.symbol == EPSILON) { for (var i = 0; i < 2; i++) { t = s.getFollowUp(i); - if (t!=null) { + if (t != null) { q.push(t); }; }; @@ -111,11 +100,10 @@ Nfa2Dfa.prototype.epsclosure = function(q) { return p; }; -// +// Reachable states over transitions with symbol. Nfa2Dfa.prototype.move = function(str, p) { - var s = null; - var q = new Stack(); - + var s, q = new Stack(); + while(!p.isEmpty()) { s = p.pop(); s.mark(false); diff --git a/javascripts/NfaSimulator.js b/javascripts/NfaSimulator.js index 0c29914..c5a035f 100644 --- a/javascripts/NfaSimulator.js +++ b/javascripts/NfaSimulator.js @@ -1,16 +1,17 @@ /* * NfaSimulator - * + * Simulate a NFA with a word. Check if regular expression produces word. */ function NfaSimulator(nfa) { this.startState = nfa.getStartState(); this.finalState = nfa.getFinalState(); }; +// Accessor functions. NfaSimulator.prototype.getStartState = function() { return this.startState; }; NfaSimulator.prototype.getFinalState = function() { return this.finalState; }; -// +// Main simulate function. NfaSimulator.prototype.simulate = function(word) { var a, accepted = false; this.p = new Stack(); @@ -26,7 +27,7 @@ NfaSimulator.prototype.simulate = function(word) { return accepted; }; -// +// Get reachable states through epsilon transitions. NfaSimulator.prototype.epsclosure = function() { var s, t, accepted = false; @@ -50,7 +51,7 @@ NfaSimulator.prototype.epsclosure = function() { return accepted; }; -// +// Get reachable states through transitions with symbol. NfaSimulator.prototype.move = function(symbol) { var s; diff --git a/javascripts/NfaState.js b/javascripts/NfaState.js index 2de256d..4291295 100644 --- a/javascripts/NfaState.js +++ b/javascripts/NfaState.js @@ -1,6 +1,6 @@ /* - * State - * + * NfaState + * Represents a state of a NFA (following Thompson's algorithm). */ function NfaState(symbol) { if(!symbol) { @@ -13,6 +13,7 @@ function NfaState(symbol) { this.id = NEXTSTATE++; }; +// Accessor functions. NfaState.prototype.mark = function(bool) { this.marked = bool; }; NfaState.prototype.getFollowUp = function(index) { return this.followUps[index]; }; NfaState.prototype.setFollowUp = function(index, state) { diff --git a/javascripts/RegexParser.js b/javascripts/RegexParser.js index 3abe426..42251af 100644 --- a/javascripts/RegexParser.js +++ b/javascripts/RegexParser.js @@ -1,14 +1,16 @@ /* * RegexParser - * + * Parsing a regular expression using recursive descent method. + * parse() returns a NFA (constructed following Thompson's algrotihm). */ function RegexParser() {}; +// Accessor functions RegexParser.prototype.getRegex = function() { return this.regex; }; RegexParser.prototype.getErrorMessage = function() { return this.errorMessage; }; RegexParser.prototype.getErrorPosition = function() { return this.errorPosition; }; -// +// Next symbol in regex. RegexParser.prototype.lookahead = function() { if (this.str.length > 0) { return this.str.substring(0, 1); @@ -16,12 +18,12 @@ RegexParser.prototype.lookahead = function() { return ''; }; -// +// Removing the firstmost symbol of regex. RegexParser.prototype.consume = function(symbol) { this.str = this.str.substring(1); }; -// +// Check if symbol matches expected symbol. RegexParser.prototype.trymatch = function(symbol) { if (this.str.substring(0, symbol.length) == symbol) { this.consume(symbol); @@ -30,14 +32,14 @@ RegexParser.prototype.trymatch = function(symbol) { return false; }; -// +// See above. RegexParser.prototype.match = function(symbol) { if (!this.trymatch(symbol)) { throw("RegexParser.match(): Expected symbol '"+symbol+"'."); }; }; -// +// Checks if a symbol is in set of symbols. RegexParser.prototype.isIn = function(symbol, set) { if (symbol.length > 0) { return set.indexOf(symbol) >= 0; @@ -45,12 +47,12 @@ RegexParser.prototype.isIn = function(symbol, set) { return false; }; -// +// See above. Set = alphabet. RegexParser.prototype.isLetter = function(symbol) { return this.isIn(symbol, ALPHABET); }; -// +// Is symbol a literal? RegexParser.prototype.literal = function() { var symbol = this.lookahead(); if(this.isLetter(symbol)) { @@ -60,7 +62,7 @@ RegexParser.prototype.literal = function() { throw("RegexParser.literal(): Expected a letter or '"+EMPTYSYMBOL+"'."); }; -// +// Atomar expression. RegexParser.prototype.atom = function() { if(this.trymatch('(')) { var nfa = this.expr(); @@ -70,12 +72,12 @@ RegexParser.prototype.atom = function() { return this.literal(); }; -// +// Factor. RegexParser.prototype.factor = function() { return this.star(this.atom()); }; -// +// Kleene Star. RegexParser.prototype.star = function(nfa) { if (this.trymatch('*')) { return this.star(nfa.kleene()); @@ -83,7 +85,7 @@ RegexParser.prototype.star = function(nfa) { return nfa; }; -// +// Term. RegexParser.prototype.term = function() { var nfa = this.factor(); var symbol = this.lookahead(); @@ -93,7 +95,7 @@ RegexParser.prototype.term = function() { return nfa; }; -// +// Expression. RegexParser.prototype.expr = function() { var nfa = this.term(); if (this.trymatch('|')) { @@ -102,7 +104,7 @@ RegexParser.prototype.expr = function() { return nfa; }; -// +// Parse function. var nfa; RegexParser.prototype.parse = function(regex) { this.str = regex; diff --git a/javascripts/Stack.js b/javascripts/Stack.js index c4e2db9..4ccd74e 100644 --- a/javascripts/Stack.js +++ b/javascripts/Stack.js @@ -1,19 +1,19 @@ /* * Stack - * + * Simple implementation of a stack using Array(). */ function Stack() { this.a = new Array(); this.length = 0; }; -// +// Push an item. Stack.prototype.push = function(obj) { this.a.push(obj); this.length++; }; -// +// Pop an item. Stack.prototype.pop = function() { if (this.isEmpty()) { throw('Stack.pop(): Pop from empty stack.'); @@ -22,7 +22,7 @@ Stack.prototype.pop = function() { return this.a.pop(); }; -// +// Check if stack is empty. Stack.prototype.isEmpty = function() { if (this.length == 0) { return true; @@ -30,12 +30,12 @@ Stack.prototype.isEmpty = function() { return false; }; -// +// Get an item at position index. Stack.prototype.get = function(index) { return this.a[index]; }; -// +// Deep copy a stack. Stack.prototype.copy = function() { var c = ((new Array()).concat(this.a)); var ret = new Stack(); @@ -44,7 +44,7 @@ Stack.prototype.copy = function() { return ret; }; -// +// String representation. Stack.prototype.str = function(separator) { if (!separator) { separator=' ' }; var a = new Array(); diff --git a/javascripts/globals.js b/javascripts/globals.js index 88d5b2a..e8668b8 100644 --- a/javascripts/globals.js +++ b/javascripts/globals.js @@ -3,4 +3,8 @@ var EPSILON = '~'; var NEXTSTATE = 0; var EMPTYSYMBOL = '%'; var ALPHABET = 'abc'+EMPTYSYMBOL; +var ALPHABETS = ALPHABET+'()|*'; var REDELIMITER = '$'; + +var ttable = new Object(); +var g; diff --git a/javascripts/graph.js b/javascripts/graph.js index c1460f2..1d7d17d 100644 --- a/javascripts/graph.js +++ b/javascripts/graph.js @@ -1,5 +1,5 @@ -// spurce: http://raphaeljs.com/graffle.html -Raphael.fn.connection = function (obj1, obj2, line, bg, strokeColor) { +// source: http://raphaeljs.com/graffle.html (extended with labels and arrow heads) +Raphael.fn.connection = function (obj1, obj2, line, bg, strokeColor, symbol, labelFontSize) { if (obj1.line && obj1.from && obj1.to) { line = obj1; obj1 = line.from; @@ -43,20 +43,38 @@ Raphael.fn.connection = function (obj1, obj2, line, bg, strokeColor) { y3 = [0, 0, 0, 0, y1 + dy, y1 - dy, y4, y4][res[1]].toFixed(3); var path = ["M", x1.toFixed(3), y1.toFixed(3), "C", x2, y2, x3, y3, x4.toFixed(3), y4.toFixed(3)].join(","); - + var theLine = this.path(path).attr({stroke: color, fill: "none"}); + var labelPoint = theLine.getPointAtLength(theLine.getTotalLength()/2); + var ahPoint = theLine.getPointAtLength(theLine.getTotalLength()); if (line && line.line) { line.bg && line.bg.attr({path: path}); line.line.attr({path: path}); - } else { + line.lbl.remove(); + line.lbl = this.text(labelPoint.x+10, labelPoint.y+10, line.symbol + ).attr({fill:'#000', 'font-size': line.labelFontSize}); + line.ah.remove(); + line.ah = this.circle(ahPoint.x, ahPoint.y, line.labelFontSize/4 + ).attr({stroke: 'none', fill: line.strokeColor}); + } else { var color = typeof line == "string" ? line : strokeColor; - return { + var strokeWidth = bg.split("|")[1] || 3; + var stroke = bg.split("|")[0]; + var ret = { bg: bg && bg.split && this.path(path - ).attr({stroke: bg.split("|")[0], - fill: "none", "stroke-width": bg.split("|")[1] || 3}), - line: this.path(path).attr({stroke: color, fill: "none"}), + ).attr({stroke: stroke, + fill: "none", "stroke-width": strokeWidth}), + line: theLine, from: obj1, - to: obj2 + to: obj2, + symbol: symbol, + labelFontSize: labelFontSize, + strokeColor: strokeColor, + ah: this.circle(ahPoint.x, ahPoint.y, labelFontSize/4 + ).attr({stroke: 'none', fill: strokeColor}), + lbl: this.text(labelPoint.x+10, labelPoint.y+10, symbol + ).attr({fill:'#000', 'font-size': labelFontSize}) }; + return ret; }; }; // source: http://stackoverflow.com/questions/2627436/svg-animation-along-path-with-raphael @@ -120,7 +138,12 @@ Raphael.fn.aNode = function(x, y, r, isFinal, hasSelfConn, }; return res; }; - +// source: http://www.davidcramer.net/code/63/dir-in-javascript.html +function dir(object) { + methods = []; + for (z in object) if (typeof(z) != 'number') methods.push(z); + return methods.join(', '); +}; function graph() { var nodeRadius = 30; @@ -128,7 +151,7 @@ function graph() { var nodeOpacity = 1; var nodeOpacityHi = .5; var labelFontSize = 16; - var strokeWidth = 2; + var strokeWidth = 3; var strokeColor = '#ccc'; r = Raphael("holder", 1024, 640); @@ -143,7 +166,7 @@ function graph() { nodeById[this.id][i].translate(dx, dy); }; for (var i = connections.length; i--;) { - r.connection(connections[i]); + r.connection(connections[i]); }; r.safari(); }, @@ -201,7 +224,8 @@ function graph() { if (state == statex) { continue; } else { - connections.push(r.connection(nodes[k][0], nodes[l][0], strokeWidth, strokeColor)); + connections.push(r.connection(nodes[k][0], nodes[l][0], + strokeColor, strokeColor, strokeColor, ALPHABET[i], labelFontSize)); }; }; l++; @@ -210,4 +234,11 @@ function graph() { }; k++; }; + return { + paper: r, + nodes: nodes, + nodeById: nodeById, + connections: connections, + test: 'test' + }; }; diff --git a/javascripts/uifunc.js b/javascripts/uifunc.js index 007305a..fd608f5 100644 --- a/javascripts/uifunc.js +++ b/javascripts/uifunc.js @@ -1,4 +1,4 @@ -// +// enable/disable if input length is > 0 function checkLength(el, bId) { if(el.value.length > 0) { enable(bId); @@ -7,17 +7,12 @@ function checkLength(el, bId) { }; }; -// -function enable(id) { - $(id).removeAttr("disabled"); -}; - -// -function disable(id) { - $(id).attr("disabled","disabled"); -}; +// enable a disabled form item +function enable(id) { $(id).removeAttr("disabled"); }; +// disable a form item +function disable(id) { $(id).attr("disabled","disabled"); }; -// +// call of RegexParser.parse() from UI function uiParse() { var parser = new RegexParser(); nfa = parser.parse($('#regex').attr('value')); @@ -34,14 +29,35 @@ function uiParse() { enable('#word'); var dfa = new Nfa2Dfa(nfa); var ttable = dfa.do(); - graph(); + window.g = graph(); disable('#regex'); disable('#parseButton'); }; $('#parseMessage').effect("highlight", {}, 1000); + + s = 'abc'; + /*g.mover = g.paper.circle( + g.nodes[0][1][0].cx.baseVal.value, + g.nodes[0][1][0].cy.baseVal.value, 30 + ).attr({fill:'#00f', stroke: 'none', opacity: 0.5}); + for (var i=0; i < s.length; i++) { + (function(g, i) { + setTimeout(function() { + var state = g.nodes[i]; + var x = state[1][0].cx.baseVal.value; + var y = state[1][0].cy.baseVal.value; + g.mover.animateAlong( + g.paper.path( + 'M'+x+state[1][0].r.baseVal.value+','+y+' '+g.connections[i].line.attr('path').toString().substring(1) + +'L'+(g.nodes[i+1][1][0].cx.baseVal.value+(i*2))+','+g.nodes[i+1][1][0].cy.baseVal.value + ).attr({stroke:'none', 'stroke-width':4}) + , 2000) + }, 2000*i); + })(g, i); + };*/ }; -// +// call of NfaSimulator.simulate() from UI function uiSimulate() { var simulator = new NfaSimulator(nfa); var check = simulator.simulate($('#word').attr('value')); @@ -60,3 +76,17 @@ function uiSimulate() { }; $('#checkMessage').effect("highlight", {}, 1000); }; + + +function getKey(e, set) { + var key = String.fromCharCode(e.which); + if (set.indexOf(key) >= 0 || e.which == 8) { + return true; + } + return false; +}; + +// +function graphMove(symbol) { + true; +}; diff --git a/regexvis.html b/regexvis.html index a881d82..a99b991 100644 --- a/regexvis.html +++ b/regexvis.html @@ -55,7 +55,7 @@ Regular Expression: @@ -64,7 +64,7 @@ Word: diff --git a/resources/raphael.png b/resources/raphael.png new file mode 100644 index 0000000..17f0358 Binary files /dev/null and b/resources/raphael.png differ diff --git a/resources/urls.txt b/resources/urls.txt index 4b9dada..49d9c32 100644 --- a/resources/urls.txt +++ b/resources/urls.txt @@ -12,3 +12,10 @@ http://www.gamedev.net/reference/articles/article2170.asp http://raphaeljs.com/reference.html http://www.w3.org/TR/SVG/ + +http://github.com/DmitryBaranovskiy/raphael/ +http://groups.google.com/group/raphaeljs/browse_thread/thread/f7f7cffa82331503/3d40c581a0e6f50b?lnk=raot +http://groups.google.com.au/group/raphaeljs/browse_thread/thread/c4bf09bd58546625/6de8fd1b07a65315?lnk=gst&q=graffle#6de8fd1b07a65315 +http://groups.google.com.au/group/raphaeljs/browse_thread/thread/adaa2b0331f64d61/7dc6d9295ddf7a63?lnk=gst&q=graffle#7dc6d9295ddf7a63 +http://paste.ubuntu.com/205627/ +http://gist.github.com/205638 -- cgit v1.2.3