Assignment.jj

options {
    LOOKAHEAD = 2;
    FORCE_LA_CHECK = true;
}

PARSER_BEGIN(Assignment)
import java.util.*;

/**
 * Main class.
 */
public class Assignment {
    public static void main(String[] args) throws EvalException {
        Assignment parser = new Assignment(System.in);
        boolean eval = true;
        boolean debug = false;

        // Try to parse
        try {
            parser.Program();
        // Parsing exception
        } catch (ParseException e) {
            System.out.println("FAIL");
            System.err.println(e.getMessage());
            eval = false;
        // Exception elsewhere, should not happen
        } catch (Exception e) {
            System.out.println("FAIL");
            System.err.println("Non-parsing error: " + e.getMessage());
            if (debug) {
                e.printStackTrace();
            }
            eval = false;
        }

        // Try to eval
        if (eval) {
            if (debug) {
                for (String n: Functions.map.keySet()) {
                    String fn = Functions.map.get(n).toString();
                    System.out.println(fn);
                }
            }
            System.out.println("PASS");
            // Start evaluation by calling MAIN with no parameters and catch
            // any errors during evaluations.
            try {
                System.out.println(Functions.map.get("MAIN").eval(new int[0]));
            } catch (RecursionException e) {
                System.out.println("DIVERGENCE");
            } catch (EvalException e) {
                System.err.println("Eval error: " + e.getMessage());
            } catch (Exception e) {
                System.err.println("Non-eval error: " + e.getMessage());
                if (debug) {
                    e.printStackTrace();
                }
            }

        }
    }
}

/**
 * Class that stores data required for call checking and evaluation.
 * "map" contains a map of all function names to their corresponding Function
 * objects.
 * "calls" contains a set of all calls potentially performed by the program,
 * which are checked for validity during the parsing stage.
 * "stack" contains the stack of calls made during evaluation of an expression
 * in order to determine if a call leads to recursion.
 */
class Functions {
    public static Map<String, Function> map = new HashMap<String, Function>();
    public static Set<Call> calls = new HashSet<Call>();
    public static Stack<Call> stack = new Stack<Call>();
    // Maximum parameters is set to 1 to accommodate the specification, but for
    // potential future expansion multi-argument functions are supported, where
    // a definition would be in the form:
    //     DEF ADD x y { x+y } ;
    // and a call would be in the form:
    //     ADD(1+1 1+2*3)
    public static int maxargs = 1;
}

/**
 * Exception raised during evaluation.
 */
class EvalException extends Exception {
    public EvalException() {
        super();
    }
    public EvalException(String message) {
        super(message);
    }
}

/**
 * Recursion exception raised during evaluation.
 */
class RecursionException extends EvalException {
    public RecursionException() {
        super("Recursion");
    }
}

/**
 * Interface that needs to be implemented by all the elements of an expression.
 */
interface Evalable {
    /**
     * Evaluates the element of an expression given a mapping of parameters to
     * numeric values that correspond to the parameters covering the scope of
     * the expression.
     *
     * @param  args          mapping of numeric values to named parameters
     * @throws EvalException thrown if an error occurs during evaluation
     */
    public int eval(Map<String, Integer> args) throws EvalException;

    /**
     * Returns the line number of the element within the program.
     *
     * @return line number
     */
    public int getLine();

    /**
     * Returns the column number of the element within the program.
     *
     * @return column number
     */
    public int getColumn();

    /**
     * Returns a representation of the element in a manner that helps
     * understand the underlying AST of the element. Useful for debugging.
     *
     * @return a string representation of the element
     */
    public String toString();
}

/**
 * Represents a positioned element within the program. Used as the base for
 * all the nodes in the AST to easily implement getLine() and getColumn() for
 * potential future expansion of evaluation messages.
 */
class Positioned {
    public final int line;
    public final int column;

    /**
     * Token-based constructor, takes position from token's starting position.
     *
     * @param t first token in the element being represented.
     */
    public Positioned(Token t) {
        this.line = t.beginLine;
        this.column = t.beginColumn;
    }

    /**
     * Manual constructor.
     *
     * @param line   line number of the element
     * @param column column number of the element
     */
    public Positioned(int line, int column) {
        this.line = line;
        this.column = column;
    }

    /**
     * Returns the line number of the element within the program.
     *
     * @return line number
     */
    public int getLine() {
        return line;
    }

    /**
     * Returns the column number of the element within the program.
     *
     * @return column number
     */
    public int getColumn() {
        return column;
    }
}

