Parser.jj

PARSER_BEGIN(Parser)
import java.util.*;

/*
* FOR DOCUMENTATION PURPOSES, "Extending code:" indicates
* areas to consider when trying to extend the code
*/

class Parser {
  public static void main(String[] args) {
    Parser p = new Parser(System.in);
    //start point of application

    try {
      //parsing
      p.Start();
      //evaluation of result if parsing succeded
      int result = Function.functions.get("MAIN").evaluate(0);

      //no errors
      System.out.println("PASS");
      System.out.println(result);
    }
    /*
    * Extending code:
    * For throwing custom errors throw an
    * instance of CustomParseException
    */
    catch(CustomParseException e) {
      System.out.println("FAIL");
      System.err.println(e.getMessage());
    }
    catch (TokenMgrError e) {
      System.out.println("FAIL");
      System.err.println(e.getMessage());
    }
    //catches a recursion error
    catch(RecursionException e) {
      System.out.println("PASS");
      System.out.println("DIVERGENCE");
    }
    /*
    * Default javacc exceptions are decoded
    * into custom errors here
    */
    catch (ParseException e) {
      System.out.println("FAIL");

      ArrayList<String> expectedTokens = new ArrayList<String>();
      String nextTokenImage = e.currentToken.next.image;
      Token errCausingToken = e.currentToken.next;

      /*
      * Get tokens that were expected but not found
      */
      for (int i = 0; i < e.expectedTokenSequences.length; i++) {
        for (int j = 0; j < e.expectedTokenSequences[i].length; j++) {
          String b = e.tokenImage[e.expectedTokenSequences[i][j]];
          expectedTokens.add(b);
        }
      }

      /*
      * Decode javacc default error messages to
      * determine the catagory of error
      * and print the custom message for each catagory
      */
      if (expectedTokens.contains("<FNAME>") & nextTokenImage.equals("DEF")) {
          ShowErrorAndQuit("Function name must not contain MAIN or DEF and must be all upper case", errCausingToken.beginLine);
      }
      if (expectedTokens.contains("\"DEF\"")) {
        ShowErrorAndQuit("Function decleration must start with DEF (uppercase)", errCausingToken.beginLine);
      }
      if (expectedTokens.contains("<PARAM>") & (nextTokenImage.equals(" ")  ||
        nextTokenImage.equals("{")) || (nextTokenImage == nextTokenImage.toUpperCase())) {
          ShowErrorAndQuit(
            "HINT: Paramaters need to be Non-empty strings, "
              + "\nLower-case characters,"
              +  "\nContains empty spaces, "
              + "\nInvalid call to MAIN, "
              + "\nWhite space in paranthesis.",
              errCausingToken.beginLine);
      }
      if (expectedTokens.contains("<FNAME>") & expectedTokens.contains("<DIGITS>") & expectedTokens.contains("<PARAM>") & nextTokenImage.equals(" ")) {
        ShowErrorAndQuit("The function cannot be empty.", errCausingToken.beginLine);
      }
      if (expectedTokens.contains("<FNAME>") & expectedTokens.contains("<DIGITS>") & expectedTokens.contains("<PARAM>") & nextTokenImage.equals("(")) {
        ShowErrorAndQuit("Parenthesis can only be present in function calls.", errCausingToken.beginLine);
      }
      if (expectedTokens.contains("\"}\"")) {
        ShowErrorAndQuit("White spaces are not allowed in the expression body.", errCausingToken.beginLine);
      }
      System.err.println("Unknown parser error");
      System.exit(-1);
    }
    catch(Throwable e) {
      System.out.println("FAIL");
      System.err.println("Unknown program error (not a parser error)");
    }
  }

  /*
  * After an error condition has been matched
  */
  private static void ShowErrorAndQuit(String err, int line)
  {
    System.err.println("Line: " + line);
    System.err.println(err);
    System.exit(-1);
  }
}

/*
* Extending code: Any feature that may require checking for recusion
* check for recusion and
* throw this class when such recusion is detected,
* to work with existing code
*/
class RecursionException extends Exception {
  public RecursionException(String message) {
    super(message);
  }

  public RecursionException() {
    super();
  }
}

/*
* Extending code: Any new feature
* resulting in a parse exception
* must throw this error upon parse error being detected
*/
class CustomParseException extends ParseException {
  public CustomParseException(String message) {
    super(message);
  }
  public CustomParseException() {
    super();
  }
}

