// expr -> subexpr expr1
// subexpr -> Int
//         -> "(" expr ")"
// expr1 -> null
//       -> "+" expr
//       -> "*" expr

record OpenParen { }
record CloseParen { }
record Plus { }
record Times { }
record EOF { }

variant Token = OpenParen | CloseParen | Plus | Times | Int | EOF;

alias ExprPtr = SharedPointer[Expression];

record PlusNode { a: ExprPtr; b: ExprPtr; }
record TimesNode { a: ExprPtr; b: ExprPtr; }

variant Expression = PlusNode | TimesNode | Int;

newExpr(v) r: SharedPointer[Expression] {
    r <-- allocateShared(Expression(v));
}

record BadParse {}
instance Exception = BadParse;

nextToken(iter) {
    if (hasNext?(iter)) {
        return next(iter);
    } else {
        return Token(EOF());
    }
}

expectToken(iter, T) {
    var t = nextToken(iter);
    if (not variantIs?(t, T)) {
        println("unexpected token ", t, " should be ", T);
        throw BadParse();
    }
}

subexpr(a, iter) ExprPtr { println("subexpr bad token ", a); throw BadParse(); }
overload subexpr(a: Int, iter) ExprPtr = newExpr(a);
overload subexpr(a: OpenParen, iter) ExprPtr = expr(*nextToken(iter), iter);

expr(a, iter) ExprPtr {
    var aa = subexpr(a, iter);
    return expr1(*nextToken(iter), iter, aa);
}

expr1(b, iter, a) ExprPtr { println("expr1 bad token ", b); throw BadParse(); }
overload expr1(b: Plus, iter, a) ExprPtr = newExpr(PlusNode(a, expr(*nextToken(iter), iter)));
overload expr1(b: Times, iter, a) ExprPtr = newExpr(TimesNode(a, expr(*nextToken(iter), iter)));
overload expr1(b: EOF, iter, a) ExprPtr = a;
overload expr1(b: CloseParen, iter, a) ExprPtr = a;

parse(sequence) {
    var iter = iterator(sequence);
    return expr(*nextToken(iter), iter);
}

overload printTo(stream, x:ExprPtr) { printTo(stream, *(x^)); }
overload printTo(stream, x:PlusNode) { printTo(stream, "(", x.a, " + ", x.b, ")"); }
overload printTo(stream, x:TimesNode) { printTo(stream, "(", x.a, " * ", x.b, ")"); }

main() {
    println(parse([Token(1), Token(Plus()), Token(2)]));
    println(parse([Token(1), Token(Plus()), Token(2), Token(Times()), Token(3)]));
    println(parse([Token(1), Token(Plus()), Token(OpenParen()), Token(2), Token(Times()), Token(3), Token(CloseParen())]));
    println(parse([Token(1), Token(Times()), Token(2), Token(Plus()), Token(3)]));
    println(parse([Token(OpenParen()), Token(1), Token(Plus()), Token(2), Token(CloseParen()), Token(Times()), Token(3)]));
    println(parse([Token(OpenParen()), Token(1), Token(Plus()), Token(2), Token(CloseParen()), Token(Times()), Token(3)]));
}