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
7 // See also http://effbot.org/zone/simple-top-down-parsing.htm
10 /*jslint onevar: false
13 /* members create, error, message, name, prototype, stringify, toSource,
17 /*global make_var, make_app, make_lam, Lambda_var */
19 var make_parse = function () {
20 var symbol_table = {};
25 var advance = function (id) {
27 if (id && token.id !== id) {
28 token.error("Expected '" + id + "'.");
30 if (token_nr >= tokens.length) {
31 token = symbol_table["(end)"];
40 if (!o || typeof o === 'function') {
41 o = symbol_table["(name)"];
43 a = o.arity || "keyword";
45 } else if (a === "number") {
46 o = symbol_table["(number)"];
48 } else if (a === "operator") {
51 t.error("Unknown operator.");
55 t.error("Unexpected token.");
57 token = Object.create(o);
61 token.arity = a; // will be: name, keyword, literal
65 var original_symbol = {
66 handler: function () {
67 this.error("Undefined.");
73 if (console && console.debug) {
75 console.debug.apply(this, arguments);
81 var symbol = function (id) {
82 var s = symbol_table[id];
84 s = Object.create(original_symbol);
94 var name_handler = function () {
95 var n = name_table[this.value];
97 n = make_var(this.value);
98 var_table[this.value] = n;
99 n = new Lambda_var(n);
100 name_table[this.value] = n;
103 return make_app(this.first.handler(), n);
109 var branch_handler = function () {
110 var n = this.second.handler();
112 return make_app(this.first.handler(), n);
118 var lambda_handler = function () {
119 var body = this.second.handler();
121 while (this.first.length) {
122 n = this.first.pop().value;
127 name_table[n] = new Lambda_var(v);
129 body = make_lam(v, body);
135 symbol("(name)").handler = name_handler;
136 symbol("let").handler = lambda_handler;
137 symbol("=").handler = branch_handler;
139 symbol(")").handler = branch_handler;
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;
148 function make_constants() {
150 function make_lam2(a, b, aa) {
151 return make_lam(a, make_lam(b, aa));
153 function make_lam3(a, b, c, aa) {
154 return make_lam(a, make_lam(b, make_lam(c, aa)));
156 function make_app3(aa, bb, cc) {
157 return make_app(make_app(aa, bb), cc);
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};
173 // constants have their own id and arity = literal
174 // numbers have id = "(number)" and arity = literal
175 symbol("(number)").handler = function () {
177 var res = number_table[n];
182 res = make_app(ss, res);
184 res = make_lam2(s, z, res);
185 number_table[this.value] = res;
188 return make_app(this.first.handler(), res);
194 var constant = function (s, v) {
196 x.handler = function () {
197 this.value = symbol_table[this.id].value;
199 return make_app(this.first.handler(), this.value);
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)));
216 constant("T", make_lam2(u, v, make_app(vv, uu)));
217 // mockingbird \u.uu = SII
218 constant("M", make_lam(u, make_app(uu, uu)));
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 // lark \uv.u(vv) = CBM = BWB
222 constant("L", make_lam2(u, v, make_app(uu, make_app(vv, vv))));
228 var expression = function (in_let) {
230 if (token.id === "\\" || token.id === "lambda") {
231 token.value = "lambda";
235 if (n.arity !== "name") {
236 n.error("Expected a variable name.");
239 if (token.id === "(") {
242 t.second = expression(false);
247 while (token.arity === "name" || token.id === "\\") {
248 if (token.id !== "\\") {
254 if (token.arity === "literal" && t.first.length === 0) {
258 } else if (token.id === ".") {
261 t.second = expression(in_let);
262 } else if (t.first.length === 1) {
266 t.error("Can't parse lambda abstract.");
272 while (token.id === "(") {
274 t = expression(false);
279 if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
284 if (n && (in_let && token.id === "in" || token.id === "(end)" || token.id === ")")) {
286 } else if (token.id === "(") {
288 t = expression(false);
294 if (token.arity !== "name" && token.arity !== "literal") {
295 token.error("Expected a variable name or literal.");
305 return function (source) {
306 tokens = source.tokens();
313 var t = null, eq, c, base = {};
316 while (token.id === "let") {
319 if (token.arity !== "name") {
320 token.error("Expected a variable name.");
324 eq = token; // token.id === "="
326 c = expression(true);
334 // target.second = c;
340 target.second = expression(false);