Lab 2: Recursive-Descent Compilers
Lab Assigned Lab Due
(Start of class)
29 Jan 12 Feb


Abstract: Using two parsing methods, you will implement a simple expression evaluator.
A CUP (Constructor of Useful Parsers) grammar specification appears at the end of this document for a language I'll call Add Haque. This specification is found in the file addhaque.cup. The language generated by this grammar includes Lisp-like prefix expressions such as
(plus 3 5)
The semantic meaning of this expression is the value resulting from adding 3 to 5. Similarly, an expression such as
(sum 1 2 3 4 5)
is intended to produce 15---the sum of its arguments. While operators like plus and times have exactly two arguments, sum could have one or more arguments.

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

(sum (times 3 (plus 3 4)) (negate 3))
should produce the value 18.
Expression Meaning
(plus a b) a + b
(minus a b) a - b
(negate a) - a
(sum a1 a2 ... aN) sum of a1 through aN
(product a1 a2 ... aN) product of a1 through aN
(mean a1 a2 ... aN) (sum of a1 through aN) divided by N
  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.
Some details:
CUP specification for AddHaque: addhaque.cup
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
	;