Skip to content

Instantly share code, notes, and snippets.

@wavebeem
Created Jul 28, 2015
Embed
What would you like to do?
Math parser using Parsimmon
var util = require("util");
var parse = require("./parse");
var data = [
"let x = 1 in",
"let y = 2 in",
"3 + x * y + 4 + 1 + 2 ^ 3 ^ 2",
].join("\n") + "\n";
// Deeply show data in a compact format.
function show(data) {
var s = util.inspect(data, {depth: null});
console.log(s);
}
// Pretend to update an object by connecting prototypes and mutating a new one.
function overlay(obj, k, v) {
var x = Object.create(obj);
x[k] = v;
return x;
}
var opTable = {
"+": function(a, b) { return a + b; },
"-": function(a, b) { return a - b; },
"*": function(a, b) { return a * b; },
"/": function(a, b) { return a / b; },
"^": Math.pow,
};
var evaluators = {
Let: function(scope, name, expr, body) {
var newScope = overlay(scope, name[1], evaluate(scope, expr));
return evaluate(newScope, body);
},
BinOp: function(scope, op, left, right) {
return opTable[op](
evaluate(scope, left),
evaluate(scope, right)
);
},
Number: function(scope, number) {
return number;
},
Ident: function(scope, ident) {
if (ident in scope) {
return scope[ident];
}
throw new Error("no such variable: " + ident);
}
}
function evaluate(scope, data) {
var tag = data[0];
var rest = data.slice(1);
var args = [scope].concat(rest);
if (evaluators.hasOwnProperty(tag)) {
return evaluators[tag].apply(null, args);
}
throw new Error("oops");
}
var ast = parse(data);
console.log("\n####### AST ###############\n");
show(ast);
console.log("\n####### VALUE #############\n");
show(evaluate({}, ast))
####### AST ###############
[ 'Let',
[ 'Ident', 'x' ],
[ 'Number', 1 ],
[ 'Let',
[ 'Ident', 'y' ],
[ 'Number', 2 ],
[ 'BinOp',
'+',
[ 'BinOp',
'+',
[ 'BinOp',
'+',
[ 'BinOp',
'+',
[ 'Number', 3 ],
[ 'BinOp', '*', [ 'Ident', 'x' ], [ 'Ident', 'y' ] ] ],
[ 'Number', 4 ] ],
[ 'Number', 1 ] ],
[ 'BinOp',
'^',
[ 'BinOp', '^', [ 'Number', 2 ], [ 'Number', 2 ] ],
[ 'Number', 3 ] ] ] ] ]
####### VALUE #############
74
var P = require("parsimmon");
var __ = P.optWhitespace;
function arrow(n) {
var s = "";
while (n-- > 0) {
s += "~";
}
s += "^";
return s;
}
function first(xs) {
return xs[0];
}
function rest(xs) {
return xs.slice(1);
}
function parseNumber(text) {
return +text;
}
function between(sep, a, b) {
if (arguments.length === 1) {
return between.bind(null, sep);
}
return a + sep + b;
}
function cons(x, xs) {
if (arguments.length === 1) {
return cons.bind(null, x);
}
return [x].concat(xs);
}
function concat(a, b) {
return a.concat(b);
}
function flatten(list) {
return list.reduce(concat, []);
}
function spaced(p) {
return __.then(p).skip(__);
}
function word(text) {
return spaced(P.string(text));
}
function surrounded(l, x, r) {
return P.string(l).then(x).skip(P.string(r));
}
function BinOp(associativity, p, ops) {
var pOps = spaced(P.alt.apply(null, ops.map(P.string)));
var f = reduceBinOps.bind(null, associativity);
return P.seq(p, P.seq(pOps, p).many()).map(f);
}
function reduceBinOps(associativity, args) {
var e = first(args);
var es = flatten(rest(args));
if (associativity === "right") {
es.reverse();
} else if (associativity !== "left") {
throw new Error("invalid associativity: " + associativity);
}
return es.reduce(function(acc, x) {
return ["BinOp", x[0], acc, x[1]];
}, e);
}
////// BEGIN GRAMMAR //////
var Expr = P.lazy(function() {
return spaced(LetExpr.or(BinExpr));
});
var Ident = P.regex(/[a-zA-Z]+/)
.map(cons("Ident"))
.desc("Identifier");
var Number = P.regex(/[0-9]+/)
.map(parseNumber)
.map(cons("Number"))
.desc("Number");
var BaseExpr = P.alt(
Number,
Ident,
surrounded("(", Expr, ")")
);
var ExpExpr = BinOp("right", BaseExpr, ["^"]);
var MulExpr = BinOp("left", ExpExpr, ["*", "/"]);
var AddExpr = BinOp("left", MulExpr, ["+", "-"]);
var BinExpr = AddExpr;
var LetExpr = P.seq(
word("let").then(Ident),
word("=").then(Expr),
word("in").then(Expr)
).map(cons("Let"));
////// END GRAMMAR //////
function parse(text) {
var result = Expr.parse(text);
if (!result.status) {
// TODO: Convert index to actual line and column numbers.
var lineno = result.index + 1;
console.error([
"/your/filesystem/program.txt:" + lineno,
"",
" " + text,
" " + arrow(result.index),
"",
"parse error: expected " +
result.expected.reduce(between(", ")),
].join("\n"));
process.exit(1);
}
return result.value;
}
module.exports = parse;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment