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