Calc1.hx

import Calc1Parser;

enum Term {
    Mul(a: Term, b: Int);
    Div(a: Term, b: Int);
    Term_Int(a: Int);
}

enum Expr {
    Add(a: Expr, b: Term);
    Sub(a: Expr, b: Term);
    Expr_Term(a: Term);
}

class SemanticAction {
    public function new() {}
    public function stackOverflow() {}
    public function syntaxError() {}

    public function makeAdd(a: Expr, b: Term): Expr {
        return Add(a, b);
    }
    public function makeSub(a: Expr, b: Term): Expr {
        return Sub(a, b);
    }
    public function makeExpr(a: Term): Expr {
        return Expr_Term(a);
    }
    public function makeMul(a: Term, b: Int): Term {
        return Mul(a, b);
    }
    public function makeDiv(a: Term, b: Int): Term {
        return Div(a, b);
    }
    public function makeTerm(a: Int): Term {
        return Term_Int(a);
    }
}

class Calc1 {
    static function scanner(s: String) {
        var r = ~/^\s*/;
        r.match(s);
        s = r.matchedRight();
        trace(s);
    
        if (s.length == 0) {
            return { token: Token.Eof, value: null, rest: '' };
        }
    
        switch(s.charAt(0)) {
            case '+': return { token: Add, value: null, rest: s.substr(1) };
            case '-': return { token: Sub, value: null, rest: s.substr(1) };
            case '*': return { token: Mul, value: null, rest: s.substr(1) };
            case '/': return { token: Div, value: null, rest: s.substr(1) };
        }
        r = ~/^\d+/;
        if (r.match(s)) {
            s = r.matchedRight();
            return {
                token: Token.Number,
                value: Std.parseInt(r.matched(0)),
                rest: s
            };
        }
        throw "unknown char";
    }

    static function parse(s) {
        var parser = new Calc1Parser.Parser(new SemanticAction());

        while(true) {
            var a = scanner(s);
            trace(a);
            if (parser.post(a.token, a.value)) {
                break;
            }
            s = a.rest;
        }
        trace(parser.accept());
    }

    public static function main(): Void {
        parse('3+7*8+2');
    }
}

Calc1Parser.hx

// This file was automatically generated by Caper.
// (http://jonigata.github.io/caper/caper.html)



import haxe.ds.Option;
import Calc1;

enum Token {
    Eof;
    Add;
    Div;
    Mul;
    Number;
    Sub;
}

class TokenLabels {
    public static function get(t: Token): String {
        return switch(t) {
            case Eof: "Eof";
            case Add: "Add";
            case Div: "Div";
            case Mul: "Mul";
            case Number: "Number";
            case Sub: "Sub";
        }
    }
}

class Stack {
    var stack: Array<StackFrame> = [];
    var tmp: Array<StackFrame> = [];
    var gap: Int;

    public function new() { this.gap = 0; }

    public function rollbackTmp() {
        this.gap = this.stack.length;
        this.tmp = [];
    }

    public function commitTmp() {
        this.stack.splice(gap, this.stack.length - gap);

        for (e in this.tmp) {
            this.stack.push(e);
        }
        this.tmp = [];
    }
    public function push(f: StackFrame): Bool {
        this.tmp.push(f);
        return true;
    }
	   
    public function pop(n: Int) {
        if (this.tmp.length < n) {
            n -= this.tmp.length;
            this.tmp = [];
            this.gap -= n;
        } else {
            this.tmp.splice(-n, n);
        }
    }

    public function top(): StackFrame {
        //assert(0 < depth());
        if (0 < this.tmp.length) {
            return this.tmp[this.tmp.length - 1];
        } else {
            return this.stack[this.gap - 1];
        }
    }
	   
    public function getArg(base: Int, index: Int): StackFrame {
        var n = tmp.length;
        if (base - index <= n) {
            return this.tmp[n - (base - index)];
        } else {
            return this.stack[this.gap - (base - n) + index];
        }
    }
	   
    public function clear() {
        this.stack = [];
        this.tmp = [];
        this.gap = 0; 
    }
	   
    public function empty(): Bool {
        if (0 < this.tmp.length) {
            return false;
        } else {
            return this.gap == 0;
        }
    }
	   