/**
 * Represents a function that can be called with an array of numeric arguments.
 */
class Function extends Positioned {
    public final String name;
    public final String[] args;
    public final Evalable expr;

    /**
     * Constructor.
     *
     * @param name name of the function
     * @param args array of named parameters
     * @param expr body of the function
     * @param line line number of the function occurrence in the program
     */
    public Function(String name, String[] args, Evalable expr, int line) {
        super(line, 0);
        this.name = name;
        this.args = args;
        this.expr = expr;
    }

    /**
     * Begins the evaluation of a function given its parameters.
     *
     * @param  args          array of numeric values corresponding to the
     *                       function parameters
     * @return               numeric value returned by the function
     * @throws EvalException thrown if an error occurs during evaluation
     */
    public int eval(int[] args) throws EvalException {
        // Check if we have the correct number of arguments
        if (args.length != this.args.length) {
            throw new EvalException("Incorrect number of arguments.");
        }
        // Create a mapping from the named parameters to the values, which is
        // required by all the elements implementing Evalable.
        Map<String, Integer> nargs = new HashMap<String, Integer>();
        for (int i = 0; i < args.length; i++) {
            nargs.put(this.args[i], args[i]);
        }
        // Eval the body of the function
        return expr.eval(nargs);
    }

    /**
     * Creates a String representation of the function. Useful for debugging as
     * it shows the structure of the AST of the body.
     *
     * @return a string representing the function
     */
    public String toString() {
        String r = name+"(";
        for (int i = 0; i < args.length; i++) {
            if (i == args.length-1) {
                r += args[i];
            } else {
                r += args[i]+",";
            }
        }
        return r+"):="+expr;
    }
}

/**
 * Represents a number in the AST.
 */
class Number extends Positioned implements Evalable {
    public final int value;

    /**
     * Token-based constructor.
     *
     * @param t token corresponding to the number.
     */
    public Number(Token t) {
        super(t);
        this.value = Integer.parseInt(t.image);
    }

    /**
     * Manual constructor.
     *
     * @param value  string representation of the Number's value
     * @param line   line number of the Number's occurrence in the program
     * @param column column number of the Number's occurrence in the program
     */
    public Number(String value, int line, int column) {
        super(line, column);
        this.value = Integer.parseInt(value);
    }

    /**
     * Manual constructor.
     *
     * @param value  the Number's value
     * @param line   line number of the Number's occurrence in the program
     * @param column column number of the Number's occurrence in the program
     */
    public Number(int value, int line, int column) {
        super(line, column);
        this.value = value;
    }

    public int eval(Map<String, Integer> args) {
        // Simply return the value of the Number, the parameters are ignored.
        return value;
    }

    public String toString() {
        return Integer.toString(value);
    }
}

/**
 * Represents a parameter in the AST.
 */
class Parameter extends Positioned implements Evalable {
    public final String name;

    /**
     * Token-based constructor.
     *
     * @param t token corresponding to the parameter.
     */
    public Parameter(Token t) {
        super(t);
        this.name = t.image;
    }

    /**
     * Manual constructor.
     *
     * @param name   the Parameter's name
     * @param line   line number of the Parameter's occurrence in the program
     * @param column column number of the Parameter's occurrence in the program
     */
    public Parameter(String name, int line, int column) {
        super(line, column);
        this.name = name;
    }

    public int eval(Map<String, Integer> args) {
        // Look up the value of the parameter in the mapping passed as the
        // argument.
        return args.get(name);
    }

    public String toString() {
        return name;
    }
}

/**
 * Represents a call to a function in the AST.
 */
class Call extends Positioned implements Evalable {
    public final String function;
    public final Evalable[] args;

    /**
     * Token-based constructor.
     *
     * @param t    token corresponding to the token representing the function
     *             being called
     * @param args parameters being passed to the function being called
     */
    public Call(Token t, Evalable[] args) {
        super(t);
        this.function = t.image;
        this.args = args;
    }

    /**
     * Manual constructor.
     *
     * @param function name of the function being called
     * @param args     parameters being passed to the function being called
     * @param line     line number of the Call's occurrence in the program
     * @param column   column number of the Call's occurrence in the program
     */
    public Call(String function, Evalable[] args, int line, int column) {
        super(line, column);
        this.function = function;
        this.args = args;
    }

