// Parser.java

// Date: 3/5/98
// Author: Adam Berger
// Description: Parser routines for SL project 

import java.io.*;
import java.math.*;

public class Parser implements TokenTypes {
  private ParseNode tree;       // root of abstract parse tree for input program 
  private Lexer lexer;
  
  private static final int statements [] = 
  { T_BREAK, T_CALL, T_IF, T_LET, T_READ, T_RETURN, T_WHILE, T_WRITE };
  
  public static final int unaryOps[] = {T_EXCLAM,  T_TILDE};
  public static final int binaryOps[] = 
  {T_PLUS, T_MINUS, T_TIMES, T_DIV, T_MOD, T_LT, T_GT, T_NE, T_EQ, T_GE, 
   T_LE, T_ASSN, T_AND, T_OR};


  public Parser (InputStream is) {
    lexer = new Lexer(is);
  }

  public void parse() throws ParseException, LexerException {
    tree = new SL_ProgramNode(); 
    while (peek()==T_FUNCTION) parse_function(tree);
    parse_block(tree);
    if (peek() != T_EOF) 
      throw new ParseException(lexer.getCurrentLine(), "extra stuff after main block");
  }
  
  // recursively print tree nodes, depth-first pre-order
  public void print() { tree.print(); }

  public void setInput(String input) throws InterpretException 
    { tree.setInputFile(input); }
  
  public BigInteger interpret() throws InterpretException {
    BigInteger i=null;
    try {
      ParseNode returnValue = tree.interpret(lexer.getSymbolTable());
      if (returnValue instanceof SL_NumberNode) 
	i=((SL_NumberNode) returnValue).getValue();
    }
    catch (BreakException b) { /* won't occur */ }
    catch (ReturnException r) { /* won't occur */ }
    return i;
  }
  
  // top-down parsing of SL programs implemented below this line 
  private void parse_function(ParseNode parent) 
    throws ParseException, LexerException  {
    SL_FunctionNode child = new SL_FunctionNode();
    parent.addChild(child);
    match(T_FUNCTION);
    parse_ident(child);
    match(T_LPAREN);
    parse_paramlist(child);
    match(T_RPAREN);
    parse_block(child);    
  }

  private void parse_paramlist(ParseNode parent) 
    throws ParseException, LexerException  {
    if (peek()==T_RPAREN) return;    // empty parameter list  
    parse_ident(parent); 
    while (peek()==T_COMMA) {
      match(T_COMMA);
      parse_ident(parent);
    }      
  }
  
  private void parse_block(ParseNode parent) throws ParseException, LexerException {
    match(T_LBRACE);
    SL_BlockNode child = new SL_BlockNode();
    parent.addChild(child);
    while (parse_statement(child));
    match(T_RBRACE);
  }
  
  private boolean parse_statement(ParseNode parent) 
    throws ParseException, LexerException { 
    ParseNode child;
    switch (peek()) {
    case T_BREAK:  
      child = new SL_BreakNode();
      parent.addChild(child);
      match(T_BREAK);
      match(T_SEMI);
      break;
    case T_CALL:   
      child = new SL_CallNode();
      parent.addChild(child);
      parse_call(child); 
      match(T_SEMI);
      break;
    case T_IF:
      child = new SL_IfNode();
      parent.addChild(child);
      parse_if(child);
      break;
    case T_LET:
      child = new SL_LetNode();
      parent.addChild(child);
      parse_let(child);
      break;
    case T_READ:
      child = new SL_ReadNode();
      parent.addChild(child);
      match(T_READ);
      parse_ident(child);
      match(T_SEMI);
      break;
    case T_RETURN:
      child = new SL_ReturnNode();
      parent.addChild(child);
      match(T_RETURN);
      parse_expr(child);
      match(T_SEMI);
      break;
    case T_WHILE:
      child = new SL_WhileNode();
      parent.addChild(child);
      match(T_WHILE);
      parse_expr(child);
      parse_block(child);
      break;
    case T_WRITE:
      child = new SL_WriteNode();
      parent.addChild(child);
      match(T_WRITE);
      parse_expr(child);
      match(T_SEMI);
      break;
    default:
      return false;
    }
    return true;
  }
 
  private void parse_call(ParseNode parent) throws ParseException, LexerException {
    match(T_CALL);
    parse_ident(parent); 
    match(T_LPAREN);
    parse_arglist(parent);
    match(T_RPAREN);
  }
  
  private void parse_expr(ParseNode parent) throws ParseException, LexerException {
    ParseNode child;
    switch (peek()) {
    case T_NUMBER:
      child = new SL_ExprNode();
      parent.addChild(child);
      parse_number(child);
      break;
    case T_IDENT:
      child = new SL_ExprNode();
      parent.addChild(child);
      parse_ident(child);
      break;
    case T_LPAREN:
      match(T_LPAREN);
      int tokenType = peek();
      boolean qUnary  = isMember(tokenType, unaryOps);
      boolean qBinary = isMember(tokenType, binaryOps);
      if (qUnary || qBinary) {
	Token t = lexer.getToken(); // eat the operator
	int opType = t.getType();
	SL_ExprNode child_ = new SL_ExprNode(opType);
	parent.addChild(child_);
	parse_expr(child_);    // first argument 
	if (qBinary) parse_expr(child_);  // second argument 
      }
      else parse_expr(parent);
      match(T_RPAREN);
      break;
    default:
      throw new ParseException(lexer.getCurrentLine(), "expecting expr");
    }
  }

  private void parse_arglist(ParseNode parent) 
    throws ParseException, LexerException {
    if (peek()==T_RPAREN) return;    // empty parameter list  
    parse_expr(parent);
    while (peek() == T_COMMA) {
      match(T_COMMA);
      parse_expr(parent);
    }
  }

  private void parse_if(ParseNode parent) throws ParseException, LexerException {
    match(T_IF);
    parse_expr(parent);
    parse_block(parent);
    if (peek()==T_ELSE) {
      match(T_ELSE);
      parse_block(parent);
    }
  }
  
  private void parse_let(ParseNode parent) throws ParseException, LexerException {
    match(T_LET);
    parse_ident(parent);
    match(T_ASSN);
    if (peek()==T_CALL) {
      SL_CallNode child = new SL_CallNode();
      parent.addChild(child);
      parse_call(child);
    }
    else parse_expr(parent);
    match(T_SEMI);
  }
    
  private void parse_ident(ParseNode parent) throws ParseException, LexerException {
    Token t = lexer.getToken();
    if (t.getType() != T_IDENT)
      throw new ParseException(lexer.getCurrentLine(), "expecting identifier");
    parent.addChild(new SL_IdentNode(t.getLexeme()));
  }

  private void parse_number(ParseNode parent) 
    throws ParseException, LexerException {
    Token t = lexer.getToken();
    if (t.getType() != T_NUMBER)
      throw new ParseException(lexer.getCurrentLine(), "expecting number");
    parent.addChild(new SL_NumberNode(t.getValue()));
  }

  // various utility routines 
  private void match(int expectedType) throws ParseException, LexerException {
    // grabs next token and requires that it has the expected type...or fails trying
    Token token = lexer.getToken();
    if (token.getType() != expectedType) 
      throw new ParseException(lexer.getCurrentLine(), expectedType);
  }
  
  private int peek() throws LexerException {
    // returns type of next token to be returned by lexer
    Token token = lexer.getToken();
    lexer.putBack(token);
    return token.getType();
  }
  
  private boolean isMember(int value, int arr[]) {
    for (int i=0; i<arr.length; i++) 
      if (arr[i]==value) return true;
    return false;
  }
}