package a5;

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;


/**
    This class contains an <code>evaluate</code> method that interprets
    programs in the simple functional language defined by the grammar
    given below.  In case of syntactic or semantic error, the method 
    will throw an <code>InputMismatchException</code> that contains an 
    appropriate error message. 
    
    It assumes that static scoping is in use.  
    So this is the EXTRA CREDIT VERSION of Assignment 5
   
    The program representation is as a string of tokens separated
    by whitespace characters as recognized by the 
    <code>Character.isWhitespace</code> predicate.
         
    There is no explicit constructor; the default constructor is sufficient.
          
    The grammar for boolean expressions has start symbol &lt;Program&gt; and productions <pre>
      Program := Def* E
      E := ( Fname E E )
      E := Number
      E := Id
      Def := define Id ( Id Id ) Def* E end
      Fname := Id | + | *
      Id := Letter+
      Number := Digit+
</pre>
    
    Note that recursive descent parsing is appropriate for this grammar. 
 */


public class Interpreter
{

	
  // used to divide the program into tokens 
  //   and to retrieve the next token
  private Scanner tokenizer;
  
  // the next unprocessed token of the program
  private String lookahead;

  
/// CLASSES FOR REPRESENTING PARSED PROGRAMS & PROGRAM SEGMENTS ///

  /**
      This class represents parsed programs in the given language.
   */
  
  
  private class Program        
  {
      // a list of the function blocks in the program
      public LinkedList<Def> defs;
      
      // the expression to be evaluated 
      public ExprTree body;
 
      
      /**
          @param d a list of the function blocks that 
            are to be part of the program
          @param b a tree representing the expression
            to be evaluated by the program
       */
      // this class has no mutators and returns no mutable
      //   values, so cloning the constructor's arguments 
      //   is unnecessary
      
      public Program(LinkedList<Def> d, ExprTree b)       {
        defs = d;
        body = b;                                        }

        
      /**
          @return the value of the program
       */  
      // update the global environment with the 
      //   bindings in in the definitions,
      //   and then evaluate the expression in the
      //   resulting environment
      
      public int evaluate()                              { 
        Environment e = new Environment();
        e.evaluateDefs(defs);
        return body.evaluate(e, "main program");         }
     

  } // end class Program
    
    
  /**
       A class for representing translated function blocks 
         in the given programming language
   */
  // Note that an alternate implementation would be to remove
  //   the name component from the class, and map function names 
  //   to closures within a frame in the same way that variable
  //   names are mapped to values.
    
  private class Def
  {
      // the function name
      public String name;
      
      // the first and second formal parameters
      public String param1;
      public String param2;
      
      // the immediately nested (translated) function blocks
      public LinkedList<Def> defs;
      
      //  a tree representing the expression
      //    to be evaluated by the program
      public ExprTree body;

      // a frame for the defining environment
      public Frame definingFrame = null;
      
      /**
          @param n the name of the function
          @param p1 the first formal parameter
          @param p2 the second formal parameter
          @param d a list of the function blocks that 
            are to be nested immediately inside this block
          @param b a tree representing the body of the
            function
       */
      // this class has no mutators and returns no mutable
      //   values, so cloning the constructor's arguments 
      //   is unnecessary
      
      public Def(String n, String p1, String p2,
                      LinkedList<Def> d, ExprTree b)       {
        name = n;
        param1 = p1;
        param2 = p2;
        defs = d;
        body = b;                                         }
        
        
      /**
          Set the definition's defining frame to a given value.
          @param the value
       */  

      public void setDefiningFrame(Frame f)         {
        definingFrame = f;                          }
      
        
      /**
          @return the name of the function
       */  

      public String getName()                             {
        return name;                                      }
      
       /**
          Applies the function to a pair of evaluated 
            arguments
          @param arg1 the first evaluated argument
          @param arg2 the second evaluated argument
          @param e the environment in which evaluation
            is to take place
          @return the value of the function  
       */  
       // updates the environment with by binding the
       //   formal parameters to the given arguments
       //   and passing along the internal definitions
       // and then evaluates the function body in the
       //   augmented environment
       
      public int apply(int arg1, int arg2, Environment e)            {
        e.addFrame(name, param1, arg1, param2, arg2, 
                   definingFrame);
        e.evaluateDefs(defs);
        int value = body.evaluate(e, name);                 
        e.popFrame();
        return value;                                                }
    
        
    } // end class Def      
    
    
    
   /**
      Instances of this class represent syntax trees (analogs
      of parse trees that are used for expression evaluation).  
      Their methods are abstract, since different subclasses
      are used for leaves and nonleaves.
   */
  