    public int eval(Map<String, Integer> args) throws EvalException {
        int retval;
        // If the same call occurs previously in the call stack we are in a
        // recursive loop due to the language not having any branching.
        if (Functions.stack.search(this) > -1) {
            throw new RecursionException();
        }
        // If we are not in a loop push this call to the call stack.
        Functions.stack.push(this);
        // Evaluate the parameters being passed to the function, as the
        // function eval only accepts numeric values.
        int[] iargs = new int[this.args.length];
        for (int i = 0; i < iargs.length; i++) {
            iargs[i] = this.args[i].eval(args);
        }
        // Get the return value.
        retval = Functions.map.get(function).eval(iargs);
        // Remove the call from the call stack once we are done, as it can
        // be repeated later outside its own branch without causing recursion.
        Functions.stack.pop();
        // Return the return value.
        return retval;
    }

    public String toString() {
        String r = function+"(";
        for (int i = 0; i < args.length; i++) {
            if (i == args.length-1) {
                r += args[i];
            } else {
                r += args[i]+",";
            }
        }
        return r+")";
    }
}

/**
 * Represents a product in the AST.
 */
class Product extends Positioned implements Evalable {
    public final Evalable factor1;
    public final Evalable factor2;

    /**
     * Constructor.
     *
     * @param factor1 one of the factors of the product
     * @param factor2 the other factor of the product
     * @param line    line number of the Product's occurrence in the program
     * @param column  column number of the Product's occurrence in the program
     */
    public Product(Evalable factor1, Evalable factor2, int line, int column) {
        super(line, column);
        this.factor1 = factor1;
        this.factor2 = factor2;
    }

    public int eval(Map<String, Integer> args) throws EvalException {
        // We simply return the product of the evaluate factors
        return factor1.eval(args)*factor2.eval(args);
    }

    public String toString() {
        return "("+factor1+"*"+factor2+")";
    }
}

/**
 * Represents a sum in the AST.
 */
class Sum extends Positioned implements Evalable {
    public final Evalable summand1;
    public final Evalable summand2;

    /**
     * Constructor.
     *
     * @param summand1 one of the summands of the sum
     * @param summand2 the other summand of the sum
     * @param line     line number of the Sum's occurrence in the program
     * @param column   column number of the Sum's occurrence in the program
     */
    public Sum(Evalable summand1, Evalable summand2, int line, int column) {
        super(line, column);
        this.summand1 = summand1;
        this.summand2 = summand2;
    }

    public int eval(Map<String, Integer> args) throws EvalException {
        // We simply sum the two evaluated summands.
        return summand1.eval(args)+summand2.eval(args);
    }

    public String toString() {
        return "("+summand1+"+"+summand2+")";
    }
}

PARSER_END(Assignment)

/**
 * Tokens for matching.
 */
TOKEN :
{
        < PLUS  : "+" >
    |   < TIMES : "*" >
    |   < LPAR  : "(" >
    |   < RPAR  : ")" >
    |   < LANG  : "{" >
    |   < RANG  : "}" >
    |   < S     : " " >
    |   < DEF   : "DEF" >
    |   < MAIN  : "MAIN" >
    |   < EOL   : ";" ( "\r" | "\n" | "\r\n" ) >
    |   < FUNC  : ( <UPPER> )+ >
    |   < PARAM : ( <LOWER> )+ >
    |   < NUM   : ( <DIGIT> )+ >
}
TOKEN :
{
        < #DIGIT : ["0"-"9"] >
    |   < #UPPER : ["A"-"Z"] >
    |   < #LOWER : ["a"-"z"] >
}

/**
 * Production for the entire program, entry point into the parsing of the
 * program. Every function that is defined is stored in Functions.map and
 * every call made in the program is stored in Functions.call.
 */
void Program() : { Function f; int i = 1; }
{
    // Find definitions and increase the line counter since every definition
    // is on a single line. Definitions are stored in Functions.map.
    ( f = Def(i++) { Functions.map.put(f.name, f); }
    )+ <EOF> {
        // Check if a MAIN function is defined.
        if (!Functions.map.containsKey("MAIN")) {
            throw new ParseException("No MAIN function.");
        }
        // Check if all calls made in the program are valid.
        for (Call c : Functions.calls) {
            if (!Functions.map.containsKey(c.function) ||
                Functions.map.get(c.function).args.length != c.args.length) {
                throw new ParseException("Call to non-existent function \"" +
                                         c + "\" at line " + c.line +
                                         ", column " + c.column + ".");
            }
        }
    }
}

/**
 * Production for Function definitions.
 *
 * @param  i the current line number in the program input.
 * @return   a Function object representing the matched function.
 */
