[go: nahoru, domu]
Skip to content

Commit

Permalink
group keys in dfa
Browse files Browse the repository at this point in the history
  • Loading branch information
@bert0RM
bert0RM committed Dec 9, 2023
1 parent ce014cd commit c63180e
Show file tree
Hide file tree
Showing 2 changed files with 82 additions and 55 deletions.
88 changes: 80 additions & 8 deletions js/automata.js
View file
Original file line number Diff line number Diff line change
@@ -1,6 +1,55 @@
/*jslint browser: true*/
/*global d3, dagreD3*/

function groupKeys(keys) {
var groupedKeys = "";
var keysArray = keys
.replace("[", "")
.replace("]", "")
.replaceAll('"', "")
.split(",");
if (keysArray.length <= 1) {
return "[" + keys.substring(2,3) + "]";
}

groupedKeys += keysArray[0];
let i = 1;
while (i < keysArray.length) {
// a-z: 97-122, A-Z: 65-90, 0-9: 48-57
// We have a sequence
if (
parseInt(keysArray[i].charCodeAt(0)) ==
parseInt(keysArray[i - 1].charCodeAt(0)) + 1
) {
if (i == keysArray.length - 1) {
groupedKeys += "-" + keysArray[i];
}
i++;
continue;
} // We dont have a sequence
else {
// Did we just end a sequence?
if (
parseInt(keysArray[i].charCodeAt(0)) ==
parseInt(keysArray[i - 1].charCodeAt(0)) + 1
) {
groupedKeys += "-" + keysArray[i - 1];
} else if (
i > 2 &&
parseInt(keysArray[i - 1].charCodeAt(0)) ==
parseInt(keysArray[i - 2].charCodeAt(0)) + 1
) {
groupedKeys += "-" + keysArray[i - 1];
groupedKeys += "," + keysArray[i];
} else {
groupedKeys += "," + keysArray[i];
}
}
i++;
}
return "[" + groupedKeys + "]";
}

