top-down-parser.js

function parseNumber(str) {
    const m = str.match(/^-?\d+/);
    if (!m) {
        throw new SyntaxError('not a number at ' + str);
    }
    const number = m[0];
    return {
        ast: { type: 'number', value: parseInt(number, 10) },
        rest: str.substr(number.length)
    };
}

const parseSum = (str) => parseBinop(str, /[+-]/, parseSum, parseFactor);
const parseFactor = (str) => parseBinop(str, /[*/]/, parseFactor, parsePrimitive);

function parseBrackets(str) {
    const rest = str.substr(1);
    const insides = rest[0] === '(' ? parseBrackets(rest) : parseSum(rest);

    if (insides.rest[0] !== ')') {
        throw new SyntaxError('Expected ) at' + insides.rest);
    }

    return { ast: insides.ast, rest: insides.rest.substr(1) };
}

function parseFunctionCall(str) {
    const m = str.match(/^([_a-z][_a-z0-9]*)\(/);
    if (!m) {
        throw new SyntaxError("Expected function name");
    }

    const args = [];
    let rest = str.substr(m[0].length);

    if (rest[0] !== ')') {
        let arg;
        while (true) {
            arg = parse(rest);
            args.push(arg.ast);

            const nextChar = arg.rest[0];
            rest = arg.rest.substr(1);

            if (nextChar === ')') break;
            if (nextChar !== ',') {
                throw new SyntaxError('Expected ) or , after an argument at ' + arg.rest);
            }
        }
    }

    return {
        ast: {
            type: 'call',
            name: m[1],
            args: args
        },
        rest: rest
    };
}

function parsePrimitive(str) {
    if (str[0] === '(') {
        return parseBrackets(str);
    }
    if (/^\d/.test(str)) {
        return parseNumber(str);
    }
    if (/^[_a-z]/.test(str)) {
        return parseFunctionCall(str);
    }
    throw new SyntaxError('Expected number or brackets at ' + str);
}

function parse(str) {
    return str[0] === '(' ? parseBrackets(str) : parseSum(str);
}

function display(ast) {
    switch (ast.type) {
        case 'number': return ast.value;
        case 'binop': return `(${display(ast.lhs)}${ast.op}${display(ast.rhs)})`;
        case 'call': return `${ast.name}(${ast.args.map(display).join(',')})`;
    }

    throw new Error('wtf');
}


const functions = {
    fn(a, b, c) { return a + b + c; }
};

function evaluate(ast) {
    switch (ast.type) {
        case 'number': return ast.value;
        case 'binop': {
            const lhsValue = evaluate(ast.lhs);
            const rhsValue = evaluate(ast.rhs);
            switch (ast.op) {
                case '+': return lhsValue + rhsValue;
                case '-': return lhsValue - rhsValue;
                case '*': return lhsValue * rhsValue;
                case '/': return lhsValue / rhsValue;
                default: throw new Error('Bad binary operation ' + ast.op);
            }
        }
        case 'call': {
            const args = ast.args.map(evaluate);
            if (!functions[ast.name]) {
                throw new Error('Bad function: ' + ast.name);
            }
            return functions[ast.name](...args);
        }
    }

    throw new Error('wtf');
}

const result = parse('1*fn(10,20+(42/7+4),30)+3*4+5*6*7');
if (result.rest) {
    console.log('Leftovers: ' + result.rest);
}
console.log(display(result.ast) + ' => ' + evaluate(result.ast));
console.dir(result.ast, { depth: Infinity });


function parseBinop(str, validOps, parseSelf, parseNext) {
    const lhs = parseNext(str);
    const nextChar = lhs.rest[0];

    if (!nextChar || !validOps.test(nextChar)) {
        return lhs;
    }

    const rhs = parseSelf(lhs.rest.substr(1));

    return {
        ast: {
            type: 'binop',
            op: nextChar,
            lhs: lhs.ast,
            rhs: rhs.ast
        },
        rest: rhs.rest
    };
}