Function Def(int i) : {
    Token t;
    Evalable e;
    List<String> l = new ArrayList<String>();
    Set<String> s = new HashSet<String>();
}
{
    <DEF> <S>
    (
        // Determine if the function is MAIN or not, and in the latter case
        // determine its parameters.
            ( t = <MAIN> )
        |   ( t = <FUNC> (
                <S> <PARAM> { l.add(token.image); } l = Params(l) )?
            )
    ) { s.addAll(l); }
    // Create the function body by finding the operation with the lowest
    // precedence and letting it be built up from there.
    <S> <LANG> <S> e = Sums(s) <S> <RANG> <S> <EOL>
    {
        return new Function(t.image, l.toArray(new String[l.size()]), e, i);
    }
}

/**
 * Performs the matching of all parameters when a function is being defined.
 *
 * @param  l the partial list of all parameters
 * @return   the complete list of all parameters
 */
List<String> Params(List<String> l) : { Token t; }
{
    ( <S> t = <PARAM> { l.add(t.image); } )* { return l; }
}

/**
 * Production for the Evalable expressions of the highest precedence. These are
 * either nullary expressions (parameters, numbers) followed by unary
 * expressions (function calls).
 *
 * @param  s the set of all valid parameter names in the expression
 * @return   a nullary or unary Evalable
 */
Evalable Nullnary(Set<String> s) : {
    Token t;
    Evalable e;
    List<Evalable> l = new ArrayList<Evalable>();
}
{
    // Matches a number
        <NUM> { return new Number(token); }
    // Matches a parameter
    |   <PARAM> {
            // Checks if the parameter is valid for the expression
            if (!s.contains(token.image)) {
                throw new ParseException("Incorrect parameter \"" +
                                         token.image + " at line " +
                                         token.beginLine + ", column " +
                                         token.beginColumn + ".");
            }
            return new Parameter(token);
        }
    // Matches a function call
    |   t = <FUNC> <LPAR>
        // Matches all the parameters a function can accept, functions need
        // at least 1 parameter.
        ( e = Sums(s) { l.add(e); } l = CallParams(s, l) )? <RPAR> {
            // Check if we exceed the maximum number of parameters
            if (l.size() > Functions.maxargs) {
                throw new ParseException("Too many parameters, found " +
                                         l.size() + " (maximum is " +
                                         Functions.maxargs + ") at line " +
                                         t.beginLine + ", column " +
                                         t.beginColumn + ".");
            }
            // Create the new call and add it to the set of all calls
            Call c = new Call(t, l.toArray(new Evalable[l.size()]));
            Functions.calls.add(c);
            return c;
        }
}

/**
 * Performs the matching of all parameters when a function is being called.
 *
 * @param  s the set of all valid parameter names in the expression
 * @param  l the partial list of all parameters
 * @return   the complete list of all parameters
 */
List<Evalable> CallParams(Set<String> s, List<Evalable> l) : { Evalable e; }
{
    ( <S> e = Sums(s) { l.add(e); } )* { return l; }
}

/**
 * Initialises the matching of a product in the language. If no product can be
 * created an expression of the closest existing higher precedence is returned.
 *
 * @param  s the set of all valid parameter names in the expression
 * @return   the product or higher precedence expression
 */
Evalable Products(Set<String> s) : { Evalable e; }
{
    e = Nullnary(s) e = CreateProduct(s, e) { return e; }
}

/**
 * Performs the matching of a product in the language.
 *
 * @param  s the set of all valid parameter names in the expression.
 * @param  p the partal product so far
 * @return   the final product
 */
Evalable CreateProduct(Set<String> s, Evalable p) : { Evalable e; }
{
    ( <TIMES> e = Nullnary(s) {
        p = new Product(p, e, p.getLine(), p.getColumn());
    } )* { return p; }
}

/**
 * Initialises the matching of a sum in the language. If no sum can be created
 * an expression of the closest existing higher precedence is returned.
 *
 * @param  s the set of all valid parameter names in the expression
 * @return   the sum or higher precedence expression
 */
Evalable Sums(Set<String> s) : { Evalable e; }
{
    e = Products(s) e = CreateSum(s, e) { return e; }
}

/**
 * Performs the matching of a sum in the language.
 *
 * @param  s the set of all valid parameter names in the expression.
 * @param  p the partal sum so far
 * @return   the final sum
 */
Evalable CreateSum(Set<String> s, Evalable p) : { Evalable e; }
{
    ( <PLUS> e = Products(s) {
        p = new Sum(p, e, p.getLine(), p.getColumn());
    } )* { return p; }
}