import java.util.Vector;
import rebelsky.compiler.lexer.Token;
import rebelsky.compiler.lexer.TokenStream;
import rebelsky.compiler.misc.Symbol;
import rebelsky.compiler.parser.Node;
import rebelsky.compiler.parser.Parser;
import rebelsky.compiler.parser.ParseException;
import rebelsky.compiler.pascal.PascalIdentifier;
import rebelsky.compiler.pascal.PascalInteger;
import rebelsky.compiler.pascal.PascalNonterminals;
import rebelsky.compiler.pascal.PascalReal;
import rebelsky.compiler.pascal.PascalTokenizer;
import rebelsky.compiler.pascal.PascalTokens;

/**
 * A simple parser for a simple "assignment language".  A program
 * in this language consists of a sequence of variable declarations
 * followed by a sequence of assignment statements.
 *
 * Here's a simple BNF grammar for the language.  program is the
 * start symbol.
 *
 *   adding_operator ::= PLUS
 *   adding_operator ::= MINUS
 *   adding_operator ::= OR
 *
 *   assignment ::= variable ASSIGN expression
 *
 *   assignment_list ::= BEGIN assignment SEMI { assignment SEMI } END
 *
 *   expression ::= simple_expression
 *   expression ::= simple_expression relational_operator simple_expression
 *
 *   factor ::= ID
 *   factor ::= INTEGER
 *   factor ::= READ
 *   factor ::= OPENPAREN expression CLOSEPAREN
 *
 *   multiplying_operator ::= TIMES
 *   multiplying_operator ::= DIVIDE
 *   multiplying_operator ::= DIV
 *   multiplying_operator ::= MOD
 *   multiplying_operator ::= AND
 *
 *   program ::= variable_declarations assignment_list
 *
 *   relational_operator ::= EQUALS
 *   relational_operator ::= NOTEQUALS
 *   relational_operator ::= LESSTHAN
 *   relational_operator ::= LESSEQUAL
 *   relational_operator ::= GREATERTHAN
 *   relational_operator ::= GREATEREQUAL
 *
 *   simple_expression ::= term { adding_operator term }
 *
 *   term ::= factor { multiplying_operator factor }
 *
 *   unsigned_number ::= UINT
 *   unsigned_number ::= UREAL
 *
 *   variable ::= ID
 *
 *   variable_declaration ::= ID { COMMA ID } TCOLON identifier
 *
 *   variable_declarations ::= VAR variable_declaration SEMI
 *                             { variable_declaration SEMI }
 *
 * @author Samuel A. Rebelsky
 * @version 0.5 of October 2002
 */
