Skip to content

Instantly share code, notes, and snippets.

@tlrobinson
Created October 2, 2011 08:56
Show Gist options
  • Save tlrobinson/1257254 to your computer and use it in GitHub Desktop.
Save tlrobinson/1257254 to your computer and use it in GitHub Desktop.
Extremely simple lexer, parser, compiler, and interpreter for a prefix notation calculator.

Prefix notation calculator

This is a very simple prefix notation calculator implementation in JavaScript, for the purpose of demonstrating a simple lexer, parser, compiler, and interpreter for my JSConf.eu talk, "JavaScript Compilers for Fun and Profit".

They're available packaged together here:

mini-calc-golfed.js contains each component JS-golfed down to < 140 bytes.

And individually as 140byt.es forks here:

$ ./demo.js
example: (+ 1 2 (* 3.1415 42) (- 3 4) (/ 5 6))
> (+ 1 2 (* 3.1415 42) (- 3 4) (/ 5 6))
tokens => [ '(',
'+',
1,
2,
'(',
'*',
3.1415,
42,
')',
'(',
'-',
3,
4,
')',
'(',
'/',
5,
6,
')',
')' ]
ast => [ '+', 1, 2, [ '*', 3.1415, 42 ], [ '-', 3, 4 ], [ '/', 5, 6 ] ]
compiled => (1+2+(3.1415*42)+(3-4)+(5/6))
interpret(parse(lex(code))) => 134.77633333333335
eval(compile(parse(lex(code)))) => 134.77633333333335
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Copyright (C) 2011 Tom Robinson <http://tlrobinson.net/>
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
// lexer
function l(s){return s.match(/\(|\)|\d+(\.\d+)?|\w+|[+*\/-]/g).map(function(t){return /^\d/.test(t)?parseFloat(t):t})}
// parser
function p(a,b,c){c=[];a.shift();while(b=a.shift()){if(b=="("){a.unshift(b);c.push(p(a))}else if(b==")"){return c}else{c.push(b)}}}
// interpreter
function i(n){if(Array.isArray(n)){n=n.map(i);return n[0].apply(null,n.slice(1))}else{return typeofn=="number"?n:e[n]}}
// compiler / code generator
function c(n,a){if(Array.isArray(n)){return "("+n.slice(1).map(c).join(n[0])+")"}else{return n}}
#!/usr/bin/env node
function lex(string) {
var tokens = string.match(/\(|\)|\d+(\.\d+)?|\w+|[+*\/-]/g);
return tokens.map(function(token) {
return /^\d/.test(token) ? parseFloat(token) : token;
});
}
function parse(tokens) {
var nodes = [];
tokens.shift();
while (token = tokens.shift()) {
if (token == "(") {
tokens.unshift(token);
nodes.push(parse(tokens));
} else if (token == ")") {
return nodes;
} else {
nodes.push(token);
}
}
}
function interpret(node) {
if (Array.isArray(node)) {
var fn = interpret(node[0]);
var args = node.slice(1).map(interpret);
return fn.apply(null, args);
} else if (typeof node === "number") {
return node;
} else {
return environment[node];
}
}
function compile(node) {
if (Array.isArray(node)) {
var operator = node[0];
var values = node.slice(1).map(compile);
return "(" + values.join(operator) + ")";
} else {
return node;
}
}
var reduce = Array.prototype.reduce;
var environment = {};
environment["+"] = function() { return reduce.call(arguments, function(a,n) { return a + n; }, 0); };
environment["*"] = function() { return reduce.call(arguments, function(a,n) { return a * n; }, 1); };
environment["-"] = function(a,b) { return a - b; };
environment["/"] = function(a,b) { return a / b; };
function run(code) {
var tokens = lex(code);
var ast = parse(tokens.slice());
var compiled = compile(ast);
var interpretedResult = interpret(ast);
var compiledResult = eval(compiled);
console.log("tokens =>", tokens);
console.log("ast =>", ast);
console.log("compiled =>", compiled);
console.log("");
console.log("interpret(parse(lex(code))) =>", interpretedResult);
console.log("eval(compile(parse(lex(code)))) =>", compiledResult);
}
process.stdout.write("example: (+ 1 2 (* 3.1415 42) (- 3 4) (/ 5 6))\n");
process.stdout.write("> ");
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(code) {
run(code)
process.stdout.write("> ");
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment