/* file:     AddMult2.java
   author:   Robert Keller
   purpose:  Tutorial additive/multiplicative expression parser
   
   The program reads an additive/multiplicative expression from standard input 
   and shows its tree as an S expr.

   The tree is formed using the abstract class Expr, which has the following
   variants (derived classes):

        AddExpr
        MultExpr
        VarExpr
        Error

   The grammar is:

    A -> P { '+' P }                                          // expression

    P -> V { '*' V }                                          // Product expr

    V -> a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z  // Variable

   In the grammar { }, means 0 or more of what's inside and | means "or"

*/

import java.io.*;

/**
 * base class for all Expressions
 */

abstract class Expr
  {
  /**
   * tell whether the expression is an error
   */

  abstract boolean isError();
  }


/**
 * additive Expressions
 */

class AddExpr extends Expr
  {
  Expr left;
  Expr right;

  /**
   * construct an additive expression from two terms
   */

  AddExpr(Expr left, Expr right)
    {
    this.left = left;
    this.right = right;
    }

  /**
   * indicate the expression is not an error
   */

  boolean isError()
    {
    return false;
    }

  public String toString()
    {
    return "(+ " + left + " " + right + ")";
    }
  }

/**
 * multiplicative Expressions
 */

class MultExpr extends Expr
  {
  Expr left;
  Expr right;

  /**
   * construct a multiplicative expression from two factors
   */

  MultExpr(Expr left, Expr right)
    {
    this.left = left;
    this.right = right;
    }

  /**
   * indicate the expression is not an error
   */

  boolean isError()
    {
    return false;
    }

  public String toString()
    {
    return "(* " + left + " " + right + ")";
    }
  }


/**
 * variable Expressions
 */

class VarExpr extends Expr
  {
  String var;

  /**
   * construct a variable expression from a String representing the variable
   */

  VarExpr(String var)
    {
    this.var = var;
    }

  /**
   * indicate the expression is not an error
   */

  boolean isError()
    {
    return false;
    }

  public String toString()
    {
    return "(var " + var + ")";
    }
  }

/**
 * error Expression
 */

class ErrorExpr extends Expr
  {
  String reason;

  /**
   * construct an error expression from the reason for the error
   */

  ErrorExpr(String reason)
    {
    this.reason = reason;
    }

  /**
   * indicate the expression is an error
   */

  boolean isError()
    {
    return true;
    }

  public String toString()
    {
    return "(error " + reason + ")";
    }
  }


/**
 * parser
 */

class AddMult2 extends ParseFromString
  {
  static String promptString = "additive&multiplicative > ";

  /**
   * constructor for additive&multiplicative parser
   */

  AddMult2(String input)        
    {
    super(input);               // capture input
    }

  /**
   * Top-level parse method: parse and check for residual input
   */

  Expr parse() 
    {
    Expr result = A();
    skipWhitespace();
    if( position < lastPosition )
      {
      System.out.print("*** Residual characters after input: ");
      while( !eof )
        {
        System.out.print(nextChar());
        }
      System.out.println();
      }
    return result;
    }


  /**
   * PARSE METHOD for A -> P { '+' P }
   */

  Expr A()
    {
    Expr result;
    Expr P1 = P();
    if( P1.isError() ) return P1;

    result = P1;

    while( skipWhitespace() && nextCharIs('+') )
      {
      Expr P2 = P();
      if( P2.isError() ) return P2;
      result = new AddExpr(result, P2);
      }
    return result;
    }


  /**
   * PARSE METHOD for P -> V { '*' V }
   */

  Expr P()
    {
    Expr result;
    Expr V1 = V();
    if( V1.isError() ) return V1;

    result = V1;

    while( skipWhitespace() && nextCharIs('*') )
      {
      Expr V2 = V();
      if( V2.isError() ) return V2;
      result = new MultExpr(result, V2);
      }
    return result;
    }


  /**
   * PARSE METHOD for V -> a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p
   *                        |q|r|s|t|u|v|w|x|y|z
   */

  Expr V()
    {
    skipWhitespace();
    if( isVar(peek()) )
      {
      return new VarExpr((new StringBuffer(1).append(nextChar())).toString());
      }      
    return new ErrorExpr("Expected variable");
    }


  /**
   * predicate defining whether its argument is a variable
   */

  boolean isVar(char c)
    {
    switch( c )
      {
      case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g':
      case 'h': case 'i': case 'j': case 'k': case 'l': case 'm': case 'n':
      case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u':
      case 'v': case 'w': case 'x': case 'y': case 'z':
        return true;
      default:
        return false;
      }
    }


  /**
   * test program for additive&multiplicative parser
   */

  static public void main(String arg[])
    {
    // BufferedReader is used to read a line at a time
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String input;
    try
      {
      while( prompt() && (input = in.readLine()) != null )
        {
        AddMult2 parser = new AddMult2(input);
        Expr result = parser.parse();
        System.out.println("result: " + result);
        System.out.println();
        }
      }
    catch( IOException e )
      {
      System.err.println("*** IOException caught; terminating");
      }
    System.out.println();
    }


  /** 
   * The prompter. Prints a prompt string.
   * The return value is just so this can be used inside a while condition.
   */

  static boolean prompt()
    {
    System.out.print(promptString);
    System.out.flush();
    return true;
    }
  }


/**
 * ParseFromString is the base class for parsing from a String, such as a
 * single input line
 */

class ParseFromString
  {
  protected String input;                 // input to parser

  protected int position;                 // position of current character

  protected int lastPosition;             // last position in input string

  protected boolean eof;                  // end-of-file condition exists


  /**
   * Create ParseFromString object for string to be parsed.
   */

  ParseFromString(String input)
    {
    this.input = input;
    position = -1;
    lastPosition = input.length()-1;
    eof = lastPosition == -1;
    }


  /**
   * Get the next input character.
   */

  char nextChar()
    {
    if( position >= lastPosition )
      {
      eof = true;
      return ' ';
      }
    return input.charAt(++position);
    }


  /**
   * If next char is the specified one, remove it and return true.
   * Otherwise return false.
   */

  boolean nextCharIs(char c)     
    {
    if( position >= lastPosition )
      {
      eof = true;
      return false;
      }
    if( c == peek() )
      {
      nextChar();
      return true;
      }
    return false;
    }

  /**
   * Return the next character in the input, but don't remove it.
   */

  char peek()
    {
    if( position >= lastPosition )
      {
      return ' ';
      }
    return input.charAt(position+1);
    }


  /**
   * Put previously read character back.
   */

  void putBack()
    {
    if( position >= 0 )
      {
      position--;
      }
    }

  /**
   * Skip any whitespace.
   */

  boolean skipWhitespace()
    {
    while( !eof && peek() == ' ' )
      {
      nextChar();
      }
    return true;
    }
  }  // class ParseFromString