  private abstract class ExprTree
  {
    abstract public int evaluate(Environment e, String caller);
  }  // end ExprTree class
  
  
  /**
     Instances of this class represent syntax trees with single
     nodes representing operands.
  */
 
  private class ExprLeaf extends ExprTree
  {
    
    // the operand
    private String atom;
    // null iff operand is a literal
    private Integer value;
    
    /**
       @param token the string representing the operand
       @param intValue the integer value if the operand is
         an integer literal (null otherwise)
     */
    
    public ExprLeaf(String token, Integer intValue)       {
      atom = token;                               
      value = intValue;                                   }
    
    
    /**
        Evaluates the operand in the given environment
        @param e the environment to be used for evaluation
        @param caller the name of the caller 
          (used for error messages only)
        @return the value of the operand (i.e., of the 
         syntax tree)
     */
    
    public int evaluate(Environment e, String caller)          {
      if (value == null)                                     {
        Integer newValue = e.getValue(atom);
        if (newValue != null)
          return newValue;
        else
          throw new InputMismatchException(
            "no value found for " + atom + " in " + caller); }
      else
        return value;                                          }

  } // end ExprLeaf class
    
  
  
  /**
     Instances of this class represent syntax trees with 
       more than one node.  Roots represent functions,
       and children represent operands.  According to the
       given grammar, all functions are assumed to be binary
       and, except for + and *, functions are expected to
       be user-defined.   
  */

  private class ExprInternalNode extends ExprTree         
  {
     // the top-level function
     private String operator;
     
     // the first operand
     private ExprTree firstChild;
     
     // the second operand 
     private ExprTree secondChild;
     
     
     /**
         A constructor that takes as arguments the three desired components
           of the new tree
         @param op the top-level function, represented as a <code>String</code>
         @param first the first operand
         @param second the second operand
      */
      // this class has no mutators and returns no mutable
      //   values, so cloning the constructor's arguments 
      //   is unnecessary
     
     public ExprInternalNode(String op, ExprTree first, ExprTree second) {
       operator = op;
       firstChild = first;
       secondChild = second;                                             }
     
     
    /**
         Evaluates the represented expression in a given environment
         @param e the environment to be used for evaluation
         @param caller the name of the caller 
           (used for error messages only)
         @return the integer value obtained by evaluating the tree 
         @throws InputMismatchException if an undefined function or
           variable is present
     */   
     // The evaluation algorithm is a recursive evaluation that's 
     //   equivalent to a postorder traversal
     // It looks up the operator and the operands in the environment
     //   and applies the operator to the operands
     // Note that processing of + and * is hard-coded into the method.
     //   However the ordering of the cases in the current version of 
     //   this method could handle the situation where these operators 
     //   can be redefined by the user.
     
     public int evaluate(Environment e, String caller)                  {
       Def d = e.getDef(operator);
       if (d != null)                                                 {
         String fname = d.getName();  
         return d.apply(firstChild.evaluate(e, fname), 
                        secondChild.evaluate(e, fname), e);           }
       if (operator.equals("+"))                                      { 
         return firstChild.evaluate(e,"+") 
              + secondChild.evaluate(e,"+");                          }
       if (operator.equals("*"))                                      {        
         return firstChild.evaluate(e,"*") 
              * secondChild.evaluate(e,"*");                          }
       else
         throw new InputMismatchException(
           "undefined function " + operator + " in " + caller);         }
     
   } // end ExprInternalNode class
    
  
   
   
  ///////////////////// ENVIRONMENTS ////////////////////// 
  
  /**
      This class is used to represent environments in which
        expressions may be evaluated using dynamic scoping
   */
  // No global frame is assumed -- the treatment of + and *
  //   is hard-coded into the "evaluate" method
  // The default constructor suffices in the 0-argument case
  
  private class Environment
  {
      
     // Here we assume that frames have their own link fields,
     //   so that it's enough to specify only the top frame
     private Frame topFrame; 
     
    
     public Environment()                                          {
      topFrame = new Frame("main",null,0,null,0,null,null); }

       
     /**
         Adds a given frame, representing a function block,
          to the environment
         @param nm the name of the function whose block
           corresponds to the frame (for debugging only)
         @param p1 the first formal parameter of the function
         @param v1 the argument bound to this parameter
         @param p2 the first formal parameter of the function
         @param v2 the argument bound to this parameter
         @param d the immediately nested function blocks for
           this function
      */  
     
     public void addFrame(String nm, String p1, int v1,
             String p2, int v2, Frame definingFrame)      {
       Frame f = new Frame(nm, p1, v1, p2, v2, topFrame, 
                           definingFrame);
       topFrame = f;                                     }
     