public class AssignLangParser
  implements Parser
{
  // +---------------------------------------------------------------------
  // | Implementation Notes |
  // +--------+
/*
  I've implemented the language with a simple predictive parser.

  The parse tree I generate does not include many of the useless nodes
  (e.g., the terminals used only for parsing; terms, factors, and any 
  other nonterminals used for disambiguating; nonterminals whose primary
  purpose is to build lists).

  For nonterminals, such as variable_declarations, that can have a
  sequence of "children", I make only one node with lots of children,
  rather than a sequence of nodes.  Hence, the arity of something
  like variable_declarations is the number of declarations.
 */

  // +--------+------------------------------------------------------------
  // | Fields |
  // +--------+

  // +--------------+------------------------------------------------------
  // | Constructors |
  // +--------------+

  // +---------+-----------------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Parse a stream of tokens, advancing that stream as necessary.
   *
   * @exception ParseException
   *   If parsing fails.
   */
  public Node parse(TokenStream tokens)
    throws ParseException
  {
    if (!(tokens instanceof PascalTokenizer))
      boom("Can only parse with Pascal tokens.");
    try {
      return parseProgram((PascalTokenizer) tokens);
    }
    // The following few lines are something of a hack.  I
    // pass along parse exceptions and turn other exceptions
    // (e.g., TokenExceptions) to ParseExceptions.
    catch (ParseException e) { throw e; }
    catch (Exception e) { throw new ParseException(e.toString()); }
  } // parse(TokenStream)


  // +------------------------+--------------------------------------------
  // | Private Helper Methods |
  // +------------------------+

  /**
   * My favorite way of reporting errors.  Essentially, a shorthand
   * for "throw new ParseException(...)".
   */
  private void boom(String message)
    throws ParseException
  {
    throw new ParseException(message);
  } // boom(String)

  /**
   * Determine if a token is an additive operator.
   */
  private boolean isAddOp(Token tok) {
    return ( (tok == PascalTokens.TPLUS) 
             || (tok == PascalTokens.TMINUS) 
             || (tok == PascalTokens.TOR) );
  } // isAddOp(Token)

  /**
   * Determine if a token is a multiplicative operator.
   */
  private boolean isMulOp(Token tok) {
    return ( (tok == PascalTokens.TTIMES) 
             || (tok == PascalTokens.TDIVIDE) 
             || (tok == PascalTokens.TDIV) 
             || (tok == PascalTokens.TMOD) 
             || (tok == PascalTokens.TAND) );
  } // isMulOp(Token)

  /**
   * Determine if a token is a relational operator.
   */
  private boolean isRelOp(Token tok) {
    return ( (tok == PascalTokens.TEQUALS) 
             || (tok == PascalTokens.TNOTEQUALS) 
             || (tok == PascalTokens.TLESSTHAN) 
             || (tok == PascalTokens.TLESSEQ) 
             || (tok == PascalTokens.TGREATERTHAN) 
             || (tok == PascalTokens.TGREATEREQ) );
  } // isRelOp(Token)

  /**
   * Give up because the wrong token was found when expecting
   * something particular (a nonterminal or a terminal).
   */
  private Node wrongToken(Symbol expected, Token found)
    throws ParseException
  {
    throw new ParseException("Expected: " + expected.toString() + 
                             "; Found: " + found.toString());
  } // wrongToken(Symbol, Token)


  // +-----------------------+---------------------------------------------
  // | Private Parse Methods |
  // +-----------------------+

  /*
     Each of these procedures throws a ParseException for obvius
     reasons (that is, parsing failed).  Each can also throw a
     host of other exceptions, typically when tokenizing fails.
   */

  private Node parseAddingOperator(PascalTokenizer tokens) 
    throws ParseException,Exception
  {
    Token tok = tokens.peek();
    if (isAddOp(tokens.peek())) {
      return new Node(tokens.next(), null);
    }
    else {
      return wrongToken(PascalNonterminals.ADDING_OPERATOR, tok);
    }
  }  // parseAddingOperator(PascalTokenizer)

  private Node parseAssignment(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    Vector children = new Vector();
    // Parse the variable
    children.add(parseVariable(tokens));
    // Check for the assignment symbol
    if (tokens.peek() != PascalTokens.TASSIGN)
      return wrongToken(PascalNonterminals.ASSIGNMENT, tokens.peek());
    tokens.next();
    // Parse the expression
    children.add(parseExpression(tokens));
    // Build and return the assignment statement 
    return new Node(PascalNonterminals.ASSIGNMENT, children);
  } // parseAssignment(PascalTokenizer)

  private Node parseAssignmentList(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    // A vector to hold all the assignments in the list.
    Vector assignments = new Vector();
    // Preparation: Make sure everything starts with BEGIN
    if (tokens.peek() != PascalTokens.TBEGIN) 
      return wrongToken(PascalNonterminals.ASSIGNMENT_LIST, tokens.peek());
    tokens.next();

    // Get all the assignments and add them to the vector.
    do {     
      // Parse the assignment.
      assignments.add(parseAssignment(tokens));
      // Check for the semicolon.
      if (tokens.peek() != PascalTokens.TSEMI) 
        return wrongToken(PascalTokens.TSEMI, tokens.peek());
      // Consume the semicolon
      tokens.next();
      // Do we have another assignment next?  assignments start with
      // identifiers, so look for one.
    } while (tokens.peek() instanceof PascalIdentifier);

    // Cleanup: Make sure the END is there.
    if (tokens.peek() != PascalTokens.TEND) 
      return wrongToken(PascalNonterminals.ASSIGNMENT_LIST, tokens.peek());
    tokens.next();

    // Build the nice node.
    return new Node(PascalNonterminals.ASSIGNMENT_LIST, assignments);
  } // parseAssignmentList(PascalTokenizer)

  private Node parseExpression(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    // Expressions need to begin with simple expressions
    Node primary = parseSimpleExpression(tokens);
    // Expressions can sometimes have relational operators
    if (isRelOp(tokens.peek())) {
      Vector children = new Vector();
      children.add(primary);
      children.add(parseRelationalOperator(tokens));
      children.add(parseSimpleExpression(tokens));
      return new Node(PascalNonterminals.EXPRESSION, children);
    }
    // If there's no relational operator, stick with the current
    // expression
    else {
      return primary;
    }
  } // parseExpression(PascalTokenizer)

  private Node parseFactor(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    Token tok = tokens.peek();
    if ( (tok instanceof PascalIdentifier) 
         || (tok instanceof PascalInteger)
         || (tok instanceof PascalReal) ) {
      return new Node(tokens.next(), null);
    }
    else if (tok == PascalTokens.TOPENPAREN) {
      // Consume the open paren
      tokens.next();
      // Get the subexpression
      Node result = parseExpression(tokens);
      // Make sure the end paren is there.
      if (tokens.peek() != PascalTokens.TCLOSEPAREN) 
        return wrongToken(PascalTokens.TCLOSEPAREN, tokens.peek());
      tokens.next();
      // Don't forget to return the intermediate result
      return result;
    } // OPENPAREN
    else {
      // Whoops, something's wrong
      return wrongToken(PascalNonterminals.FACTOR, tokens.peek());
    }
  } // parseFactor(PascalTokenizer)

  private Node parseMultiplyingOperator(PascalTokenizer tokens) 
    throws ParseException,Exception
  {
    if (isMulOp(tokens.peek())) 
      return new Node(tokens.next(), null);
    else 
      return wrongToken(PascalNonterminals.MULTIPLYING_OPERATOR, tokens.peek());
  }  // parseMultiplyingOperator(PascalTokenizer)

  private Node parseProgram(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    Vector children = new Vector();
    children.add(parseVariableDeclarations(tokens));
    children.add(parseAssignmentList(tokens));
    return new Node(PascalNonterminals.PROGRAM, children);
  } // parseProgram(PascalTokenizer)

  private Node parseRelationalOperator(PascalTokenizer tokens) 
    throws ParseException,Exception
  {
    if (isRelOp(tokens.peek())) 
      return new Node(tokens.next(), null);
    else 
      return wrongToken(PascalNonterminals.RELATIONAL_OPERATOR, tokens.peek());
  }  // parseRelationalOperator(PascalTokenizer)

  private Node parseSimpleExpression(PascalTokenizer tokens) 
    throws ParseException,Exception
  {
    // Every simple expression begins with a term, so get it.
    Node result = parseTerm(tokens);
    // If the next symbol is an adding operator, there should be
    // that operator and another term, which together make a
    // a compound simple expression.
    while (isAddOp(tokens.peek())) {
      // Three part expression, so build the children
      Vector children = new Vector();
      children.add(result);
      children.add(parseAddingOperator(tokens));
      children.add(parseTerm(tokens));
      // Update the result
      result = new Node(PascalNonterminals.EXPRESSION, children);
    } // while
    // That's it, we're done.
    return result;
  } // parseSimpleExpression(PascalTokenizer)

  private Node parseTerm(PascalTokenizer tokens) 
    throws ParseException,Exception
  {
    // Every term begins with a factor, so get it.
    Node result = parseFactor(tokens);
    // If the next symbol is a multiplying operator, there should be
    // the operator and another factor, which together make a 
    // compound term.
    while (isMulOp(tokens.peek())) {
      // Three part expression, so build the children
      Vector children = new Vector();
      children.add(result);
      children.add(parseMultiplyingOperator(tokens));
      children.add(parseFactor(tokens));
      // Update the result
      result = new Node(PascalNonterminals.EXPRESSION, children);
    } // while
    // That's it, we're done.
    return result;
  } // parseTerm(PascalTokenizer)

  private Node parseVariable(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    // Take the next identifier and shove it in a node.
    if (tokens.peek() instanceof PascalIdentifier)
      return new Node(tokens.next(), null);
    else
      return wrongToken(PascalNonterminals.VARIABLE, tokens.peek());
  } // parseVariable(PascalTokenizer)

  private Node parseVariableDeclaration(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    Vector children = new Vector();
    // Make sure we start with an identifier
    if (!(tokens.peek() instanceof PascalIdentifier))
      return wrongToken(PascalNonterminals.VARIABLE_DECLARATION, tokens.peek());
    // Add the identifier
    children.add(new Node(tokens.next(), null));
    // Are there more?
    while (tokens.peek() == PascalTokens.TCOMMA) {
      tokens.next();
      // Make sure we start with an identifier
      if (!(tokens.peek() instanceof PascalIdentifier))
        return wrongToken(PascalNonterminals.VARIABLE_DECLARATION, tokens.peek());
      // Add the identifier
      children.add(new Node(tokens.next(), null));
    }
    // Ready for the colon
    if (tokens.peek() != PascalTokens.TCOLON) 
      return wrongToken(PascalTokens.TCOLON, tokens.peek());
    tokens.next();
    // Ready for the type
    if (!(tokens.peek() instanceof PascalIdentifier))
      return wrongToken(PascalNonterminals.VARIABLE_DECLARATION, tokens.peek());
    children.add(new Node(tokens.next(), null));
    // We're done
    return new Node(PascalNonterminals.VARIABLE_DECLARATION, children);
  } // parseVariableDeclaration(PascalTokenizer)

  private Node parseVariableDeclarations(PascalTokenizer tokens)
    throws ParseException,Exception
  {
    Vector children = new Vector();
    if (tokens.peek() != PascalTokens.TVAR)
      return wrongToken(PascalNonterminals.VARIABLE_DECLARATIONS, 
                        tokens.peek());
    tokens.next();
    while (tokens.peek() instanceof PascalIdentifier) {
      children.add(parseVariableDeclaration(tokens));
      if (tokens.peek() != PascalTokens.TSEMI)
        return wrongToken(PascalTokens.TSEMI, tokens.peek());
      tokens.next();
    } // while
    return new Node(PascalNonterminals.VARIABLE_DECLARATIONS, children);
  } // parseVariableDeclarations(PascalTokenizer)

} // class AssignLangParser