X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=code%2Fparse.js;h=5cdeb40e6210d126593905eb725d22fc0b15ddac;hp=fe079dc5439ece6e9b3cf5f1c7199ed573c90ff3;hb=35949604299e54f944273e8aba8cd2dd33179415;hpb=42859c95fe5548d1fc3c3f5b03980b13a35ebf35;ds=sidebyside diff --git a/code/parse.js b/code/parse.js index fe079dc5..5cdeb40e 100644 --- a/code/parse.js +++ b/code/parse.js @@ -1,8 +1,20 @@ // 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 +// 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 = {}; @@ -24,21 +36,21 @@ var make_parse = function () { v = t.value; a = t.type; if (a === "name") { - o = symbol_table[v]; - if (o && typeof o !== 'function' ) { - a = "keyword"; - } else { - o = symbol_table["(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["(literal)"]; - a = "literal"; + o = symbol_table["(number)"]; + a = "literal"; } else if (a === "operator") { o = symbol_table[v]; if (!o) { t.error("Unknown operator."); } - a = "keyword"; + a = "keyword"; } else { t.error("Unexpected token."); } @@ -53,9 +65,19 @@ var make_parse = function () { 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) { @@ -66,185 +88,259 @@ var make_parse = function () { return s; }; + var var_table; + var name_table; -// try { -// if (console && console.debug) { -// function print() { -// console.debug.apply(this, arguments); -// } -// } -// } catch (e) {} + 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 itself = function () { - return this; + 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; }; - var var_table = {}; - var name_table = {}; + 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("\u03bb").handler = lambda_handler; + // symbol("\u2203").handler = exists_handler; + // symbol("\u2200").handler = forall_handler; + symbol("."); - 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; + function make_constants() { + + function make_lam2(a, b, aa) { + return make_lam(a, make_lam(b, aa)); } - if (this.first) { - return make_app(this.first.handler(), n); - } else { - return n; + function make_lam3(a, b, c, aa) { + return make_lam(a, make_lam(b, make_lam(c, aa))); } - }; - - var branch_handler = function () { - var n = this.second.handler(); - if (this.first) { - return make_app(this.first.handler(), n); - } else { - return n; + 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 = {}; - 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); + // 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; } - body = make_lam(v, body); } - return body; - }; - symbol("(end)"); - symbol("(name)").handler = name_handler; - symbol("(literal)").handler = itself; - 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("."); - - 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") { - t.first.push(n); - n = token; - advance(); - } - if (token.id === ".") { - t.first.push(n); - advance(); - t.second = expression(in_let); - } else if (t.first.length === 1) { - t.second = n; + 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 { - t.first.push(n); - t.error("Can't parse lambda abstract."); + return this.value; } - 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; - } - } - if (token.arity != "name") { - token.error("Expected a variable name."); - } - token.first = n; - n = token; - advance(); - while (true) { - if (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.error("Expected a variable name."); - } - token.first = n; - n = token; - advance(); - } - } - } + 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))); + + // trush \uv.vu = CI + constant("T", make_lam2(u, v, make_app(vv, uu))); + // mockingbird \u.uu = SII + constant("M", make_lam(u, make_app(uu, uu))); + // warbler \uv.uvv = C(BM(BBT) = C(BS(C(BBI)I))I + constant("W", make_lam2(u, v, make_app3(uu, vv, vv))); + // lark \uv.u(vv) = CBM = BWB + constant("L", make_lam2(u, v, make_app(uu, make_app(vv, vv)))); + // Y is SLL + } + 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(); + 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); - c.first = eq; - eq.second = t; - target.second = c; - target = t; - advance("in"); - } - - target.second = expression(false); + + // 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; + return base.second; }; };