--- /dev/null
+// 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("\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") {
+ 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;
+ };
+
+};
+