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

    A -> P { '+' P }                                          // AddMult expr

    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.*;

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

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

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

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

  Object parse() 
    {
    Object 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 }
   **/

  Object A()
    {
    Object result;
    Object P1 = P();
    if( isFailure(P1) ) return failure;

    result = P1;

    while( skipWhitespace() && nextCharIs('+') )
      {
      Object P2 = P();
      if( isFailure(P2) ) return failure;
      result = OpenList.list("+", result, P2);
      }
    return result;
    }


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

  Object P()
    {
    Object result;
    Object V1 = V();
    if( isFailure(V1) ) return failure;

    result = V1;

    while( skipWhitespace() && nextCharIs('*') )
      {
      Object V2 = V();
      if( isFailure(V2) ) return failure;
      result = OpenList.list("*", 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
   **/

  Object V()
    {
    skipWhitespace();
    if( isVar(peek()) )
      {
      return (new StringBuffer(1).append(nextChar())).toString();
      }      
    return failure;
    }


  /**
   * 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 )
        {
        AddMult parser = new AddMult(input);
        Object 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
  {
  public final static ParseFailure failure = new ParseFailure();     // failure

  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;
    }


  /**
   * Test whether the argument is a ParseFailure object.
   **/

  boolean isFailure(Object ob)
    {
    return ob instanceof ParseFailure;
    }
  }  // class ParseFromString


/**  
 * ParseFailure object is used to indicate a parse failure.
 **/

class ParseFailure
  {
  }