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 var make_parse = function () {
   8     var symbol_table = {};
   9     var token;
  10     var tokens;
  11     var token_nr;
  12
  13     var advance = function (id) {
  14         var a, o, t, v;
  15         if (id && token.id !== id) {
  16             token.error("Expected '" + id + "'.");
  17         }
  18         if (token_nr >= tokens.length) {
  19             token = symbol_table["(end)"];
  20             return;
  21         }
  22         t = tokens[token_nr];
  23         token_nr += 1;
  24         v = t.value;
  25         a = t.type;
  26         if (a === "name") {
  27                         o = symbol_table[v];
  28                         if (o && typeof o !== 'function' ) {
  29                                 a = "keyword";
  30                         } else {
  31                                 o = symbol_table["(name)"];
  32                         }
  33         } else if (a ===  "number") {
  34             o = symbol_table["(literal)"];
  35             a = "literal";
  36         } else if (a === "operator") {
  37             o = symbol_table[v];
  38             if (!o) {
  39                 t.error("Unknown operator.");
  40             }
  41                         a = "keyword";
  42         } else {
  43             t.error("Unexpected token.");
  44         }
  45         token = Object.create(o);
  46         token.from  = t.from;
  47         token.to    = t.to;
  48         token.value = v;
  49         token.arity = a; // will be: name, keyword, literal
  50         return token;
  51     };
  52
  53     var original_symbol = {
  54         handler: function () {
  55             this.error("Undefined.");
  56         },
  57     };
  58
  59     var symbol = function (id) {
  60         var s = symbol_table[id];
  61         if (!s) {
  62             s = Object.create(original_symbol);
  63             s.id = s.value = id;
  64             symbol_table[id] = s;
  65         }
  66         return s;
  67     };
  68
  69
  70 //     try {
  71 //         if (console && console.debug) {
  72 //             function print() {
  73 //                 console.debug.apply(this, arguments);
  74 //             }
  75 //         }
  76 //     } catch (e) {}
  77
  78
  79     var itself = function () {
  80         return this;
  81     };
  82
  83         var var_table = {};
  84         var name_table = {};
  85
  86         var name_handler = function () {
  87                 var n = name_table[this.value];
  88                 if (!n) {
  89                         n = make_var(this.value);
  90                         var_table[this.value] = n;
  91                         n = new Lambda_var(n);
  92                         name_table[this.value] = n;
  93                 }
  94                 if (this.first) {
  95                         return make_app(this.first.handler(), n);
  96                 } else {
  97                         return n;
  98                 }
  99         };
 100
 101         var branch_handler = function () {
 102                 var n = this.second.handler();
 103                 if (this.first) {
 104                         return make_app(this.first.handler(), n);
 105                 } else {
 106                         return n;
 107                 }
 108         };
 109
 110         var lambda_handler = function () {
 111                 var body = this.second.handler();
 112                 var n, v;
 113                 while (this.first.length) {
 114                         n = this.first.pop().value;
 115                         v = var_table[n];
 116                         if (!v) {
 117                                 v = make_var(n);
 118                                 var_table[n] = v;
 119                                 name_table[n] = new Lambda_var(v);
 120                         }
 121                         body = make_lam(v, body);
 122                 }
 123                 return body;
 124         };
 125
 126     symbol("(end)");
 127         symbol("(name)").handler = name_handler;
 128     symbol("(literal)").handler = itself;
 129         symbol("let").handler = lambda_handler;
 130         symbol("=").handler = branch_handler;
 131         symbol("in");
 132         symbol(")").handler = branch_handler;
 133         symbol("(");
 134         symbol("\\").handler = lambda_handler;
 135         symbol("lambda").handler = lambda_handler;
 136         symbol(".");
 137
 138         var expression = function (in_let) {
 139                 var t, n;
 140                 if (token.id === "\\" || token.id === "lambda") {
 141                         token.value = "lambda";
 142                         t = token;
 143                         advance();
 144                         n = token;
 145                         if (n.arity !== "name") {
 146                                 n.error("Expected a variable name.");
 147                         }
 148                         advance();
 149                         if (token.id === "(") {
 150                                 t.first = [n];
 151                                 advance();
 152                                 t.second = expression(false);
 153                                 advance(")");
 154                                 return t;
 155                         } else {
 156                                 t.first = [];
 157                                 while (token.arity === "name") {
 158                                         t.first.push(n);
 159                                         n = token;
 160                                         advance();
 161                                 }
 162                                 if (token.id === ".") {
 163                                         t.first.push(n);
 164                                         advance();
 165                                         t.second = expression(in_let);
 166                                 } else if (t.first.length === 1) {
 167                                         t.second = n;
 168                                 } else {
 169                                         t.first.push(n);
 170                                         t.error("Can't parse lambda abstract.");
 171                                 }
 172                                 return t;
 173                         };
 174                 } else {
 175                         n = null;
 176                         while (token.id === "(") {
 177                                 advance();
 178                                 t = expression(false);
 179                                 token.first = n;
 180                                 token.second = t;
 181                                 n = token;
 182                                 advance(")");
 183                                 if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
 184                                         return n;
 185                                 }
 186                         }
 187                         if (token.arity != "name") {
 188                                 token.error("Expected a variable name.");
 189                         }
 190                         token.first = n;
 191                         n = token;
 192                         advance();
 193                         while (true) {
 194                                 if (in_let && token.id === "in" || token.id === "(end)" || token.id === ")") {
 195                                         return n;
 196                                 } else if (token.id === "(") {
 197                                         advance();
 198                                         t = expression(false);
 199                                         token.first = n;
 200                                         token.second = t;
 201                                         n = token;
 202                                         advance(")");
 203                                 } else {
 204                                         if (token.arity != "name") {
 205                                                 token.error("Expected a variable name.");
 206                                         }
 207                                         token.first = n;
 208                                         n = token;
 209                                         advance();
 210                                 }
 211                         }
 212                 }
 213         }
 214
 215     return function (source) {
 216                 tokens = source.tokens();
 217         token_nr = 0;
 218         advance();
 219
 220                 // let n = c in b
 221                 // (\n. b) c
 222
 223                 var t = null, eq, c, base = {};
 224                 var target = base;
 225
 226                 while (token.id == "let") {
 227                         t = token;
 228                         advance();
 229                         if (token.arity !== "name") {
 230                                 token.error("Expected a variable name.");
 231                         }
 232                         t.first = [token];
 233                         advance();
 234                         eq = token; // token.id === "="
 235                         advance("=");
 236                         c = expression(true);
 237                         c.first = eq;
 238                         eq.second = t;
 239                         target.second = c;
 240                         target = t;
 241                         advance("in");
 242                 }
 243
 244                 target.second = expression(false);
 245
 246         advance("(end)");
 247                 return base.second;
 248     };
 249
 250 };
 251