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