/** Parser for Assignment 2 */

import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;
import java.util.LinkedList;

/**
 * Exception during parsing.
 */
class ParseException extends RuntimeException {
    /**
     * Constructor for an exception during parsing.
     * @param s description
     */
    ParseException(String s) {
        super(s);
    }
}

/**
 * Parser class.
 */
class Parser {
    /**
     * Lexer that delivers the tokens.
     */
    private Lexer in;

    /**
     * If keyword.
     */
    KeyWord ifKey;

    /**
     * Then keyword.
     */
    KeyWord thenKey;

    /**
     * Else keyword.
     */
    KeyWord elseKey;

    /**
     * Let keyword.
     */
    KeyWord letKey;

    /**
     * Letrec keyword.
     */
    KeyWord letrecKey;

    /**
     * In keyword.
     */
    KeyWord inKey;

    /**
     * Map keyword.
     */
    KeyWord mapKey;

    /**
     * To keyword.
     */
    KeyWord toKey;

    /**
     * Assign keyword.
     */
    KeyWord assignKey;

    /**
     * Constructor for a parser.
     * @param i lexer to use
     */
    Parser(Lexer i) {
        in = i;
        initParser();
    }

    /**
     * Constructor for a parser.
     * @param r reader to use
     */
    Parser(Reader r) {
        this(new Lexer(r));
    }

    /**
     * Constructor for a parser.
     * @param fileName file name
     * @throws IOException
     */
    Parser(String fileName) throws IOException {
        this(new FileReader(fileName));
    }

    /**
     * Accessor for the lexer.
     * @return lexer
     */
    Lexer lexer() {
        return in;
    }

    /**
     * Initialize the parser.
     */
    private void initParser() {
        ifKey = (KeyWord)in.wordTable.get("if");
        thenKey = (KeyWord)in.wordTable.get("then");
        elseKey = (KeyWord)in.wordTable.get("else");
        letKey = (KeyWord)in.wordTable.get("let");
        letrecKey = (KeyWord)in.wordTable.get("letrec");
        inKey = (KeyWord)in.wordTable.get("in");
        mapKey = (KeyWord)in.wordTable.get("map");
        toKey = (KeyWord)in.wordTable.get("to");
        assignKey = (KeyWord)in.wordTable.get(":=");
    }

    /**
     * Parse the tokens in the lexer and return the AST.
     * @return AST
     */
    public AST parse() {
        AST prog = parseExp();
        Token t = in.readToken();
        if (t == null) {
            return prog;
        }
        else {
            throw
            new ParseException("Legal program followed by extra token " + t);
        }
    }

    /**
     * Parse the tokens in the lexer, perform a context-sensitive check, and return the AST.
     * @return AST
     */
    public AST parseAndCheck() {
        AST prog = parseExp();
        Token t = in.readToken();
        if (t != null) {
            throw
            new ParseException("Legal program followed by extra token " + t);
        }
        prog.accept(CheckVisitor.INITIAL);   // aborts on an error by throwing an exception
        return prog;
    }

    /**
     * Parse an expression.
     * @return AST
     */
    private AST parseExp() {
        Token token = in.readToken();

        // <exp> :: = if <exp> then <exp> else <exp>
        //          | let <prop-def-list> in <exp>
        //          | map <id-list> to <exp>
        //          | <term> { <biop> <exp> }

        if (token == ifKey) {
            return parseIf();
        }
        // if (token == letrecKey) return parseLetRec();
        if (token == letKey) {
            return parseLet();
        }
        if (token == mapKey) {
            return parseMap();
        }

        /*  Supports the addition of blocks to Jam
         if (token == LeftBrace.ONLY) {
         AST[] exps = parseExps(SemiColon.ONLY,RightBrace.ONLY);
         // including closing brace
         if (exps.length == 0) throw new ParseException("Illegal empty block");
         return new Block(exps);
         }
         */

        AST term = parseTerm(token);
        Token next = in.peek();
        if (next instanceof OpToken) {
            OpToken op = (OpToken)next;
            in.readToken(); // remove next from input stream
            if (!(op.isBinOp())) {
                error(next, "binary operator");
            }
            AST exp = parseExp();
            return new BinOpApp(op.toBinOp(), term, exp);
        }

        // next not a binary operator
        return term;
    }

    /**
     * Parse a term.
     * @param token token just read
     * @return AST
     */
    private AST parseTerm(Token token) {

        // <term>     ::= { <unop> } <term> |
        //                <constant> |
        //                <factor> {( <exp-list> )}

        // <constant> ::= <null> | <int> | <bool>

        if (token instanceof OpToken) {
            OpToken op = (OpToken)token;
            if (!op.isUnOp()) {
                error(op, "unary operator");
            }
            return new UnOpApp(op.toUnOp(), parseTerm(in.readToken()));
        }
        if (token instanceof Constant) {
            return (Constant)token;
        }
        AST factor = parseFactor(token);
        Token next = in.peek();
        if (next == LeftParen.ONLY) {
            in.readToken();  // remove next from input stream
            AST[] exps = parseArgs();  // including closing paren
            return new App(factor, exps);
        }
        return factor;
    }

    /**
     * Parse a factor
     * @param token token just read
     * @return AST
     */
    private AST parseFactor(Token token) {

        // <factor>   ::= <prim> | <variable> | ( <exp> )

        if (token == LeftParen.ONLY) {
            AST exp = parseExp();
            token = in.readToken();
            if (token != RightParen.ONLY) {
                error(token, "`)'");
            }
            return exp;
        }
        if (!(token instanceof PrimFun) && !(token instanceof Variable)) {
            error(token, "constant, primitive, variable, or `('");
        }

        // Term\Constant = Variable or PrimFun
        return (Term)token;
    }

