// Parser for lambda with let written in Simplified JavaScript
//      by Jim Pryor 2010-09-22
//      Stripped down from Top Down Operator Precedence : parse.js
//      http://javascript.crockford.com/tdop/index.html
//      Douglas Crockford 2010-06-26

//      See also http://effbot.org/zone/simple-top-down-parsing.htm


/*jslint onevar: false
 */

/*   members create, error, message, name, prototype, stringify, toSource,
    toString, write
*/

/*global make_var, make_app, make_lam, Lambda_var */

var make_parse = function () {
    var symbol_table = {};
    var token;
    var tokens;
    var token_nr;

    var advance = function (id) {
        var a, o, t, v;
        if (id && token.id !== id) {
            token.error("Expected '" + id + "'.");
        }
        if (token_nr >= tokens.length) {
            token = symbol_table["(end)"];
            return;
        }
        t = tokens[token_nr];
        token_nr += 1;
        v = t.value;
        a = t.type;
        if (a === "name") {
            o = symbol_table[v];
            if (!o || typeof o === 'function') {
                o = symbol_table["(name)"];
            } else {
                a = o.arity || "keyword";
            }
        } else if (a ===  "number") {
            o = symbol_table["(number)"];
			a = "literal";
        } else if (a === "operator") {
            o = symbol_table[v];
            if (!o) {
                t.error("Unknown operator.");
            }
            a = "keyword";
        } else {
            t.error("Unexpected token.");
        }
        token = Object.create(o);
        token.from  = t.from;
        token.to    = t.to;
        token.value = v;
        token.arity = a; // will be: name, keyword, literal
        return token;
    };

    var original_symbol = {
        handler: function () {
            this.error("Undefined.");
        }
    };

	/*
	try {
		if (console && console.debug) {
			function print() {
				console.debug.apply(this, arguments);
			}
		}
	} catch (e) {}
	*/

    var symbol = function (id) {
        var s = symbol_table[id];
        if (!s) {
            s = Object.create(original_symbol);
            s.id = s.value = id;
            symbol_table[id] = s;
        }
        return s;
    };

    var var_table;
    var name_table;

    var name_handler = function () {
        var n = name_table[this.value];
        if (!n) {
            n = make_var(this.value);
            var_table[this.value] = n;
            n = new Lambda_var(n);
            name_table[this.value] = n;
        }
        if (this.first) {
            return make_app(this.first.handler(), n);
        } else {
            return n;
        }
    };

    var branch_handler = function () {
        var n = this.second.handler();
        if (this.first) {
            return make_app(this.first.handler(), n);
        } else {
            return n;
        }
    };

    var lambda_handler = function () {
        var body = this.second.handler();
        var n, v;
        while (this.first.length) {
            n = this.first.pop().value;
            v = var_table[n];
            if (!v) {
                v = make_var(n);
                var_table[n] = v;
                name_table[n] = new Lambda_var(v);
            }
            body = make_lam(v, body);
        }
        return body;
    };

    symbol("(end)");
    symbol("(name)").handler = name_handler;
    symbol("let").handler = lambda_handler;
    symbol("=").handler = branch_handler;
    symbol("in");
    symbol(")").handler = branch_handler;
    symbol("(");
    symbol("\\").handler = lambda_handler;
    symbol("lambda").handler = lambda_handler;
    symbol(".");

	function make_constants() {

		function make_lam2(a, b, aa) {
			return make_lam(a, make_lam(b, aa));
		}
		function make_lam3(a, b, c, aa) {
			return make_lam(a, make_lam(b, make_lam(c, aa)));
		}
		function make_app3(aa, bb, cc) {
			return make_app(make_app(aa, bb), cc);
		}
		var u = make_var("u");
		var v = make_var("v");
		var x = make_var("x");
		var s = make_var("s");
		var z = make_var("z");
		var uu = new Lambda_var(u);
		var vv = new Lambda_var(v);
		var xx = new Lambda_var(x);
		var ss = new Lambda_var(s);
		var zz = new Lambda_var(z);
		var_table = { u: u, v: v, x: x, s: s, z: z};
		name_table = {u: uu, v: vv, x: xx, s: ss, z: zz};
		number_table = {};

		// constants have their own id and arity = literal
		// numbers have id = "(number)" and arity = literal
		symbol("(number)").handler = function () {
			var n = this.value;
			var res = number_table[n];
			if (!res) {
				res = zz;
				while (n > 0) {
					n -= 1;
					res = make_app(ss, res);
				}
				res = make_lam2(s, z, res);
				number_table[this.value] = res;
			}
			if (this.first) {
				return make_app(this.first.handler(), res);
			} else {
				return res;
			}
		}

		var constant = function (s, v) {
			var x = symbol(s);
			x.handler = function () {
				this.value = symbol_table[this.id].value;
				if (this.first) {
					return make_app(this.first.handler(), this.value);
				} else {
					return this.value;
				}
			};
			x.arity = "literal";
			x.value = v;
			return x;
		};

		constant("S", make_lam3(u, v, x, make_app3(uu, xx, make_app(vv, xx))));
		constant("K", make_lam2(u, v, uu));
		constant("I", make_lam(x, xx));
		constant("B", make_lam3(u, v, x, make_app(uu, make_app(vv, xx))));
		constant("C", make_lam3(u, v, x, make_app3(uu, xx, vv)));
		constant("W", make_lam2(u, v, make_app3(uu, vv, vv)));
		constant("T", make_lam2(u, v, make_app(vv, uu)));

	}
	make_constants();

    var expression = function (in_let) {
        var t, n;
        if (token.id === "\\" || token.id === "lambda") {
            token.value = "lambda";
            t = token;
            advance();
            n = token;
            if (n.arity !== "name") {
                n.error("Expected a variable name.");
            }
            advance();
            if (token.id === "(") {
                t.first = [n];
                advance();
                t.second = expression(false);
                advance(")");
                return t;
            } else {
                t.first = [];
                while (token.arity === "name" || token.id === "\\") {
		    if (token.id !== "\\") {
                      t.first.push(n);
                      n = token;
		    }
                    advance();
                }
				if (token.arity === "literal" && t.first.length === 0) {
					t.first.push(n);
					t.second = token;
					advance();
				} else if (token.id === ".") {
                    t.first.push(n);
                    advance();
                    t.second = expression(in_let);
                } else if (t.first.length === 1) {
                    t.second = n;
                } else {
                    t.first.push(n);
                    t.error("Can't parse lambda abstract.");
                }
                return t;
            }
        } else {
            n = null;
            while (token.id === "(") {
                advance();
                t = expression(false);
                token.first = n;
                token.second = t;
                n = token;
                advance(")");
                if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
                    return n;
                }
            }
            while (true) {
				if (n && (in_let && token.id === "in" || token.id === "(end)" || token.id === ")")) {
                    return n;
                } else if (token.id === "(") {
                    advance();
                    t = expression(false);
                    token.first = n;
                    token.second = t;
                    n = token;
                    advance(")");
                } else {
                    if (token.arity !== "name" && token.arity !== "literal") {
                        token.error("Expected a variable name or literal.");
                    }
                    token.first = n;
                    n = token;
                    advance();
                }
            }
        }
	};

    return function (source) {
        tokens = source.tokens();
        token_nr = 0;
        advance();
        
        // let n = c in b
        // (\n. b) c

        var t = null, eq, c, base = {};
        var target = base;

        while (token.id === "let") {
            t = token;
            advance();
            if (token.arity !== "name") {
                token.error("Expected a variable name.");
            }
            t.first = [token];
            advance();
            eq = token; // token.id === "="
            advance("=");
            c = expression(true);

			eq.first = t;
			eq.second = c;
			target.second = eq;

//             c.first = eq;
//             eq.second = t;
//             target.second = c;

            target = t;
            advance("in");
        }
    
        target.second = expression(false);

        advance("(end)");
        return base.second;
    };

};