code/parse.js

   1 // Parser for lambda with let written in Simplified JavaScript
   2 //      by Jim Pryor 2010-09-22
   3 //      Stripped down from Top Down Operator Precedence : parse.js
   4 //      http://javascript.crockford.com/tdop/index.html
   5 //      Douglas Crockford 2010-06-26
   6
   7 //      See also http://effbot.org/zone/simple-top-down-parsing.htm
   8
   9
  10 /*jslint onevar: false
  11  */
  12
  13 /*   members create, error, message, name, prototype, stringify, toSource,
  14     toString, write
  15 */
  16
  17 /*global make_var, make_app, make_lam, Lambda_var */
  18
  19 var make_parse = function () {
  20     var symbol_table = {};
  21     var token;
  22     var tokens;
  23     var token_nr;
  24
  25     var advance = function (id) {
  26         var a, o, t, v;
  27         if (id && token.id !== id) {
  28             token.error("Expected '" + id + "'.");
  29         }
  30         if (token_nr >= tokens.length) {
  31             token = symbol_table["(end)"];
  32             return;
  33         }
  34         t = tokens[token_nr];
  35         token_nr += 1;
  36         v = t.value;
  37         a = t.type;
  38         if (a === "name") {
  39             o = symbol_table[v];
  40             if (!o || typeof o === 'function') {
  41                 o = symbol_table["(name)"];
  42             } else {
  43                 a = o.arity || "keyword";
  44             }
  45         } else if (a ===  "number") {
  46             o = symbol_table["(number)"];
  47                         a = "literal";
  48         } else if (a === "operator") {
  49             o = symbol_table[v];
  50             if (!o) {
  51                 t.error("Unknown operator.");
  52             }
  53             a = "keyword";
  54         } else {
  55             t.error("Unexpected token.");
  56         }
  57         token = Object.create(o);
  58         token.from  = t.from;
  59         token.to    = t.to;
  60         token.value = v;
  61         token.arity = a; // will be: name, keyword, literal
  62         return token;
  63     };
  64
  65     var original_symbol = {
  66         handler: function () {
  67             this.error("Undefined.");
  68         }
  69     };
  70
  71         /*
  72         try {
  73                 if (console && console.debug) {
  74                         function print() {
  75                                 console.debug.apply(this, arguments);
  76                         }
  77                 }
  78         } catch (e) {}
  79         */
  80
  81     var symbol = function (id) {
  82         var s = symbol_table[id];
  83         if (!s) {
  84             s = Object.create(original_symbol);
  85             s.id = s.value = id;
  86             symbol_table[id] = s;
  87         }
  88         return s;
  89     };
  90
  91     var var_table;
  92     var name_table;
  93
  94     var name_handler = function () {
  95         var n = name_table[this.value];
  96         if (!n) {
  97             n = make_var(this.value);
  98             var_table[this.value] = n;
  99             n = new Lambda_var(n);
 100             name_table[this.value] = n;
 101         }
 102         if (this.first) {
 103             return make_app(this.first.handler(), n);
 104         } else {
 105             return n;
 106         }
 107     };
 108
 109     var branch_handler = function () {
 110         var n = this.second.handler();
 111         if (this.first) {
 112             return make_app(this.first.handler(), n);
 113         } else {
 114             return n;
 115         }
 116     };
 117
 118     var lambda_handler = function () {
 119         var body = this.second.handler();
 120         var n, v;
 121         while (this.first.length) {
 122             n = this.first.pop().value;
 123             v = var_table[n];
 124             if (!v) {
 125                 v = make_var(n);
 126                 var_table[n] = v;
 127                 name_table[n] = new Lambda_var(v);
 128             }
 129             body = make_lam(v, body);
 130         }
 131         return body;
 132     };
 133
 134     symbol("(end)");
 135     symbol("(name)").handler = name_handler;
 136     symbol("let").handler = lambda_handler;
 137     symbol("=").handler = branch_handler;
 138     symbol("in");
 139     symbol(")").handler = branch_handler;
 140     symbol("(");
 141     symbol("\\").handler = lambda_handler;
 142     symbol("lambda").handler = lambda_handler;
 143     symbol("\u03bb").handler = lambda_handler;
 144     // symbol("\u2203").handler = exists_handler;
 145     // symbol("\u2200").handler = forall_handler;
 146     symbol(".");
 147
 148         function make_constants() {
 149
 150                 function make_lam2(a, b, aa) {
 151                         return make_lam(a, make_lam(b, aa));
 152                 }
 153                 function make_lam3(a, b, c, aa) {
 154                         return make_lam(a, make_lam(b, make_lam(c, aa)));
 155                 }
 156                 function make_app3(aa, bb, cc) {
 157                         return make_app(make_app(aa, bb), cc);
 158                 }
 159                 var u = make_var("u");
 160                 var v = make_var("v");
 161                 var x = make_var("x");
 162                 var s = make_var("s");
 163                 var z = make_var("z");
 164                 var uu = new Lambda_var(u);
 165                 var vv = new Lambda_var(v);
 166                 var xx = new Lambda_var(x);
 167                 var ss = new Lambda_var(s);
 168                 var zz = new Lambda_var(z);
 169                 var_table = { u: u, v: v, x: x, s: s, z: z};
 170                 name_table = {u: uu, v: vv, x: xx, s: ss, z: zz};
 171                 number_table = {};
 172
 173                 // constants have their own id and arity = literal
 174                 // numbers have id = "(number)" and arity = literal
 175                 symbol("(number)").handler = function () {
 176                         var n = this.value;
 177                         var res = number_table[n];
 178                         if (!res) {
 179                                 res = zz;
 180                                 while (n > 0) {
 181                                         n -= 1;
 182                                         res = make_app(ss, res);
 183                                 }
 184                                 res = make_lam2(s, z, res);
 185                                 number_table[this.value] = res;
 186                         }
 187                         if (this.first) {
 188                                 return make_app(this.first.handler(), res);
 189                         } else {
 190                                 return res;
 191                         }
 192                 }
 193
 194                 var constant = function (s, v) {
 195                         var x = symbol(s);
 196                         x.handler = function () {
 197                                 this.value = symbol_table[this.id].value;
 198                                 if (this.first) {
 199                                         return make_app(this.first.handler(), this.value);
 200                                 } else {
 201                                         return this.value;
 202                                 }
 203                         };
 204                         x.arity = "literal";
 205                         x.value = v;
 206                         return x;
 207                 };
 208
 209                 constant("S", make_lam3(u, v, x, make_app3(uu, xx, make_app(vv, xx))));
 210                 constant("K", make_lam2(u, v, uu));
 211                 constant("I", make_lam(x, xx));
 212                 constant("B", make_lam3(u, v, x, make_app(uu, make_app(vv, xx))));
 213                 constant("C", make_lam3(u, v, x, make_app3(uu, xx, vv)));
 214
 215                 // trush \uv.vu = CI = box
 216                 constant("T", make_lam2(u, v, make_app(vv, uu)));
 217                 // vireo \uvw.wuv = pair
 218                 constant("V", make_lam3(u, v, x, make_app3(xx, uu, vv)));
 219                 // warbler \uv.uvv = C(BM(BBT) = C(BS(C(BBI)I))I
 220                 constant("W", make_lam2(u, v, make_app3(uu, vv, vv)));
 221                 // mockingbird \u.uu = SII = omega
 222                 constant("M", make_lam(u, make_app(uu, uu)));
 223                 // lark \uv.u(vv) = CBM = BWB
 224                 constant("L", make_lam2(u, v, make_app(uu, make_app(vv, vv))));
 225                 // Y is SLL
 226
 227         }
 228         make_constants();
 229
 230     var expression = function (in_let) {
 231         var t, n;
 232         if (token.id === "\\" || token.id === "lambda") {
 233             token.value = "lambda";
 234             t = token;
 235             advance();
 236             n = token;
 237             if (n.arity !== "name") {
 238                 n.error("Expected a variable name.");
 239             }
 240             advance();
 241             if (token.id === "(") {
 242                 t.first = [n];
 243                 advance();
 244                 t.second = expression(false);
 245                 advance(")");
 246                 return t;
 247             } else {
 248                 t.first = [];
 249                 while (token.arity === "name" || token.id === "\\") {
 250                     if (token.id !== "\\") {
 251                       t.first.push(n);
 252                       n = token;
 253                     }
 254                     advance();
 255                 }
 256                                 if (token.arity === "literal" && t.first.length === 0) {
 257                                         t.first.push(n);
 258                                         t.second = token;
 259                                         advance();
 260                                 } else if (token.id === ".") {
 261                     t.first.push(n);
 262                     advance();
 263                     t.second = expression(in_let);
 264                 } else if (t.first.length === 1) {
 265                     t.second = n;
 266                 } else {
 267                     t.first.push(n);
 268                     t.error("Can't parse lambda abstract.");
 269                 }
 270                 return t;
 271             }
 272         } else {
 273             n = null;
 274             while (token.id === "(") {
 275                 advance();
 276                 t = expression(false);
 277                 token.first = n;
 278                 token.second = t;
 279                 n = token;
 280                 advance(")");
 281                 if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
 282                     return n;
 283                 }
 284             }
 285             while (true) {
 286                                 if (n && (in_let && token.id === "in" || token.id === "(end)" || token.id === ")")) {
 287                     return n;
 288                 } else if (token.id === "(") {
 289                     advance();
 290                     t = expression(false);
 291                     token.first = n;
 292                     token.second = t;
 293                     n = token;
 294                     advance(")");
 295                 } else {
 296                     if (token.arity !== "name" && token.arity !== "literal") {
 297                         token.error("Expected a variable name or literal.");
 298                     }
 299                     token.first = n;
 300                     n = token;
 301                     advance();
 302                 }
 303             }
 304         }
 305         };
 306
 307     return function (source) {
 308         tokens = source.tokens();
 309         token_nr = 0;
 310         advance();
 311
 312         // let n = c in b
 313         // (\n. b) c
 314
 315         var t = null, eq, c, base = {};
 316         var target = base;
 317
 318         while (token.id === "let") {
 319             t = token;
 320             advance();
 321             if (token.arity !== "name") {
 322                 token.error("Expected a variable name.");
 323             }
 324             t.first = [token];
 325             advance();
 326             eq = token; // token.id === "="
 327             advance("=");
 328             c = expression(true);
 329
 330                         eq.first = t;
 331                         eq.second = c;
 332                         target.second = eq;
 333
 334 //             c.first = eq;
 335 //             eq.second = t;
 336 //             target.second = c;
 337
 338             target = t;
 339             advance("in");
 340         }
 341
 342         target.second = expression(false);
 343
 344         advance("(end)");
 345         return base.second;
 346     };
 347
 348 };
 349