    public function depth(): Int {
        return this.gap + this.tmp.length;
    }
	   
    public function nth(index: Int): StackFrame {
        if (this.gap <= index) {
            return this.tmp[index - this.gap];
        } else {
            return this.stack[index];
        }
    }

    public function setNth(index: Int, t: StackFrame) {
        if (this.gap <= index) {
            this.tmp[index - this.gap] = t;
        } else {
            this.stack[index] = t;
        }
    }

    public function swapTopAndSecond() {
        var d = depth();
        //assert(2 <= d);
        var x = nth(d - 1);
        setNth(d - 1, nth(d - 2));
        setNth(d - 2, x);
    }

}

private typedef State = Parser->Token->Dynamic->Bool;
private typedef Gotof = Nonterminal->Int;

private typedef TableEntry = {
    state: Int,
    gotof: Int,
    handleError: Bool,
};

private typedef StackFrame = {
    entry: TableEntry,
    value: Dynamic,
    sequenceLength: Int,
};

private typedef Range = {
    begin: Int,
    end: Int,
};

private enum Nonterminal {
    Nonterminal_Expr;
    Nonterminal_Term;
}
private typedef SemanticAction = {
    function syntaxError(): Void;
    function stackOverflow(): Void;
    function makeAdd(arg0: Expr, arg1: Term): Expr;
    function makeSub(arg0: Expr, arg1: Term): Expr;
    function makeExpr(arg0: Term): Expr;
    function makeTerm(arg0: Int): Term;
    function makeDiv(arg0: Term, arg1: Int): Term;
    function makeMul(arg0: Term, arg1: Int): Term;
}

class Parser{

    public function new(sa: SemanticAction){ this.sa = sa; reset(); }

    public function reset() {
        this.failed = false;
        this.accepted = false;
        this.stack = new Stack();
        rollbackTmpStack();
        if (pushStack(0, null)) {
            commitTmpStack();
        } else {
            this.sa.stackOverflow();
            this.failed = true;
        }
    }

    public function post(token: Token, value: Dynamic): Bool {
        rollbackTmpStack();
        this.failed = false;
        while(state_table(stackTop().entry.state, this, token, value)){ }
        if (!this.failed) {
            commitTmpStack();
        } else {
            recover(token, value);
        }
        return this.accepted || this.failed;
    }

    public function accept(): Dynamic {
        //assert(this.accepted);
        if (this.failed) { return null; }
        return this.acceptedValue;
    }

    public function error(): Bool { return this.failed; }


    var accepted: Bool;
    var failed: Bool;
    var acceptedValue: Dynamic;

    var sa: SemanticAction;

    var stack: Stack;

    function pushStack(stateIndex: Int, v: Dynamic, sl: Int = 0): Bool {
	var f = this.stack.push({
            entry: entry(stateIndex),
            value: v,
            sequenceLength: sl
        });
        //assert(!this.failed);
        if (!f) { 
            this.failed = true;
            this.sa.stackOverflow();
        }
        return f;
    }

    function popStack(n: Int) {
        this.stack.pop(n);
    }

    function stackTop(): StackFrame {
        return this.stack.top();
    }

    function getArg(base: Int, index: Int): Dynamic {
        return this.stack.getArg(base, index).value;
    }

    function clearStack() {
        this.stack.clear();
    }

    function rollbackTmpStack() {
        this.stack.rollbackTmp();
    }

    function commitTmpStack() {
        this.stack.commitTmp();
    }

    function recover(t: Token, v: Dynamic) {
    }

    function call_nothing(nonterminal: Nonterminal, base: Int): Bool {
        popStack(base);
        var dest_index = gotof_table(stackTop().entry.gotof, nonterminal);
        return pushStack(dest_index, null);
    }

    function call_0_makeAdd(nonterminal: Nonterminal, base: Int, argIndex0: Int, argIndex1: Int): Bool {
        var arg0 = getArg(base, argIndex0);
        var arg1 = getArg(base, argIndex1);
        var r = this.sa.makeAdd(arg0, arg1);
        popStack(base);
        var dest_index = gotof_table(stackTop().entry.gotof, nonterminal);
        return pushStack(dest_index, r);
    }

