Extremely simple lexer, parser, compiler, and interpreter for a prefix notation calculator.

README.md

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:

• https://gist.github.com/1257254

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

And individually as 140byt.es forks here:

• Lexer: https://gist.github.com/1259461
• Parser: https://gist.github.com/1259487
• Interpreter: https://gist.github.com/1259489
• Compiler: https://gist.github.com/1259490

example.txt

$ ./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

LICENSE.txt

            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.

mini-calc-golfed.js

// 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}}

mini-calc.js

#!/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("> ");
});