     /**
          Evaluates all the definitions in a given list.
          That is, enters them into the current frame
            and initializes their envrionment references.
          @param defs the list of definitions
          @param definingEnv the environment in which
             the definitions were defined
      */  
     // may assume that there is at least one frame on the stack
     public void evaluateDefs(LinkedList<Def> defs)   {                          
       for (Def d : defs)
         topFrame.evaluateDef(d, topFrame);           }
     

     /**
         @return the top frame of the environment
      */    
     
     public Frame getTopFrame()                         {
       return topFrame;                                 }
       
       
     /**
         Remove the top frame of the environment
      */    
     
     public void popFrame()                             {
       topFrame = topFrame.link;                        }
       
       
     /**
         Evaluates a variable in the environment
         @param var the variable name
         @return the value bound to the variable
           if there is one, null otherwise.
      */
     // Sequentially searches the frames (most recent
     //   first) until a binding for the symbol is found
     
     public Integer getValue(String var)              {  
       return topFrame.getVarBinding(var);    }  

       
      /**
         Looks up a function name in the environment
         @param var the function name
         @return the closest function block corresponding to 
           the function name if there is one, null otherwise.
      */
     // Sequentially searches the frames (most recent
     //   first) until a binding for the name is found
     
     public Def getDef(String var)                    {  
       return topFrame.getDefBinding(var);            }  
      
  } // end class Environment  
         
       
    /**
          Represents a frame in a dynamic scoping environment
     */    
     
     private class Frame
     {
        // for debugging only
        private String name;
        
        // the first and second formal parameters 
        private String param1;
        private String param2;
        
        // the values bound respectively to these parameters
        private int value1;
        private int value2;
        
        // the immediately nested (translated) function blocks
        private LinkedList<Def> defs;
        
        // the frame immediately below this frame in the
        //   run-time stack
        private Frame link;
        
        // the top frame in the definining enviroment 
        //   (the successor in the static chain)
        
        private Frame staticSuccessor;
        
        /**
         @param nm the name of the function whose block
           corresponds to the frame
         @param p1 the first formal parameter of the function
         @param v1 the argument bound to this parameter
         @param p2 the first formal parameter of the function
         @param v2 the argument bound to this parameter
        */
        
        public Frame(String nm, String p1, int v1, String p2, int v2,
                     Frame l, Frame successor)                         {
          name = nm;
          param1 = p1;
          param2 = p2;
          value1 = v1;
          value2 = v2;            
          defs = new LinkedList<Def>();
          link = l;
          staticSuccessor = successor;                        }
     
          
      /**
          Evaluates a given definition
          That is, enters them into the current frame
            and initializes their envrionment references.
          @param def the list of definitions
          @param definingEnv the environment in which
             the definitions were defined
      */  
     public void evaluateDef(Def d, Frame definingFrame)       {
       d.setDefiningFrame(definingFrame);
       defs.add(d);                                            }
     
        
     /**
         Looks up a variable in the frame
         @param var the variable name
         @return the value bound to the variable
           if there is one, null otherwise.
      */
     
        public Integer getVarBinding(String var)           {
          if (var.equals(param1))
            return value1;
          if (var.equals(param2))
            return value2;
          if (staticSuccessor != null)
            return staticSuccessor.getVarBinding(var);
          else 
            return null;                                   }  
          
          
      /**
         Looks up a function name in the frame
         @param var the function name
         @return the function block corresponding to 
           the function name if there is one, null otherwise.
      */
        public Def getDefBinding(String var)               {
          for (Def d : defs)
            if (d.getName().equals(var))
              return d;
          if (staticSuccessor != null)
            return staticSuccessor.getDefBinding(var);
          else 
            return null;                                   }  
          
     } // end class Frame
       
       
  /**
      Evaluate an expression consistent with the given grammar
      @param input the input string representing the expression
      @return the integer value
      @throws InputMismatchException for ill-formed input strings
   */
  
  public int evaluate(String input)                           {
    return parse(input).evaluate();                           }
  
  
  /////////////////// PARSING METHODS /////////////////////////  
  
  /**
      Parse a string that is assumed to represent a program
        that can be generated by the given grammar
      @param input the input string  
      @return a syntax tree for the expression, represented as 
        an <code>ExprTree</code>  
      @throws InputMismatchException for ill-formed input strings
   */
  // The parsing algorithm is recursive descent.
  // A dummy symbol is appended to each input string so
  //   that lookahead never fails
  // The input string is entered into a tokenizer,
  //   which really ought to be closed as in Assignment 2