    /**
     * Parse an if construct.
     * @return AST
     */
    private AST parseIf() {
        // parses `if <exp> then <exp> else <exp>'
        // given that `if' has already been read

        AST test = parseExp();
        Token key1 = in.readToken();
        if (key1 != thenKey) {
            error(key1, "`then'");
        }
        AST conseq = parseExp();
        Token key2 = in.readToken();
        if (key2 != elseKey) {
            error(key2, "`else'");
        }
        AST alt = parseExp();
        return new If(test, conseq, alt);
    }

    /**
     * Parse a let construct
     * @return AST
     */
    private AST parseLet() {
        // parses `let <prop-def-list> in <exp>'
        // given that `let' has already been read

        Def[] defs = parseDefs(false);
        // consumes `in'; false means rhs may be non Map
        AST body = parseExp();
        return new Let(defs, body);
    }

    /*
     private AST parseLetRec() {
     // parses `letrec <prop-def-list> in <exp>'
     // given that `letrec' has already been read
   
     Def[] defs = parseDefs(true);
     // consumes `in'; true means each rhs must be a Map
     AST body = parseExp();
     return new LetRec(defs,body);
     }
     */

    /**
     * P{arse a map construct.
     * @return AST
     */
    private AST parseMap() {
        // parses `map <id-list> to <exp>'
        // given that `map' has already been read

        Variable[] vars = parseVars(); // consumes the delimiter `to'
        AST body = parseExp();
        return new Map(vars, body);
    }

    /**
     * Parse a list of expressions.
     * @param separator token that should separate the expressions
     * @param delim token that delimits the list
     * @return array of expressions
     */
    private AST[] parseExps(Token separator, Token delim) {
        // parses `<exp-list> <delim>'
        // where
        //   <exp-list>      ::= <empty> | <prop-exp-list>
        //   <empty> ::=
        //   <prop-exp-list> ::= <exp> | <exp> <separator> <prop-exp-list>

        LinkedList<AST> exps = new LinkedList<AST>();
        Token next = in.peek();
        if (next == delim) {
            in.readToken(); // consume RightParen
            return new AST[0];
        }

        // next is still at front of input stream

        do {
            AST exp = parseExp();
            exps.addLast(exp);
            next = in.readToken();
        } while(next == separator);
        if (next != delim) {
            error(next, "`,' or `)'");
        }
        return exps.toArray(new AST[0]);
    }

    /**
     * Parse arguments.
     * @return array of ASTs
     */
    private AST[] parseArgs() {
        return parseExps(Comma.ONLY, RightParen.ONLY);
    }

    /**
     * Parse variables.
     * @return list of variables.
     */
    private Variable[] parseVars() {

        // parses <id-list>
        // where
        //   <id-list>       ::= <empty> | <prop-id-list>
        //   <prop-id-list>  ::= <id> | <id> , <id-list>

        // NOTE: consumes `to' following <id-list>

        LinkedList<Variable> vars = new LinkedList<Variable>();
        Token t = in.readToken();
        if (t == toKey) {
            return new Variable[0];
        }
        do {
            if (!(t instanceof Variable)) {
                error(t, "variable");
            }
            vars.addLast((Variable)t);
            t = in.readToken();
            if (t == toKey) {
                break;
            }
            if (t != Comma.ONLY) {
                error(t, "`to' or `,'");
            }
            // Comma found, read next variable
            t = in.readToken();
        } while(true);
        return vars.toArray(new Variable[0]);
    }

    /**
     * Parse definitions.
     * @param forceMap true if right-hand sides need to be map constructs
     * @return array of definitions
     */
    private Def[] parseDefs(boolean forceMap) {
        // parses  `<prop-def-list> in'
        // where
        //   <prop-def-list> ::= <def> | <def> <def-list>

        // NOTE: consumes `in' following <prop-def-list>

        LinkedList<Def> defs = new LinkedList<Def>();
        Token t = in.readToken();
        do {
            Def d = parseDef(t);
            if (forceMap && (!(d.rhs() instanceof Map))) {
                throw new ParseException("right hand side of definition `" + d
                                         + "' is not a map expression");
            }
            defs.addLast(d);
            t = in.readToken();
        } while(t != inKey);
        return defs.toArray(new Def[0]);
    }

    /**
     * Parse a single definition.
     * @param var token just read
     * @return definition
     */
    private Def parseDef(Token var) {
        // parses <id> := <exp> ;
        // which is <def>
        // given that first token var has been read

        if (!(var instanceof Variable)) {
            error(var, "variable");
        }
        Token key = in.readToken();
        if (key != assignKey) {
            error(key, "`:='");
        }
        AST exp = parseExp();
        Token semi = in.readToken();
        if (semi != SemiColon.ONLY) {
            error(semi, "`;'");
        }
        return new Def((Variable)var, exp);
    }

    /**
     * Throw an exception.
     * @param found token found
     * @param expected what was expected
     */
    private void error(Token found, String expected) {
//        for(int i = 0; i < 10; i++) {
//            System.out.println(in.readToken());
//        }
        throw new ParseException("Token `" + found + "' appears where " +
                                 expected + " was expected");
    }

    /**
     * JVM entry point. Parse the specified file nad print out the AST.
     * @param args command line arguments
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        // check for legal argument list
        if (args.length == 0) {
            System.out.println("Usage: java Parser <filename>");
            return;
        }
        Parser p = new Parser(args[0]);
        AST prog = p.parse();
        System.out.println("Parse tree is: " + prog);
    }
}