    function call_0_makeSub(nonterminal: Nonterminal, base: Int, argIndex0: Int, argIndex1: Int): Bool {
        var arg0 = getArg(base, argIndex0);
        var arg1 = getArg(base, argIndex1);
        var r = this.sa.makeSub(arg0, arg1);
        popStack(base);
        var dest_index = gotof_table(stackTop().entry.gotof, nonterminal);
        return pushStack(dest_index, r);
    }

    function call_0_makeExpr(nonterminal: Nonterminal, base: Int, argIndex0: Int): Bool {
        var arg0 = getArg(base, argIndex0);
        var r = this.sa.makeExpr(arg0);
        popStack(base);
        var dest_index = gotof_table(stackTop().entry.gotof, nonterminal);
        return pushStack(dest_index, r);
    }

    function call_0_makeTerm(nonterminal: Nonterminal, base: Int, argIndex0: Int): Bool {
        var arg0 = getArg(base, argIndex0);
        var r = this.sa.makeTerm(arg0);
        popStack(base);
        var dest_index = gotof_table(stackTop().entry.gotof, nonterminal);
        return pushStack(dest_index, r);
    }

    function call_0_makeDiv(nonterminal: Nonterminal, base: Int, argIndex0: Int, argIndex1: Int): Bool {
        var arg0 = getArg(base, argIndex0);
        var arg1 = getArg(base, argIndex1);
        var r = this.sa.makeDiv(arg0, arg1);
        popStack(base);
        var dest_index = gotof_table(stackTop().entry.gotof, nonterminal);
        return pushStack(dest_index, r);
    }

    function call_0_makeMul(nonterminal: Nonterminal, base: Int, argIndex0: Int, argIndex1: Int): Bool {
        var arg0 = getArg(base, argIndex0);
        var arg1 = getArg(base, argIndex1);
        var r = this.sa.makeMul(arg0, arg1);
        popStack(base);
        var dest_index = gotof_table(stackTop().entry.gotof, nonterminal);
        return pushStack(dest_index, r);
    }

