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