/*
* Extending code:
* A new feature class must implement this
* interface to allow it to work with old code
*/
interface iEvaluable {
  /*
  * Return the int that a component of
  * a statement in PLM can resolve to
  */
  int evaluate(int pVal) throws ParseException, RecursionException;
}

/*
* Class representing the function product defined in the parser.
* A class is used so Function objects
* can be stored later, representing
* a function production, and called upon later during runtime execution.
* Root node of the following abstract syntax tree
*/
class Function implements iEvaluable {
  /* Store all functions globally */
  public static HashMap<String, Function> functions = new HashMap<String, Function>();
  /* Top level expression for function production */
  private Expression rootExpression;
  private String fName;

  public Function(Expression rootExpression, String fName) {
    this.rootExpression = rootExpression;
    this.fName = fName;
  }

  public int evaluate(int pVal) throws ParseException, RecursionException {
    return rootExpression.evaluate(pVal);
  }

  public String getFName() {
    return this.fName;
  }
}

/*
* Extending code:
* Any new feature class that
* can directly return an int Val
* must implement this interface to work with old code
*/
interface Val {
  int getVal(int param) throws ParseException, RecursionException;
}

/*
* Class represent literal integer value in PLM
* that can be directly evaluated to a positive
* integer. Hence it implements Val interface
*/
class Digits implements Val {
  private int Val;

  public Digits(int Val) {
    this.Val = Val;
  }

  public int getVal(int pVal) throws ParseException, RecursionException {
    return Val;
  }
}

/*
* Represents the numerical value that
* a expression production evalutes too
*/
class Expression implements iEvaluable {
  private ArrayList<Multiplication> multiplications;

  public Expression(ArrayList<Multiplication> multiplications) {
    this.multiplications = multiplications;
  }

  /*
  * A expression at the top level consists of a sum of
  * multiplications which is calculated by sum of array
  * operation
  */
  public int evaluate(int pVal) throws ParseException, RecursionException {
    int total = 0;
    for(Multiplication m: multiplications) {
      total += m.evaluate(pVal);
    }
    return total;
  }
}

/*
* Class represent value of
* sequence of multiplications
* constructed from a multiplaction production
*/
class Multiplication implements iEvaluable {
  private ArrayList<Val> Vals;

  public Multiplication(ArrayList<Val> Vals) {
    this.Vals = Vals;
  }

  public int evaluate(int pVal) throws ParseException, RecursionException {
    int total = 1;
    for(Val v: Vals) {
      total *= v.getVal(pVal);
    }
    return total;
  }
}

/*
* Object constructed when a call from Function(start)
* is made to Function(end).
* Acting as a connection between AST of two Function
* objects
*/
class FCallEdge {
  public static Set<FCallEdge> allFCallEdges = new HashSet<FCallEdge>();
  private String start;
  private String end;

  public FCallEdge(String start, String end) {
    this.start = start;
    this.end = end;
  }

  public String getStart() {
    return start;
  }

  public String getEnd() {
    return end;
  }

  /*
  * Manually define how to determine two
  * FCallEdges
  */
  @Override
  public int hashCode() {
    return (start + end).hashCode();
  }

  @Override
  public boolean equals(Object e2) {
    if(e2 instanceof FCallEdge) return this.hashCode() == e2.hashCode();
    return false;
  }
}

/*
* Represents a fcall prod
* from the parser below
*/
class FCall implements Val {
  private String startFName;
  private String fName;
  private Expression argExpression;
  /* Stores current stack of unfinished functions */
  public static Stack<FCallEdge> currentlyExecuting = new Stack<FCallEdge>();

  /*
  * A FCall consists of the start function (fName) that calls
  * another function startFName
  */
  public FCall(String fName, Expression argExpression, String startFName) {
    this.fName = fName;
    this.argExpression = argExpression;
    this.startFName = startFName;
  }

  /*
  * The numerical value of a function call
  * is calculated by evaluating
  * startFName with the provided argExpression
  */
  public int getVal(int pVal) throws ParseException, RecursionException {
    FCallEdge edge = new FCallEdge(startFName, fName);
    /* If current function call goes to a function
    which hasn't yet been completed, then there is a
    cycle in the graph of function calls.
    Stack stores functions that haven't been finished yet */
    if (!(this.currentlyExecuting.search(new FCallEdge(edge.getEnd(), edge.getStart())) > -1)) {
      this.currentlyExecuting.push(edge);

      int argVal = argExpression.evaluate(pVal);
      Function f = Function.functions.get(fName);
      int val = f.evaluate(argVal);

      this.currentlyExecuting.pop();
      return val;
    }
    else {
      throw new RecursionException(String.format("Recursion detected %s->%s", startFName, fName));
    }
  }
}

