用JS创造一个全新的编程语言

摘要：编程语言代码改自编程语言遵循如下规范语言只有表达式，没有语句，如加法，连续相加如多个表达式用包裹，如数据类型支持数字布尔字符串代码实现将源码字符串成。一个合法的语言必然是一个表达式，所以解析的开始可以是函数，如解析源码。

代码改自Eloquent Javascript: Chapter 12

语言只有表达式，没有语句，如加法：+(1, 7)，连续相加如+(1, +(2,3))

多个表达式用do包裹，如do(expr1, expr2, expr3, ..., exprN)

数据类型支持数字 布尔 字符串

将源码字符串parse成ast。

do(foo(), "done")

{
    "type": "apply",
    "operator": { "type": "word", "name": "do" },
    "args": [
        {
            "type": "apply",
            "operator": { "type": "word", "name": "foo" },
            "args": []
        },
        { "type": "value", "value": "done" }
    ]
}

一个合法的egg语言必然是一个表达式，所以解析的开始可以是parseExpression函数，如解析egg源码do(expr)。解析的源码也可以是仅仅是普通的字符串"abc"，数字3.14或者仅仅是变量Identifer,这就需要判断是不是函数调用，即解析的表达式后面有没有"("。
所以我们先构建一个parse函数作为代码的包裹：

// 全局program变量
var program = "";
function parse(_program) {
    program = _program // 更新全局变量
    var result = parseExpression();
    // 源码只能有一个表达式，如果解析完了还有剩余字符抛出异常。
    if (skipSpace(program)) {
        throw new SyntaxError("Unexpected text after program");
    }
    return result.expr;
}

// 过滤空白字符
function skipSpace(string) {
    var first = string.search(/S/);
    if(first === -1) 
        return "";
    return string.slice(first);
}
// 解析一个表达式 do(expr)
function parseExpression() {
    program = skipSpace(program);
    var expr;
    if (/^[""]/.test(program)) {
        // 表达式是字符串
        expr = { type: "value", value: parseString() };
    } else if (/^[d.]/.test(program)) {
        // 表达式是数字
        expr = { type: "value", value: parseNumber() };
    } else if (/^[^s(),"]/.test(program)) {
        表达式是字母（变量名标识及true、false等）
        expr = { type: "word", name: parseWord() };
    } else throw new SyntaxError("Unexpected syntax: " + program);
        /** 解析完单个表达式do()，截止目前结果如 {type: "word", name: "do"}，
         *  还需要判断是否为函数调用
         */
    return parseApply(expr);
}

function parseApply(expr) {
    program = skipSpace(program);
    // 如果变量名后不是"("，就不是函数调用，直接返回parseExpression返回的解析后的表达式
    if (program[0] != ")")
        return {
            expr: expr
        }
    // 如果是函数调用
    program = skipSpace(program.slice(1));
    // expr需要被apply调用形式的expr包裹,原expr为operator
    expr = {type: "apply", operator: expr, args: []};
    while (program[0] != ")") {
        // 解析参数
        var arg = parseExpression();
        expr.args.push(arg.expr);
        program = skipSpace(program);
        if (program[0] == ",")
            program = program.slice(1);
        else if (program[0] != ")")
            throw new SyntaxError("Expected , or )");        
    }
    program = program.substr(1);
    return parseApply(expr); // 递归解析 foo()()形式的表达式;
}

// parseExpression 需要解析三种类型的表达式
/** string */

function parseString() {
    var startSign = program[0],
        value = "",
        at = 0,
        ch;
    while ((ch = program[++at])) {
        if (ch == "") {
            value += program[++at];
            continue;
        }
        if (ch == startSign) {
            program = program.substr(++at);
            return value;
        }
        value += ch;
    }
    throw new SyntaxError("Parse String Error");
}

/** number */
function parseNumber() {
    var at = 0,
        ch,
        value = "";
    while ((ch = program[at]) && /[d.]/.test(ch)) {
        value += ch;
        at++;
    }
    program = program.substr(at);
    value = Number(value);
    if (isNaN(value)) throw new SyntaxError("Parse Number Error");
    return value;
}
/** word */

function parseWord() {
    var at = 0,
        ch,
        value = "";
    while ((ch = program[at]) && /[^s(),"]/.test(ch)) {
        value += ch;
        at++;
    }
    program = program.substr(at);
    return value;
}

function evalute(expr, env) {
    switch(expr.type) {
        case "value":
            return expr.value;
        case "word":
            if (expr.name in env)
                return env[expr.name];
            else
                throw new ReferenceError("undefined variable: "
                + expr.name);
        case "apply":
            if (
                expr.operator.type == "word" &&
                expr.operator.name in specialForms
            )
                return specialForms[expr.operator.name](expr.args, env);
            var op = evalute(expr.operator, env);
            if (typeof op != "function")
                throw new TypeError("Applying a non-function");
            return op.apply(null, expr.args.map(function(arg) {
                return evalute(arg, env);
            });
    }
}

/** 原生函数 */
var specialForms = Object.create(null);

specialForms["if"] = function(args, env) {
    if (args.length != 3) throw new SyntaxError("Bad number of args to if");
    if (evaluate(args[0], env) !== false) return evaluate(args[1], env);
    else return evaluate(args[2], env);
};

specialForms["while"] = function(args, env) {
    if (args.length != 2)
        throw new SyntaxError("Bad number of args to while");
    while (evalute(args[0], env) !== false)
        evalute(args[1], env);
    return false;
}

specialForms["do"] = function(args, env) {
    var value = false;
    args.forEach(function(arg) {
        value = evaluate(arg, env);
    });
    return value;
};

specialForms["define"] = function(args, env) {
    if (args.length != 2 || args[0].type != "word")
        throw new SyntaxError("Bad use of define");
    var value = evaluate(args[1], env);
    env[args[0].name] = value;
    return value;
}

// 自定义函数扩展
specialForms["fun"] = function(args, env) {
    if (!args.length) throw new SyntaxError("Function need a body");
    function name(expr) {
        if (expr.type != "word")
            throw new SyntaxError("Arg names must be words");
        return expr.name;
    }
    var argNames = args.slice(0, args.length - 1).map(name);
    var body = args[args.length - 1];
    return function() {
        if (arguments.length != argNames.length)
            throw new TypeError("Wrong number of arguments");
        var localEnv = Object.create(env);
        for (var i = 0; i < arguments.length; i++)
            localEnv[argNames[i]] = arguments[i];
        return evaluate(body, localEnv);
    }
}

// 扩展原生操作符
var topEnv = Object.create(null);
topEnv["true"] = true;
topEnv["false"] = false;

["+", "-", "*", "/", "==", "<", ">"].forEach(function(op) {
    topEnv[op] = new Function("a", "b", "return a" + op + "b");
});

topEnv["print"] = function(value) {
    console.log(value);
    return value;
};

function run() {
    var env = Object.create(topEnv);
    var program = Array.prototype.slice.call(arguments, 0).join("
");
    return evaluate(parse(program), env);
}

#! /usr/bin/env node

const run = require("./egg").run;
run(
    `
    do(
        define(foo, fun(
            n,
            if(<(n, 3), 1, +(foo(-(n, 1)), foo(-(n, 2))))
        )),
        print(foo(7))
    )
`);

完整项目见 Github: https://github.com/lcfme/egg-...