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
10 /* members create, error, message, name, prototype, stringify, toSource,
14 /*global make_var, make_app, make_lam, Lambda_var */
16 var make_parse = function () {
17 var symbol_table = {};
22 var advance = function (id) {
24 if (id && token.id !== id) {
25 token.error("Expected '" + id + "'.");
27 if (token_nr >= tokens.length) {
28 token = symbol_table["(end)"];
37 if (!o || typeof o === 'function') {
38 o = symbol_table["(name)"];
40 a = o.arity || "keyword";
42 } else if (a === "number") {
43 o = symbol_table["(number)"];
45 } else if (a === "operator") {
48 t.error("Unknown operator.");
52 t.error("Unexpected token.");
54 token = Object.create(o);
58 token.arity = a; // will be: name, keyword, literal
62 var original_symbol = {
63 handler: function () {
64 this.error("Undefined.");
69 if (console && console.debug) {
71 console.debug.apply(this, arguments);
76 var symbol = function (id) {
77 var s = symbol_table[id];
79 s = Object.create(original_symbol);
89 var name_handler = function () {
90 var n = name_table[this.value];
92 n = make_var(this.value);
93 var_table[this.value] = n;
94 n = new Lambda_var(n);
95 name_table[this.value] = n;
98 return make_app(this.first.handler(), n);
104 var branch_handler = function () {
105 var n = this.second.handler();
107 return make_app(this.first.handler(), n);
113 var lambda_handler = function () {
114 var body = this.second.handler();
116 while (this.first.length) {
117 n = this.first.pop().value;
122 name_table[n] = new Lambda_var(v);
124 body = make_lam(v, body);
130 symbol("(name)").handler = name_handler;
131 symbol("let").handler = lambda_handler;
132 symbol("=").handler = branch_handler;
134 symbol(")").handler = branch_handler;
136 symbol("\\").handler = lambda_handler;
137 symbol("lambda").handler = lambda_handler;
140 function make_constants() {
142 function make_lam2(a, b, aa) {
143 return make_lam(a, make_lam(b, aa));
145 function make_lam3(a, b, c, aa) {
146 return make_lam(a, make_lam(b, make_lam(c, aa)));
148 function make_app3(aa, bb, cc) {
149 return make_app(make_app(aa, bb), cc);
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};
165 // constants have their own id and arity = literal
166 // numbers have id = "(number)" and arity = literal
167 symbol("(number)").handler = function () {
169 var res = number_table[n];
174 res = make_app(ss, res);
176 res = make_lam2(s, z, res);
177 number_table[this.value] = res;
182 var constant = function (s, v) {
184 x.handler = function () {
185 this.value = symbol_table[this.id].value;
187 return make_app(this.first.handler(), this.value);
197 constant("S", make_lam3(u, v, x, make_app3(uu, xx, make_app(vv, xx))));
198 constant("K", make_lam2(u, v, uu));
199 constant("I", make_lam(x, xx));
200 constant("B", make_lam3(u, v, x, make_app(uu, make_app(vv, xx))));
201 constant("C", make_lam3(u, v, x, make_app3(uu, xx, vv)));
202 constant("W", make_lam2(u, v, make_app3(uu, vv, vv)));
203 constant("T", make_lam2(u, v, make_app(vv, uu)));
208 var expression = function (in_let) {
210 if (token.id === "\\" || token.id === "lambda") {
211 token.value = "lambda";
215 if (n.arity !== "name") {
216 n.error("Expected a variable name.");
219 if (token.id === "(") {
222 t.second = expression(false);
227 while (token.arity === "name") {
232 if (token.arity === "literal" && t.first.length === 0) {
236 } else if (token.id === ".") {
239 t.second = expression(in_let);
240 } else if (t.first.length === 1) {
244 t.error("Can't parse lambda abstract.");
250 while (token.id === "(") {
252 t = expression(false);
257 if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
262 if (n && (in_let && token.id === "in" || token.id === "(end)" || token.id === ")")) {
264 } else if (token.id === "(") {
266 t = expression(false);
272 if (token.arity !== "name" && token.arity !== "literal") {
273 token.error("Expected a variable name or literal.");
283 return function (source) {
284 tokens = source.tokens();
291 var t = null, eq, c, base = {};
294 while (token.id === "let") {
297 if (token.arity !== "name") {
298 token.error("Expected a variable name.");
302 eq = token; // token.id === "="
304 c = expression(true);
312 // target.second = c;
318 target.second = expression(false);