03.parser

03.ast.js

var AST = function() {};

AST.prototype.init = function() {
    this.p = {};
};

AST.prototype.walk = function(callback) {
    callback.call(this);

    var p = this.p;
    for (var key in p) {
        var ast = p[key];
        if (ast instanceof AST) {
            p[key].walk(callback);
        }
    }
};

AST.prototype.code = function() {
    var code = this._code();

    var type = this.type();
    var as = this.as;

    if ( as && (type !== as) ) {
        return type + '2' + as + '(' + code + ')';
    }

    return code;
};

AST.prototype.type = function() {
    return 'scalar';
};

AST.prototype.setTypes = function() {};

//  ---------------------------------------------------------------------------------------------------------------  //

var asts = {};

//  ---------------------------------------------------------------------------------------------------------------  //

(function() {

var _ctors = {};

AST.create = function(id) {
    var ctor = get(id);
    var ast = new ctor();

    ast.init();

    return ast;

    function get(id) {
        var ctor = _ctors[id];

        if (!ctor) {
            ctor = _ctors[id] = function() {};

            var proto = asts[id] || {};

            var options = proto.options || {};

            var base = (options.base) ? get(options.base) : AST;
            inherit(ctor, base, proto);

            if (options.mixin) {
                extend( proto, asts[options.mixin] )
            }

            ctor.prototype.id = id;
        }

        return ctor;
    }
};

function inherit(ctor, base, mixin) {
    var F = function() {};
    F.prototype = base.prototype;
    var proto = ctor.prototype = new F();
    ctor.prototype.constructor = ctor;

    if (mixin) {
        extend(proto, mixin);
    }

    return ctor;
};

function extend(dest) {
    for (var i = 1, l = arguments.length; i < l; i++) {
        var src = arguments[i];
        for (var key in src) {
            dest[key] = src[key];
        }
    }

    return dest;
};

})();

03.asts.js

asts.binop = {};

asts.binop._code = function() {
    return this.p.left.code() + ' ' + this.p.op + ' ' + this.p.right.code();
};

//  Сигнатуры:
//
//      || &&       b b -> b
//      == !=       * * -> b
//      < <= >= >   s s -> b
//      + - * /     s s -> s
//

asts.binop.type = function() {
    return 'boolean';
};

