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

egg编程语言

代码改自Eloquent Javascript: Chapter 12

egg编程语言遵循如下规范

• 语言只有表达式，没有语句，如加法：+(1, 7)，连续相加如+(1, +(2,3))
• 多个表达式用do包裹，如do(expr1, expr2, expr3, ..., exprN)
• 数据类型支持数字 布尔 字符串

代码实现：

parse

• 将源码字符串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;
}

evaluate

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('\n');
    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-...