/**
* @param {string} svgId The id of the svg tag, which should contains a `g` tag.
* @param {object} start @see regexToNfa().
Expand All @@ -25,7 +74,10 @@ function genAutomataSVG(svgId, start) {
render = new dagreD3.render();

zoom = d3.behavior.zoom().on("zoom", function () {
inner.attr("transform", "translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")");
inner.attr(
"transform",
"translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")"
);
});
svg.call(zoom);
g.setNode(-1, { shape: "text", label: "start" });
Expand All @@ -45,7 +97,7 @@ function genAutomataSVG(svgId, start) {
for (var escapeKey in escapeMap) {
label = label.replace("\\" + escapeKey, "\\\\" + escapeKey);
}
g.setEdge(node.id, next.id, { label: label });
g.setEdge(node.id, next.id, { label: groupKeys(label) });
if (!ids.hasOwnProperty(next.id)) {
queue.push(next);
}
Expand Down Expand Up @@ -211,7 +263,7 @@ function genAutomataSVG(svgId, start) {
render(inner, g);
svg.attr("height", g.graph().height * 1.5 + 40);
var hscale = svg.attr("height") / g.graph().height;
var wscale = svg.attr("width") / (g.graph().width+40);
var wscale = svg.attr("width") / (g.graph().width + 40);
var scale = hscale;
if (hscale > wscale) {
scale = wscale;
Expand Down Expand Up @@ -239,7 +291,10 @@ function genAutomatonLR0(svgId, start) {
render = new dagreD3.render();

zoom = d3.behavior.zoom().on("zoom", function () {
inner.attr("transform", "translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")");
inner.attr(
"transform",
"translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")"
);
});
svg.call(zoom);

Expand All @@ -254,7 +309,13 @@ function genAutomatonLR0(svgId, start) {
while (front < queue.length) {
node = queue[front];
ids[node.key] = node;
label = "I" + node.num + "\n===\n" + prettyPrintItems(node.kernel) + "\n---\n" + prettyPrintItems(node.nonkernel);
label =
"I" +
node.num +
"\n===\n" +
prettyPrintItems(node.kernel) +
"\n---\n" +
prettyPrintItems(node.nonkernel);
g.setNode(node.key, { shape: "rect", label: label });
keys = Object.keys(node.edges);
for (i = 0; i < keys.length; i += 1) {
Expand Down Expand Up @@ -325,12 +386,17 @@ function genAutomatonLR1(svgId, start) {
render = new dagreD3.render();

zoom = d3.behavior.zoom().on("zoom", function () {
inner.attr("transform", "translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")");
inner.attr(
"transform",
"translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")"
);
});
svg.call(zoom);

function prettyPrintItem(item) {
return item.head + " -> " + item.body.join(" ") + ", " + item.lookahead.join("/");
return (
item.head + " -> " + item.body.join(" ") + ", " + item.lookahead.join("/")
);
}

function prettyPrintItems(items) {
Expand All @@ -340,7 +406,13 @@ function genAutomatonLR1(svgId, start) {
while (front < queue.length) {
node = queue[front];
ids[node.key] = node;
label = "I" + node.num + "\n===\n" + prettyPrintItems(node.kernel) + "\n---\n" + prettyPrintItems(node.nonkernel);
label =
"I" +
node.num +
"\n===\n" +
prettyPrintItems(node.kernel) +
"\n---\n" +
prettyPrintItems(node.nonkernel);
g.setNode(node.key, { shape: "rect", label: label });
keys = Object.keys(node.edges);
for (i = 0; i < keys.length; i += 1) {
Expand Down
49 changes: 2 additions & 47 deletions js/min_dfa.js
View file
Original file line number Diff line number Diff line change
Expand Up @@ -54,51 +54,6 @@ $(document).ready(function () {
return result;
}

function groupKeys(keys) {
var groupedKeys = "";
var keysArray = keys.split(",");
if (keysArray.length <= 1) {
return keys;
}

groupedKeys += keysArray[0];
let i = 1;
while (i < keysArray.length) {
// a-z: 97-122, A-Z: 65-90, 0-9: 48-57
// We have a sequence
if (
parseInt(keysArray[i].charCodeAt(0)) ==
parseInt(keysArray[i - 1].charCodeAt(0)) + 1
) {
if (i == keysArray.length - 1) {
groupedKeys += "-" + keysArray[i];
}
i++;
continue;
} // We dont have a sequence
else {
// Did we just end a sequence?
if (
parseInt(keysArray[i].charCodeAt(0)) ==
parseInt(keysArray[i - 1].charCodeAt(0)) + 1
) {
groupedKeys += "-" + keysArray[i - 1];
} else if (
i > 2 &&
parseInt(keysArray[i - 1].charCodeAt(0)) ==
parseInt(keysArray[i - 2].charCodeAt(0)) + 1
) {
groupedKeys += "-" + keysArray[i - 1];
groupedKeys += "," + keysArray[i];
} else {
groupedKeys += "," + keysArray[i];
}
}
i++;
}
return groupedKeys;
}

function genDfaTable(start) {
var i,
j,
Expand Down Expand Up @@ -129,7 +84,7 @@ $(document).ready(function () {
html += '<table class="table is-bordered is-striped is-fullwidth">';
html += "<thead>";
html += "<tr>";
html += "<th>DFA STATE</th>";
// html += "<th>DFA STATE</th>";
html += "<th>Min-DFA STATE</th>";
html += "<th>TYPE</th>";
for (i = 0; i < symbols.length; i += 1) {
Expand All @@ -140,7 +95,7 @@ $(document).ready(function () {
html += "<tbody>";
for (i = 0; i < nodes.length; i += 1) {
html += "<tr>";
html += "<td>{" + groupKeys(nodes[i].key) + "}</td>";
// html += "<td>{" + snodes[i].key + "}</td>";
html += '<td class="node' + nodes[i].id + '">' + nodes[i].id + "</td>";
html += "<td>" + nodes[i].type + "</td>";
for (j = 0; j < symbols.length; j += 1) {
Expand Down

0 comments on commit c63180e

Please sign in to comment.