asts.binop.setTypes = function() {
    this.p.left.as = 'scalar';
    this.p.right.as = 'scalar';
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.or = {
    options: {
        base: 'binop'
    }
};

asts.or.setTypes = function() {
    this.p.left.as = 'boolean';
    this.p.right.as = 'boolean';

};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.and = {
    options: {
        base: 'binop'
    }
};

asts.and.setTypes = asts.or.setTypes;

//  ---------------------------------------------------------------------------------------------------------------  //

asts.eq = {
    options: {
        base: 'binop'
    }
};

asts.eq.setTypes = function() {
    var left = this.p.left;
    var right = this.p.right;

    if (left.type() !== 'scalar' || right.type() !== 'scalar') {
        left.as = 'boolean';
        right.as = 'boolean';
    }
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.rel = {
    options: {
        base: 'binop'
    }
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.add = {
    options: {
        base: 'binop'
    }
};

asts.add.type = function() {
    return 'scalar';
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.mul = {
    options: {
        base: 'binop'
    }
};

asts.mul.type = function() {
    return 'scalar';
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.unop = {};

asts.unop._code = function() {
    return this.p.op + '(' + this.p.expr.code() + ')';
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.minus = {
    options: {
        base: 'unop'
    }
};

asts.minus.setTypes = function() {
    this.p.expr.as = 'scalar';
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.not = {
    options: {
        base: 'unop'
    }
};

asts.not.type = function() {
    return 'boolean';
};

asts.not.setTypes = function() {
    this.p.expr.as = 'boolean';
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.subexpr = {};

asts.subexpr._code = function() {
    return '(' + this.p.expr.code() + ')';
};

asts.subexpr.type = function() {
    return this.p.expr.type();
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.number = {};

asts.number._code = function() {
    return this.p.value;
};

//  ---------------------------------------------------------------------------------------------------------------  //

asts.var_ = {};

asts.var_.code = function() {
    return 'vars["' + this.p.name + '"]';
};

//  ---------------------------------------------------------------------------------------------------------------  //

03.grammar.js

var tokens = {};

tokens.ADD = /^[+-]/;
tokens.MUL = /^[*/%]/;
tokens.EQ = /^(==|!=)/;
tokens.REL = /^(<=|>=|<|>)/;
tokens.DIGIT = /^[0-9]/;
tokens.NUMBER = /^[0-9]+(\.[0-9]+)?/;
tokens.ID = /^[A-Za-z_][A-Za-z0-9_-]*/;

//  ---------------------------------------------------------------------------------------------------------------  //

var rules = {};

rules.expr = function() {
    return this.match('or');
};

rules.or = function(p) {
    p.left = this.match('and');

    if ( this.test('||') ) {
        p.op = this.match('||');
        p.right = this.match('or')
    } else {
        return p.left;
    }
};

rules.and = function(p) {
    p.left = this.match('eq');

    if ( this.test('&&') ) {
        p.op = this.match('&&');
        p.right = this.match('and')
    } else {
        return p.left;
    }
};

rules.eq = function(p) {
    p.left = this.match('rel');

    if ( this.test('EQ') ) {
        p.op = this.match('EQ');
        p.right = this.match('and')
    } else {
        return p.left;
    }
};

rules.rel = function(p) {
    p.left = this.match('add');

    if ( this.test('REL') ) {
        p.op = this.match('REL');
        p.right = this.match('rel')
    } else {
        return p.left;
    }
};

rules.add = function(p) {
    p.left = this.match('mul');

    if ( this.test('ADD') ) {
        p.op = this.match('ADD');
        p.right = this.match('add')
    } else {
        return p.left;
    }
};

rules.mul = function(p) {
    p.left = this.match('minus');

    if ( this.test('MUL') ) {
        p.op = this.match('MUL');
        p.right = this.match('mul')
    } else {
        return p.left;
    }
};

rules.minus = function(p) {
    if ( this.test('-') ) {
        p.op = this.match('-');
        p.expr = this.match('minus');
    } else {
        return this.match('not');
    }
};

rules.not = function(p) {
    if ( this.test('!') ) {
        p.op = this.match('!');
        p.expr = this.match('not');
    } else {
        return this.match('primary');
    }
};

rules.primary = function() {
    if ( this.test('(') ) {
        return this.match('subexpr');
    }

    if ( this.test('DIGIT') ) {
        return this.match('number');
    }

    return this.match('var_');
};

rules.subexpr = function(p) {
    this.match('(');
    p.expr = this.match('expr');
    this.match(')');
};

rules.number = function(p) {
    p.value = +this.match('NUMBER');
};

rules.var_ = function(p) {
    p.name = this.match('ID');
};

03.parser.html

<!doctype html>
<html>
<head>
    <meta charset="utf-8">
    <title>parser.03</title>
    <script src="03.ast.js"></script>
    <script src="03.asts.js"></script>
    <script src="03.grammar.js"></script>
    <script src="03.parser.js"></script>
</head>
<body>

<script>
function ast2func(ast) {
    return Function('vars', 'return (' + ast.code() + ');');
}

var grammar = {
    tokens: tokens,
    rules: rules
};
var parser = new Parser(grammar);

parse('2 * 3 + 4 - 5');
parse('!!3');
parse('(3 > 2) + 4');
parse('(3 > 2) != 4');
parse('a * a + b * b', { a: 3, b: 4 });

function parse(s, vars) {
    var ast = parser.parse(s, 'expr');
    var f = ast2func(ast);

    ast.walk(function() {
        this.setTypes();
    });

    console.log( ast.code(), ast.type() );
    console.log( f(vars) );
}
</script>

</body>
</html>

03.parser.js

function Parser(grammar) {
    this._patterns = {};

    this._addTokens( grammar.tokens || {} );
    this._addRules( grammar.rules || {} );
};

Parser.prototype._addTokens = function(tokens) {
    for (var id in tokens) {
        this._addToken( id, tokens[id] );
    }
};

Parser.prototype._addToken = function(id, token) {
    var compiled;

    if (typeof token === 'string') {
        var l = token.length;

        compiled = function() {
            if (this.current.substr(0, l) !== token) {
                this.error('Expected token: ' + id);
            }
            this.move(l);
            this.skip();

            return token;
        };
    } else {
        compiled = function() {
            var r = token.exec(this.current);
            if (!r) {
                this.error('Expected token: ' + id);
            }

            var s = r[0];
            this.move(s.length);
            this.skip();

            return s;
        };
    }

    this._patterns[id] = compiled;

    return compiled;
};

Parser.prototype._addRules = function(rules) {
    var patterns = this._patterns;

    for (var id in rules) {
        (function(id, rule) {
            patterns[id] = function() {
                var ast = AST.create(id);
                var r = rule.call(this, ast.p, ast);

                return (r === undefined) ? ast : r;
            };
        })( id, rules[id] );
    }
};

Parser.prototype.parse = function(input, id) {
    this.input = input;
    this.p = 0;
    this.current = input;

    var ast = this.match(id);

    /*
    if (this.current) {
        this.error('End of string expected');
    }
    */

    return ast;
};

Parser.prototype.match = function(id) {
    // console.log('match', id, this.current);
    var r = this._get(id).call(this);

    this.skip();

    return r;
};

Parser.prototype.test = function(id) {
    var r = true;
    var p = this.p;
    try {
        this._get(id).call(this);
    } catch (e) {
        r = false;
    }
    this.p = p;
    this.current = this.input.substr(p);

    return r;
};

Parser.prototype.skip = function() {
    var r = /^\s+/.exec(this.current);
    if (r) {
        this.move(r[0].length);
    }
};

Parser.prototype.move = function(n) {
    this.p += n;
    this.current = this.current.substr(n);
};

Parser.prototype.error = function(msg) {
    throw 'ERROR: ' + msg + ', at position ' + this.p;
};

Parser.prototype._get = function(id) {
    var pattern = this._patterns[id];

    if (!pattern) {
        pattern = this._addToken(id, id);
    }

    return pattern;
};