Objective To demonstrate working knowledge of derivation and

Objective:
To demonstrate working knowledge of derivation and parsing.
Required:
Write a program that tokenizes and parses an expression, generates the derivation, and the Parse Trees for
that expression given the simple grammar below. Your program should indicate that an expression is invalid
if it does not follow the grammar. Moreover, it should demonstrate that this grammar is ambiguous. The next
step is to propose and make some changes to the grammar to make it unambiguous.
Submit a soft copy of the program, with a hard copy of the program, and sample outputs. Please include the
honor code. The programming languages that can be used to write the parser are Lisp, C++, or Java. Your
name should be on all documents submitted.
The grammar is:
e ::= n | e+e | e-e
n ::= d | nd
d ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
where e is the start symbol. Symbols e, n, d are nonterminals, and 0-9, +, and – are the
terminals

grammar SimpleCalc;

tokens {

PLUS = \'+\' ;

MINUS = \'-\' ;

MULT = \'*\' ;

DIV = \'/\' ;

}

@members {

public static void main(String[] args) throws Exception {

SimpleCalcLexer lex = new SimpleCalcLexer(new ANTLRFileStream(args[0]));

CommonTokenStream tokens = new CommonTokenStream(lex);

SimpleCalcParser parser = new SimpleCalcParser(tokens);

try {

parser.expr();

} catch (RecognitionException e) {

e.printStackTrace();

}

/*------------------------------------------------------------------

* PARSER RULES

*------------------------------------------------------------------*/

/*to print parse tree:*/

public class ParseTree implements Iterable<ParseTree> {
    /** The grammar symbol represented by this node of the tree. */
    private final Symbol symbol;

    /** The children of this parse tree node, in the order in which they appear */
    private final List<ParseTree> children;

    /**
     * Constructs a new parse tree wrapping the given symbol with the given
     * children.
     *
     * @param symbol The symbol at this parse tree node.
     * @param children The children of this parse tree node.
     */
    public ParseTree(Symbol symbol, List<ParseTree> children) {
        if (symbol == null || children == null)
            throw new NullPointerException();

        this.symbol = symbol;
        this.children = children;
    }

    /**
     * Constructs a new parse tree node holding the given symbol, but with
     * no children.
     *
     * @param symbol The symbol held by this parse tree node.
     */
    public ParseTree(Symbol symbol) {
        this(symbol, new ArrayList<ParseTree>());
    }

    /**
     * Returns the symbol held by this parse tree node.
     *
     * @return The symbol held by this parse tree node.
     */
    public Symbol getSymbol() {
        return symbol;
    }

    /**
     * Returns a mutable view of the children of this parse tree node.
     *
     * @return A mutable view of the children of this parse tree node.
     */
    public List<ParseTree> getChildren() {
        return children;
    }

    /**
     * Returns a mutable iterator to traverse the children of this parse tree.
     *
     * @return A mutable iterator traversing the children of this node.
     */
    public Iterator<ParseTree> iterator() {
        return getChildren().iterator();
    }

    /**
     * Returns a human-readable representation of the parse tree.
     *
     * @return A human-readable representation of the parse tree.
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(symbol);
        if (symbol instanceof Nonterminal) {
            builder.append(\" -> \");
            builder.append(getChildren());
        }
        return builder.toString();
    }
}