X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=code%2Fparse.js;h=5cdeb40e6210d126593905eb725d22fc0b15ddac;hp=4fbab09e0941aaee8769f0f7bff6a57deefc6e7d;hb=0d85c76d0d37b32bf99483b86828a7d2829db44e;hpb=cd8399c376ac90e274d01f063f14140ee4c41e68 diff --git a/code/parse.js b/code/parse.js index 4fbab09e..5cdeb40e 100644 --- a/code/parse.js +++ b/code/parse.js @@ -4,6 +4,9 @@ // 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 */ @@ -34,14 +37,14 @@ var make_parse = function () { a = t.type; if (a === "name") { o = symbol_table[v]; - if (o && typeof o !== 'function') { - a = "keyword"; - } else { + 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) { @@ -65,6 +68,16 @@ var make_parse = function () { } }; + /* + 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) { @@ -75,22 +88,8 @@ var make_parse = function () { return s; }; - -// try { -// if (console && console.debug) { -// function print() { -// console.debug.apply(this, arguments); -// } -// } -// } catch (e) {} - - - var itself = function () { - return this; - }; - - var var_table = {}; - var name_table = {}; + var var_table; + var name_table; var name_handler = function () { var n = name_table[this.value]; @@ -134,7 +133,6 @@ var make_parse = function () { symbol("(end)"); symbol("(name)").handler = name_handler; - symbol("(literal)").handler = itself; symbol("let").handler = lambda_handler; symbol("=").handler = branch_handler; symbol("in"); @@ -142,8 +140,91 @@ var make_parse = function () { 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("."); + 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))); + + // 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") { @@ -163,12 +244,18 @@ var make_parse = function () { return t; } else { t.first = []; - while (token.arity === "name") { - t.first.push(n); - n = token; + while (token.arity === "name" || token.id === "\\") { + if (token.id !== "\\") { + t.first.push(n); + n = token; + } advance(); } - if (token.id === ".") { + 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); @@ -204,8 +291,8 @@ var make_parse = function () { n = token; advance(")"); } else { - if (token.arity !== "name") { - token.error("Expected a variable name."); + if (token.arity !== "name" && token.arity !== "literal") { + token.error("Expected a variable name or literal."); } token.first = n; n = token;