summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--javascripts/Nfa.js10
-rw-r--r--javascripts/Nfa2Dfa.js80
-rw-r--r--javascripts/NfaSimulator.js9
-rw-r--r--javascripts/NfaState.js5
-rw-r--r--javascripts/RegexParser.js30
-rw-r--r--javascripts/Stack.js14
-rw-r--r--javascripts/globals.js4
-rw-r--r--javascripts/graph.js57
-rw-r--r--javascripts/uifunc.js56
-rw-r--r--regexvis.html4
-rw-r--r--resources/raphael.pngbin0 -> 8091 bytes
-rw-r--r--resources/urls.txt7
12 files changed, 170 insertions, 106 deletions
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()+'<br />');
+
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()+'<br />');
- 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 @@
<tr>
<td style='text-align:right'><strong>Regular Expression:</strong></td>
<td><input type="text" name="regex" id="regex" value=""
- onchange='checkLength(this, "#parseButton")'
+ onchange='checkLength(this, "#parseButton")' onkeypress="return getKey(event, ALPHABETS)"
onmouseout='checkLength(this, "#parseButton")' autocomplete="off" />
<input type="button" name="parseButton" id="parseButton"
value="Parse" disabled='disabled' autocomplete="off" onclick="uiParse()" />
@@ -64,7 +64,7 @@
<tr>
<td style='text-align:right'><strong>Word:</strong></td>
<td><input type="text" name="word" id="word" value="" disabled='disabled'
- onchange='checkLength(this, "#checkButton")'
+ onchange='checkLength(this, "#checkButton")' onkeypress="return getKey(event, ALPHABET)"
onmouseout='checkLength(this, "#checkButton")' autocomplete="off" />
<input type="button" name="checkButton" id="checkButton"
value="Check" disabled='disabled' autocomplete="off" onclick="uiSimulate()" />
diff --git a/resources/raphael.png b/resources/raphael.png
new file mode 100644
index 0000000..17f0358
--- /dev/null
+++ b/resources/raphael.png
Binary files 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 05:11:40 +0000