Last active
August 29, 2015 13:56
-
-
Save nathan/8876236 to your computer and use it in GitHub Desktop.
Earley parser
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
~ function(exp) { | |
function Rule(name, symbols, postprocess) { | |
this.name = name; | |
this.symbols = symbols; | |
this.postprocess = postprocess || function(a){return a}; | |
} | |
Rule.prototype.getStartState = function(location) { | |
return new State(this, 0, location); | |
} | |
function State(rule, expect, reference) { | |
this.rule = rule; | |
this.expect = expect; | |
this.reference = reference; | |
this.data = []; | |
} | |
State.prototype.consume = function(inp) { | |
var rem = Object.prototype.toString.call(this.rule.symbols[this.expect]) === '[object RegExp]' && this.rule.symbols[this.expect].test(inp); | |
if (rem || this.rule.symbols[this.expect] === inp) { | |
var a = new State(this.rule, this.expect+1, this.reference); | |
a.data = this.data.slice(0); | |
a.data.push(inp); | |
return a; | |
} else { | |
return false; | |
} | |
} | |
State.prototype.complete = function(table, location) { | |
if (this.expect === this.rule.symbols.length) { | |
this.data = this.rule.postprocess(this.data); | |
var me = this; | |
var w = 0; | |
while (w < table[this.reference].length) { | |
var s = table[this.reference][w]; | |
var x = s.consume(me.rule.name); | |
if (x) { | |
x.data[x.data.length-1] = me.data; | |
table[location].push(x); | |
x.complete(table, location); | |
} | |
w++; | |
} | |
/*table[this.reference].forEach(function(s) { | |
var x = s.consume(me.rule.name); | |
if (x) { | |
x.data[x.data.length-1] = me.data; | |
table[location].push(x); | |
x.complete(table, location); | |
} | |
});*/ | |
} | |
} | |
function Parse(tokens, rules, start) { | |
if (!start) { | |
start = rules[0]; | |
} | |
var table = []; | |
table.push([]); | |
// I could be expecting anything! | |
rules.forEach(function (r) { | |
table[0].push(r.getStartState(0)); | |
}); | |
table[0].forEach(function(s) { | |
s.complete(table, 0); | |
}); | |
for (var current = 0; current < tokens.length; current++) { | |
table.push([]); | |
table[current].forEach(function(s) { | |
var x = s.consume(tokens[current]); | |
if (x) { | |
table[current+1].push(x); | |
} | |
}); | |
// TODO: This isn't the right thing | |
// you want to only push in what you can expect | |
/* | |
rules.forEach(function (r) { | |
table[current+1].push(r.getStartState(current+1)); | |
});*/ | |
var i = 0; | |
var addedRules = []; | |
while (i < table[current+1].length) { | |
var state = table[current+1][i]; | |
var exp = state.rule.symbols[state.expect]; | |
rules.forEach(function(r) { | |
if (r.name === exp && addedRules.indexOf(r) === -1) { | |
addedRules.push(r); | |
table[current+1].push(r.getStartState(current+1)); | |
} | |
}); | |
i++; | |
} | |
table[current+1].forEach(function(s) { | |
s.complete(table, current+1); | |
}); | |
} | |
console.log(require('util').inspect(table, null, {depth:-1})); | |
var considerations = []; | |
table[table.length-1].forEach(function (t) { | |
if (t.rule.name === start && t.expect === t.rule.symbols.length && t.reference === 0) { | |
considerations.push(t); | |
} | |
}); | |
if (considerations[0]) { | |
return considerations[0].data; | |
} else { | |
return false; | |
} | |
} | |
var E = {rule:"E"}; | |
var T = {rule:"T"}; | |
console.log(Parse("1 + 1".split(/\s+/), [ | |
new Rule(E, [new RegExp("[0-9]+")], function(d) {return parseFloat(d);}), | |
new Rule(E, [E, "*", E], function(d) {return d[0] * d[2];}), | |
new Rule(E, [E, "+", E], function(d) {return d[0] + d[2];}) | |
], E)); | |
var S = {rule:"S"}; | |
console.log(Parse(["b", "b", "b"], [ | |
new Rule(S, [S, "b"]), | |
new Rule(S, []) | |
], S)); | |
var S = {rule:"S"}; | |
console.log(Parse(["b", "b", "b"], [ | |
new Rule(S, [S, S, "b"]) | |
new Rule(S, []) | |
], S)); | |
}(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment