formatting
[lambda.git] / code / parse.js
index 4fbab09..9712809 100644 (file)
@@ -4,6 +4,9 @@
 //      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
  */
 
@@ -34,14 +37,14 @@ var make_parse = function () {
         a = t.type;
         if (a === "name") {
             o = symbol_table[v];
-            if (o && typeof o !== 'function') {
-                a = "keyword";
-            } else {
+            if (!o || typeof o === 'function') {
                 o = symbol_table["(name)"];
+            } else {
+                a = o.arity || "keyword";
             }
         } else if (a ===  "number") {
-            o = symbol_table["(literal)"];
-            a = "literal";
+            o = symbol_table["(number)"];
+                       a = "literal";
         } else if (a === "operator") {
             o = symbol_table[v];
             if (!o) {
@@ -65,6 +68,16 @@ var make_parse = function () {
         }
     };
 
+       /*
+       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) {
@@ -75,22 +88,8 @@ var make_parse = function () {
         return s;
     };
 
-
-//     try {
-//         if (console && console.debug) {
-//             function print() {
-//                 console.debug.apply(this, arguments);
-//             }
-//         }
-//     } catch (e) {}
-
-
-    var itself = function () {
-        return this;
-    };
-
-    var var_table = {};
-    var name_table = {};
+    var var_table;
+    var name_table;
 
     var name_handler = function () {
         var n = name_table[this.value];
@@ -134,7 +133,6 @@ var make_parse = function () {
 
     symbol("(end)");
     symbol("(name)").handler = name_handler;
-    symbol("(literal)").handler = itself;
     symbol("let").handler = lambda_handler;
     symbol("=").handler = branch_handler;
     symbol("in");
@@ -142,8 +140,93 @@ var make_parse = function () {
     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 = box
+               constant("T", make_lam2(u, v, make_app(vv, uu)));
+               // vireo \uvw.wuv = pair
+               constant("V", make_lam3(u, v, x, make_app3(xx, uu, vv)));
+               // warbler \uv.uvv = C(BM(BBT) = C(BS(C(BBI)I))I
+               constant("W", make_lam2(u, v, make_app3(uu, vv, vv)));
+               // mockingbird \u.uu = SII = omega
+               constant("M", make_lam(u, make_app(uu, uu)));
+               // 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") {
@@ -163,12 +246,18 @@ var make_parse = function () {
                 return t;
             } else {
                 t.first = [];
-                while (token.arity === "name") {
-                    t.first.push(n);
-                    n = token;
+                while (token.arity === "name" || token.id === "\\") {
+                   if (token.id !== "\\") {
+                      t.first.push(n);
+                      n = token;
+                   }
                     advance();
                 }
-                if (token.id === ".") {
+                               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);
@@ -204,8 +293,8 @@ var make_parse = function () {
                     n = token;
                     advance(")");
                 } else {
-                    if (token.arity !== "name") {
-                        token.error("Expected a variable name.");
+                    if (token.arity !== "name" && token.arity !== "literal") {
+                        token.error("Expected a variable name or literal.");
                     }
                     token.first = n;
                     n = token;
@@ -219,7 +308,7 @@ var make_parse = function () {
         tokens = source.tokens();
         token_nr = 0;
         advance();
-        
+
         // let n = c in b
         // (\n. b) c
 
@@ -249,7 +338,7 @@ var make_parse = function () {
             target = t;
             advance("in");
         }
-    
+
         target.second = expression(false);
 
         advance("(end)");