/*
* Represents a param within
* a expression production
*/
class Param implements Val {
  public int getVal(int pVal) throws ParseException, RecursionException {
      return pVal;
  }
}
PARSER_END(Parser)

TOKEN : {
  < MAIN : "MAIN" >        |
  < SC : ";" >             |
  < EOL : "\n">            |
  < PLUS : "+" >           |
  < MUL : "*" >            |
  < S : " " >              |
  < DEF : "DEF" >          |
  < LCB : "{" >            |
  < RCB : "}" >            |
  < LPB : "(" >            |
  < RPB : ")" >            |
  < FNAME : (<UPPER>)+ >   |
  < PARAM : (<LOWER>)+ >   |
  < DIGITS : (<DIGIT>)+ >
}
TOKEN : {
  < UPPER : (["A"-"Z"]) >  |
  < LOWER : (["a"-"z"]) >  |
  < DIGIT : (["0"-"9"]) >
}

void Start() throws ParseException, RecursionException:
{}
{
  (FunctionProd())+
  <EOF>
  {
    if(!Function.functions.containsKey("MAIN")) {
      throw new CustomParseException("MAIN function not defined");
    }

    //check undefined function not called
    for(FCallEdge edge: FCallEdge.allFCallEdges) {
      if(!Function.functions.containsKey(edge.getEnd())) {
        throw new CustomParseException(String.format("Undefined function '%s' is referenced " +
          "in function '%s'", edge.getEnd(), edge.getStart()));
      }
    }
  }
}

void FunctionProd() throws ParseException:
{
  Token t;
  String fName;
  String pName;
  Expression expression;
  Function f;
}
{
  <DEF><S>(
    <MAIN>
    <S><LCB><S>
    expression = ExpressionProd("MAIN", null)
    <S><RCB>
    {
      f = new Function(expression, "MAIN"); //NONE as parameter name implies its MAIN so no parameters
    }
    |
    t = <FNAME>
    { fName = t.image; }
    <S>
    t = <PARAM>
    { pName = t.image; }
    <S><LCB><S>
    expression = ExpressionProd(fName, pName)
    <S><RCB>
    {
      f = new Function(expression, fName);
    }
  )
  {
    if(Function.functions.containsKey(f.getFName())) {
      throw new CustomParseException(String.format("Function '%s' defined more than once", f.getFName()));
    }
    else {
      Function.functions.put(f.getFName(), f);
    }
  }
  <S> <SC> <EOL>
 }

Expression ExpressionProd(String startFName, String functionPName):
{
  ArrayList<Multiplication> multiples = new ArrayList<Multiplication>();
  Multiplication multiple;
}
{
  multiple = TermProd(startFName, functionPName)
  { multiples.add(multiple); }
  (
    <PLUS>
    multiple = TermProd(startFName, functionPName)
    { multiples.add(multiple); }
  )*
  {
    Expression e = new Expression(multiples);
    return e;
  }
}

Multiplication TermProd(String startFName, String functionPName):
{
  Val v;
  ArrayList<Val> Vals = new ArrayList<Val>();
}
{
  v = ValProd(startFName, functionPName)
  { Vals.add(v); }
  (
    <MUL>
    v = ValProd(startFName, functionPName)
    { Vals.add(v); }
  )*
  {
    Multiplication m = new Multiplication(Vals);
    return m;
  }
}

Val ValProd(String startFName, String functionPName):
{
  Token t;
  FCall fCall;
}
{
  (
    t = <DIGITS>
    {
      Digits d = new Digits(Integer.parseInt(t.image));
      return d;
    }
    |
    fCall = FCallProd(startFName, functionPName)
    { return fCall; }
    |
    t = <PARAM>
    {
      if(!functionPName.equals(t.image)) {
        throw new CustomParseException(String.format("Invalid parameter name '%s' "
          + "used inside function '%s'", t.image, startFName));
      }
      Param p = new Param();
      return p;
    }
  )
}

FCall FCallProd(String startFName, String functionPName):
{
  Token t;
  Expression expression;
}
{
  t = <FNAME>
  <LPB>
  expression = ExpressionProd(startFName, functionPName)
  <RPB>
  {
    FCall fCall = new FCall(t.image, expression, startFName);
    FCallEdge.allFCallEdges.add(new FCallEdge(startFName, t.image));/* Create a FCallEdge for this call••••••••• */
    return fCall;
  }
}