  private Program parse(String input)                            {
    if (input == null)
      throw new InputMismatchException(
        "input string cannot be null");
    tokenizer = new Scanner(input + " $end-of-file$");
    lookahead = tokenizer.next();    
    Program result = parseProgram();
    tokenizer.close();
    if (!lookahead.equals("$end-of-file$"))
      throw new InputMismatchException(
        "symbols remain after end of expression");    
    return result;                                               }
  
  
  //////// parsing methods for particular nonterminals /////////

  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;program&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a <code>Program</code> representation for the string
       (which is thus assumed to represent a legal program) 
     @throws InputMismatchException for ill-formed input strings    
   */
  
  private Program parseProgram()                              {
    LinkedList<Def> deflist = new LinkedList<Def>();  
    while (lookahead.equals("define"))                      {
      Def def = parseDef();
      deflist.add(def);                                     }
    ExprTree e = parseExpr();  
    return new Program(deflist, e);                            }  
         

  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;def&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a <code>Def</code> representation for the string
       (which is thus assumed to represent a function block) 
     @throws InputMismatchException for ill-formed input strings
   */
  
  private Def parseDef()                                     {
    // could remove this test -- lookahead is already checked
    if (!lookahead.equals("define"))                         
      throw new InputMismatchException(
        "define expected -- " + lookahead + " found");
    lookahead = tokenizer.next();           
    String name = parseId();
    if (!lookahead.equals("("))
      throw new InputMismatchException(
        "( expected in " + name + " -- " + lookahead + " found");
    lookahead = tokenizer.next();           
    String param1 = parseId();
    String param2 = parseId();
    if (!lookahead.equals(")"))
      throw new InputMismatchException(
        ") expected in " + name + " -- " + lookahead + " found");
    lookahead = tokenizer.next();           
    LinkedList<Def> deflist = new LinkedList<Def>();  
    while (lookahead.equals("define"))                      {
      Def def = parseDef();
      deflist.add(def);                                     }
    ExprTree e = parseExpr();  
    if (!lookahead.equals("end"))
      throw new InputMismatchException(
        "end expected in " + name + " -- " + lookahead + " found");
    lookahead = tokenizer.next();           
    return new Def(name, param1, param2, deflist, e);          }  
         
     
  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;expr&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a syntax tree for the expression, represented as 
       an <code>ExprTree</code>  
     @throws InputMismatchException for ill-formed input strings
  */
  
  private ExprTree parseExpr()                                     {
      // try the 3rd rule
    if (lookahead.equals("("))                           {
      lookahead = tokenizer.next();   
      String f = parseFunctionName();  
      ExprTree child1 = parseExpr();
      ExprTree child2 = parseExpr();
      if (!lookahead.equals(")"))                           
        throw new InputMismatchException(
          ") expected in " + f + " -- " + lookahead + " found");
      lookahead = tokenizer.next();   
      return new ExprInternalNode(f, child1, child2);    }  
    
      // try the 1st rule 
    else if (Character.isLetter(lookahead.charAt(0)))    {              
      return new ExprLeaf(parseId(), null);              }
      
      // try the 2nd rule  
    else if (Character.isDigit(lookahead.charAt(0)))     { 
      String numberAsString = parseNumber();
      return new ExprLeaf(numberAsString,
         Integer.parseInt(numberAsString));              }     
    
    else
      throw new InputMismatchException(
        "( expected -- " + lookahead + " found");           }
    

  
  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;id&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a String representing the token
     @throws InputMismatchException for ill-formed input strings
  */
  
  private String parseId()                                        {     
    for (int i=0; i<lookahead.length(); i++)     
      if (!Character.isLetter(lookahead.charAt(i)))
        throw new InputMismatchException(
          "illegal character in identifier -- " + lookahead);
    String id=lookahead;
    lookahead = tokenizer.next(); 
    return id;                                      }

    
  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;number&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a String representing the token
     @throws InputMismatchException for ill-formed input strings
  */
  
  private String parseNumber()                                        {     
    for (int i=0; i<lookahead.length(); i++)           
      if (!Character.isDigit(lookahead.charAt(i)))
        throw new InputMismatchException(
          "illegal digit in number -- " + lookahead);
    String id=lookahead;
    lookahead = tokenizer.next(); 
    return id;                                      }
    
  
  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;fname&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a String representing the function name
     @throws InputMismatchException for ill-formed input strings
  */
    
  private String parseFunctionName()                               {
    if (lookahead.equals("+") || lookahead.equals("*"))        {
      String name = lookahead;
      lookahead = tokenizer.next(); 
      return name;                                             }
    else                                                       {
      return parseId();                                            }
  
    }}