dfa.js

function IntervalTree() {
	this.intervals = [];
	this.intervals[0] = [];
	this.nodes = [];
}
IntervalTree.prototype.addInterval = function (unit, id) {
	if (id > this.intervals.length - 1) {
		this.intervals[id] = [];
	}
	this.intervals[id][this.intervals[id].length] = unit;
};
function DFANode(id, accepting, transitions = []) {
	this.id = id;
	this.accept = accepting;
	this.trans = transitions;
}
function DFA(regex = null) {
	this.intervalTree = new IntervalTree();
	this.nodes = [];
	this.start = 0;
	this.addNode(false);
	this.addNode(true);
}
DFA.prototype.addNode = function (accepting, transitions = []) {
	var newNode = new DFANode(this.nodes.length, accepting, transitions);
	this.nodes[newNode.id] = newNode;
	this.intervalTree.addInterval(newNode.trans, newNode.id);
};
DFA.prototype.accepts = function (string) {
	var chars = [];
	for (var loc = 0; loc < string.length; loc++) {
		chars[loc] = string.charCodeAt(loc);
	}
	var charPos = 0;
	var startNode = this.nodes[this.start];
	var nodeStack = [startNode];
	var prefixes = "";
	while (nodeStack.length > 0) {
		var node = nodeStack.pop();
		if (node.accept && prefixes === string) {
			return true;
		}
		if (charPos > string.length) {
			return false;
		}
		for (var accessor in node.trans) {
			var transition = node.trans[accessor];
			if ("eps" in transition) {
				nodeStack[nodeStack.length] = this.nodes[transition.eps];
			} else if ("rng" in transition) {
				if (chars[charPos] >= transition.rng[0] && chars[charPos] <= transition.rng[1]) {
					nodeStack[nodeStack.length] = this.nodes[transition.id];
					prefixes += string[charPos];
				} else {
					return false;
				}
			}
		}
		charPos++;
	}
	return false;
};
var testDFA = new DFA();
testDFA.nodes[0].trans = [{ rng: [72, 72], id: 2 }];
testDFA.addNode(false, [{ rng: [69, 69], id: 3 }]);
testDFA.addNode(false, [{ rng: [76, 76], id: 4 }]);
testDFA.addNode(false, [{ rng: [76, 76], id: 5 }]);
testDFA.addNode(false, [{ rng: [79, 79], id: 1 }]);
console.info(testDFA.accepts("HELLO"));