如何写 Lisp 解释器?

关于代码的话我搜到了两个例子 blog.csdn.net/sedgewick googies.info/articles/l 但具体说, 写一个解释器应该怎样考虑呢?
关注者
304
被浏览
22260

9 个回答

function interpret(form, env, ctx){
	if(form instanceof Array){
		switch(form[0]){
			case 'lambda': {
				var params = form[1];
				var body = form[2];
				return ctx(function(ctx){ return function() {
					var e = Object.create(env);
					for(var j = 0; j < params.length; j++) e[params[j]] = arguments[j];
					return interpret(body, e, ctx)
				}})
			};
			case 'if': {
				var test = form[1], consequent = form[2], alternate = form[3];
				return interpret(form[1], env, function(c){
					if(c) return interpret(consequent, env, ctx)
					else  return interpret(alternate, env, ctx)
				})
			};
			case 'callcc': {
				return interpret(form[1], env, function(f){
					var fctx = function(){ return function(x){ return ctx(x) }};
					return f(fctx)(fctx)
				})
			};
			case 'quote': {
				return ctx(form[1])
			};
			default: {
				return interpretCall(form, env, ctx);
			};
		}
	} else if(typeof form === 'string') {
		return ctx(env[form])
	} else {
		return ctx(form)
	}
}

function interpretCall(form, env, ctx){
	return interpret(form[0], env, function(callee){
		return interpret$(form.slice(1), env, function(args){
			return callee(ctx).apply(null, args)
		})	
	})
}
function interpret$(form, env, ctx){
	if(!form.length) return ctx(null);
	else return interpret(form[0], env, function(x0){
		return interpret$(form.slice(1), env, function(x$){
			if(x$) return ctx([x0])
			else return ctx([x0].concat(x$))
		})
	})
}

function id(x){ return x }

var env0 = { trace: function(ctx){ return function(x) { return ctx(console.log(x)) }}};

interpret(['trace', ['callcc', ['lambda', ['return'], ['return', ['quote', 3]]]]], env0, id);
因为之前有人说我偷懒没做 call/cc,今天我就做它一回。全文按照 Danvy 他们的抽象解释模式写成,显式传递 Continuation。

下面是个混淆版 :)
function $(C,E,K){if(!(C instanceof Array))return K("string"==typeof C?
E[C]:C);switch(C[0]){case"lambda":return K(function(K){return function(
){for(var e=Object.create(E),u=0;u<C[1].length;u++)e[C[1][u]]=arguments
[u];return $(C[2],e,K)}});case"if":return $(C[1],E,function(e){return e
?$(C[2],E,K):$(C[3],E,K)});case"callcc":return $(C[1],E,function(C){var
E=function(){return function(C){return K(C)}};return C(E)(E)});case "'"
:return K(C[1]);default:return $c(C,E,K)}}function $c(C,E,K){return $(C
[0],E,function(e){return $$(C.slice(1),E,function(C){return e(K).apply(
null,C)})})}; function $$(C,E,K) {return C.length?$(C[0],E,function(e){
return $$(C.slice(1),E,function(C){return K(C?[e]:[e].concat(C))})}):K(
null)}var e={trace:function(k){return function(x){return k(console.log(
x))}}};$(['trace',['callcc',['lambda',['return'],['return',["'",42]]]]]
,e,function(x){return x});
如果想完整理解建议阅读SICP第4章,以及MIT配套的视频和讲义
整体来说,你需要考虑以下几个方面(你可以对照着看一下你给的第二个链接中的文章,我觉得Peter Norvig已经描述的很清楚了):
1,词法分析器(lexical analyzer),即将程序分解为一个个词法单位,例如“(+ 5 a)”字符串,分解为['+', 5, 'a']。
2,语法分析器(Parser),就是把上面的结果构造成一颗语法树,即
'+'
/ \
5 'a'
3,求值器(Ealuator),通常求值器还需要一个环境参数,然后计算上述语法树在该环境下的值。例如,假设此时求值环境为{'+': <built-in function add>, 'a': 2},在上述语法树的值为7。
4,打印程序(Printer),就是把上步中得到的值先转换为字符串,再打印出来,我们的例子比较简单,结果就是7。