怎样写一个解释器js版本

树遍历算法:

var treeSum = (list) => {

    if (typeof list === 'number') {
        return list;
    } else {
        var car = list.shift();
        var cdr = list.shift();
        return tree(car) + tree(cdr);
    } 
}

treeSum([1, 2]);
treeSum([1, [2, 3]]);
treeSum([[1, 2], 3]);
treeSum([[1, 2], [3, 4]]);

一个计算器

var calc = (list) => {
    if (typeof list === 'number') {
        return list;
    } else {
        var op = list.shift();
        var car = list.shift();
        var cdr = list.shift();

        if (op == '+') {
            return calc(car) + calc(cdr);
        } else if (op == '-') {
            return calc(car) - calc(cdr);
        } else if (op == '*') {
            return calc(car) * calc(cdr);
        } else {
            return calc(car) / calc(cdr);
        }
    }
}
calc(['+', 1, 2])

设置一个环境

var env0 = [];

var extenv = (x, v, env) => {
    var m = new Map();
    m.set(x, v);
    env.push(m);
    //如果需要进行查找需要做这样
}

var lookup = (x, env) => {
    var p = 0;
    for (var i in env) {
        if (env[i].has(x)) {
            p = env[i].get(x);
        }
    }
    if (p == undefined) {
        return false;
    } else {
        return p;
    }
}

下面是对语言环境的定义

var env0 = [];

var extenv = (x, v, env) => {
    var m = new Map();
    m.set(x, v);
    env.push(m);
}

var lookup = (x, env) => {
    var p = 0;
    for (var i in env) {
        if (env[i].has(x)) {
            p = env[i].get(x);
        }
    }
    if (p == undefined) {
        return false;
    } else {
        return p;
    }
}

#lang racket
;; 空环境
(define env0 '())

;; 对环境 env 进行扩展，把 x 映射到 v
(define ext-env
  (lambda (x v env)
    (cons `(,x . ,v) env)))

;; 取值。在环境中 env 中查找 x 的值
(define lookup
  (lambda (x env)
    (let ([p (assq x env)])
      (cond
       [(not p) #f]
       [else (cdr p)]))))

;;闭包的数据结构定义, 包含一个函数定义f和它定义时候所在的环境
(struct Closure (f env))

;;解释器
(define interp
  (lambda (exp env)
    (match exp
      [(? symbol? x)
       (let ([v (lookup x env)])
         (cond
           [(not v)
            (error "undefined varible" x)]
           [else v]))]
      [(? number? x) x]
      [`(lambda (,x) ,e)
       (Closure exp env)]
      [`(let ([,x ,e1]) ,e2)
       (let ([v1 (interp e1 env)])
         (interp e2 (ext-env x v1 env)))]
      [`(,e1, e2)
      (let ([v1 (interp e1 env)]                ;;计算函数e1的值
            [v2 (interp e2 env)])               ;;计算参数e2的值
        (match v1
          [(Closure `(lambda (,x) ,e) env-save) ;;使用模式匹配的方式取出闭包中的各个子结构
           (interp e (ext-env x v2 env-save))]))];;在闭包的环境中env-save中把x绑定到v2, 解释函数体
      [`(,op ,e1, e2)
       (let ([v1 (interp e1 env)]
             [v2 (interp e2 env)])
         (match op
           ['+ (+ v1 v2)]
           ['- (- v1 v2)]
           ['* (* v1 v2)]
           ['/ (/ v1 v2)]))])))

(define r2
  (lambda (exp)
    (interp exp env0)))

;;scheme中的作用域
(let ([x 2])
  (let ([f (lambda (y) (* x y))])
    (let ([x 4])
      (f 3)))) ;;在这里不应该去产生影响

;;对函数调用的解释
(r2 '(+ 1 2))
(r2 '(* 2 3))
(r2 '((lambda (x))))

原文地址：http://www.cnblogs.com/zhengel/p/16907371.html