using static System.Console;
using System.Text.RegularExpressions;

class Parser {
    List<string> tokens = [];
    int pos;

    public Parser(string input) {
        foreach (Match m in Regex.Matches(input, @"\d+|[a-z]+|[=!<>]+|\S"))
            tokens.Add(m.Value);
    }

    string next() => tokens[pos++];
    string? peek() => pos < tokens.Count ? tokens[pos] : null;

    bool match(string s) {
        if (peek() == s) {
            pos += 1;
            return true;
        }
        return false;
    }

    void assert(bool b) {
        if (!b) {
            WriteLine(string.Join("|", tokens[pos ..]));
            throw new Exception("syntax error");
        }
    }

    public Expr parse_paren_expr() {
        assert(match("("));
        Expr e = parse_expr();
        assert(match(")"));
        return e;
    }

    public Expr parse_primary() {
        if (peek() == "(")
            return parse_paren_expr();
        string t = next();
        if (t == "false" || t == "true")
            return new Const(new Bool(t == "true"));
        return int.TryParse(t, out int i) ? new Const(new Int(i)) : new Var(t);
    }

    public Expr parse_factor() {
        Expr e = parse_primary();
        while (peek() == "*" || peek() == "/" || peek() == "%")
            e = new BinOp(e, next(), parse_primary());
        return e;
    }

    public Expr parse_term() {
        Expr e = parse_factor();
        while (peek() == "+" || peek() == "-")
            e = new BinOp(e, next(), parse_factor());
        return e;
    }

    public Expr parse_comparison() {
        string[] compare_ops = ["==", "!=", "<", "<=", ">", ">="];
        Expr e = parse_term();
        if (compare_ops.Contains(peek()))
            e = new BinOp(e, next(), parse_term());
        return e;
    }

    public Expr parse_expr() => parse_comparison();

    public Stmt? parse_print() {
        if (match("print")) {
            Print p = new(parse_paren_expr());
            assert(match(";"));
            return p;
        }
        return null;
    }

    public Stmt parse_assignment() {
        string id = next();
        assert(match("="));
        Assign a = new(id, parse_expr());
        assert(match(";"));
        return a;
    }

    public Stmt parse_statement() =>
        parse_print() ?? parse_assignment();

    public List<Stmt> parse_statements() {
        List<Stmt> stmts = [];
        while (peek() != null)
            stmts.Add(parse_statement());
        return stmts;
    }

    public Block parse_program() => new(parse_statements());
}