Any argument could itself be a parenthesized, prefix expression. The string

1. Design a grammar free of left-recursion for the language Add Haque. The final grammar you use for your top-down parser should be placed in the Parse.java file, as indicated by the comments, as your answer for this part. Your implementation must agree with your stated grammar for this part or points will be deducted.
2. Compute the First() and Follow() sets for each nonterminal in the grammar. Place your answer in the Parse.java file, as indicated by the comments.
3. Implement a recursive-descent, predictive parser for this language. Your implementation must agree with the grammar you provided as your answer for question (1). For each ``outermost'' expression in a file, print the value associated with the expression. For this part, you will modify only the file Parse.java. To turn in this part, use the following, substituting your own last and first names: mail -s 'homework 2a lastname_firstname' cs431@cec < Parse.java Do not submit by any other method.
4. Document how you treated the result of a (mean ...) expression. Place your answer in the Parse.java file, as indicated by the comments.
5. Augment the given CUP grammar specification to include actions that compute the values of the expressions bottom-up. For each ``outermost'' expression, print the value associated with the expression. For this part, you will modify only the file addhaque.cup. Note that this file is already suitable for bottom-up parsing: you need not use your top-down grammar for this part. However, some modification of this file will make your job substantially easier. To turn in this part, use the following, substituting your own last and first names: mail -s 'homework 2b lastname_firstname' cs431@cec < addhaque.cup Do not submit by any other method.

• As before, set things up by performing the following steps:
  1. Create a new directory for your work: mkdir hw2
  2. Change into that directory: cd hw2
  3. Set things up by typing make -f ~cs431/hw2/Makefile Setup
• If you prefer, you can unzip this and try it on your PC. Support is offered only for the UNIX version.
• You will find all the files you need for this project linked in your hw2 directory:

  Parse.java	The skeleton for your predictive parser.
  addhaque.cup	The CUP grammar specification file.
  TestFiles	The directory of test files for this project

• The following will be useful as you develop your solution:

  make	Brings your work up-to-date by compiling modified files.
  java tdn file	Runs your top-down (recursive-descent) parser on file
  java bup file	Runs your bottom-up parser on file
  cd ~cs431/hw2/Soln followed by either of the above commands	Runs my solution for you

• In adding actions to the CUP specification file, consider changing the grammar to ease processing (while recognizing the same language, of course!).
• Be certainly only to modify the files Parse.java for your recursive-descent parser, and addhaque.cup for the CUP-based parser.
• Beware the use of global variables in either of the files you modify: global variables generally don't work well when there is recursion.
• There is an additional semantic type available for your use: IntPair. If a nonterminal is declared of that type, then for semantic symbol s you can use s.int1 and s.int2. You may find this useful for mean in your bottom-up parser.

import java_cup.runtime.*;
import hw2.*;
import Common.Listing;

terminal Integer number;
terminal         plus, minus, sum, product, times, negate, mean;
terminal         lparen, rparen;

non terminal Integer  Program, File, Lists, List, Expression;
non terminal Integer  Atom, Operand, Operands;

start with Program;

Program
	::= File
	;

File   
	::= Lists
	;

Lists
	::= Lists List
	|   List
	;

List
	::= lparen Expression rparen
	;

Expression
	::= plus    Operand Operand
	|   minus   Operand Operand
	|   times   Operand Operand
	|   negate  Operand
	|   sum     Operands
	|   product Operands
	|   mean    Operands
	;

Operand
	::= Atom
	;

Operands
	::= Operands Operand
	|   Operand
	;

Atom
	::= List
	|   number
	;