    static function state_0(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_0 << ' + TokenLabels.get(token));
        switch(token) {
        case Number:
            // shift
            self.pushStack(/*state*/ 7, value);
            return false;
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_0(nonterminal: Nonterminal): Int {
        switch(nonterminal) {
        case Nonterminal_Expr: return 1;
        case Nonterminal_Term: return 2;
        default: /*assert(0);*/ return -1;
        }
    }

    static function state_1(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_1 << ' + TokenLabels.get(token));
        switch(token) {
        case Eof:
            // accept
            self.accepted = true;
            self.acceptedValue = self.getArg(1, 0);
            return false;
        case Add:
            // shift
            self.pushStack(/*state*/ 3, value);
            return false;
        case Sub:
            // shift
            self.pushStack(/*state*/ 5, value);
            return false;
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_1(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_2(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_2 << ' + TokenLabels.get(token));
        switch(token) {
        case Div:
            // shift
            self.pushStack(/*state*/ 10, value);
            return false;
        case Mul:
            // shift
            self.pushStack(/*state*/ 8, value);
            return false;
        case Eof | Add | Sub:
            // reduce
            return self.call_0_makeExpr(Nonterminal_Expr, /*pop*/ 1, 0);
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_2(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_3(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_3 << ' + TokenLabels.get(token));
        switch(token) {
        case Number:
            // shift
            self.pushStack(/*state*/ 7, value);
            return false;
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_3(nonterminal: Nonterminal): Int {
        switch(nonterminal) {
        case Nonterminal_Term: return 4;
        default: /*assert(0);*/ return -1;
        }
    }

    static function state_4(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_4 << ' + TokenLabels.get(token));
        switch(token) {
        case Div:
            // shift
            self.pushStack(/*state*/ 10, value);
            return false;
        case Mul:
            // shift
            self.pushStack(/*state*/ 8, value);
            return false;
        case Eof | Add | Sub:
            // reduce
            return self.call_0_makeAdd(Nonterminal_Expr, /*pop*/ 3, 0, 2);
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_4(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_5(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_5 << ' + TokenLabels.get(token));
        switch(token) {
        case Number:
            // shift
            self.pushStack(/*state*/ 7, value);
            return false;
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_5(nonterminal: Nonterminal): Int {
        switch(nonterminal) {
        case Nonterminal_Term: return 6;
        default: /*assert(0);*/ return -1;
        }
    }

    static function state_6(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_6 << ' + TokenLabels.get(token));
        switch(token) {
        case Div:
            // shift
            self.pushStack(/*state*/ 10, value);
            return false;
        case Mul:
            // shift
            self.pushStack(/*state*/ 8, value);
            return false;
        case Eof | Add | Sub:
            // reduce
            return self.call_0_makeSub(Nonterminal_Expr, /*pop*/ 3, 0, 2);
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_6(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_7(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_7 << ' + TokenLabels.get(token));
        switch(token) {
        case Eof | Add | Div | Mul | Sub:
            // reduce
            return self.call_0_makeTerm(Nonterminal_Term, /*pop*/ 1, 0);
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_7(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_8(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_8 << ' + TokenLabels.get(token));
        switch(token) {
        case Number:
            // shift
            self.pushStack(/*state*/ 9, value);
            return false;
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_8(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_9(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_9 << ' + TokenLabels.get(token));
        switch(token) {
        case Eof | Add | Div | Mul | Sub:
            // reduce
            return self.call_0_makeMul(Nonterminal_Term, /*pop*/ 3, 0, 2);
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_9(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_10(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_10 << ' + TokenLabels.get(token));
        switch(token) {
        case Number:
            // shift
            self.pushStack(/*state*/ 11, value);
            return false;
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_10(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static function state_11(self: Parser, token: Token, value:  Dynamic): Bool {
        trace('state_11 << ' + TokenLabels.get(token));
        switch(token) {
        case Eof | Add | Div | Mul | Sub:
            // reduce
            return self.call_0_makeDiv(Nonterminal_Term, /*pop*/ 3, 0, 2);
        default:
            self.sa.syntaxError();
            self.failed = true;
            return false;
        }
    }

    static function gotof_11(nonterminal: Nonterminal): Int {
        //assert(0);
        return -1;
    }

    static var entries = [
        { state: 0, gotof: 0, handleError: false },
        { state: 1, gotof: 1, handleError: false },
        { state: 2, gotof: 2, handleError: false },
        { state: 3, gotof: 3, handleError: false },
        { state: 4, gotof: 4, handleError: false },
        { state: 5, gotof: 5, handleError: false },
        { state: 6, gotof: 6, handleError: false },
        { state: 7, gotof: 7, handleError: false },
        { state: 8, gotof: 8, handleError: false },
        { state: 9, gotof: 9, handleError: false },
        { state: 10, gotof: 10, handleError: false },
        { state: 11, gotof: 11, handleError: false },
    ];
	
	static function gotof_table(index:Int, nonterminal: Nonterminal):Int {
		return switch index {
			case 0: gotof_0(nonterminal);
			case 1: gotof_1(nonterminal);
			case 2: gotof_2(nonterminal);
			case 3: gotof_3(nonterminal);
			case 4: gotof_4(nonterminal);			
			case 5: gotof_5(nonterminal);
			case 6: gotof_6(nonterminal);
			case 7: gotof_7(nonterminal);
			case 8: gotof_8(nonterminal);
			case 9: gotof_9(nonterminal);
			case 10: gotof_10(nonterminal);
			case 11: gotof_11(nonterminal);
			case _: throw "invalid";
		}
	}

	static function state_table(index:Int, self:Parser, token:Token, value:Dynamic):Bool {
		return switch index {
			case 0: state_0(self,token,value);
			case 1: state_1(self,token,value);
			case 2: state_2(self,token,value);
			case 3: state_3(self,token,value);
			case 4: state_4(self,token,value);			
			case 5: state_5(self,token,value);
			case 6: state_6(self,token,value);
			case 7: state_7(self,token,value);
			case 8: state_8(self,token,value);
			case 9: state_9(self,token,value);
			case 10: state_10(self,token,value);
			case 11: state_11(self,token,value);
			case _: throw "invalid";
		}
	}	
	
    function entry(n: Int): TableEntry {
        return entries[n];
    }

}