Programming Assignment 2

Getting Started

Update your repository. Locate and install the Labs/2 project into your eclipse workspace then use the ant file to build it, as explained in the previous lab.

Abstract: You will implement a simple expression evaluator using recursive-descent parsing.



Overview

A specification specification appears at the end of this document for a language called Add Haque. This specification is given in the form of a context-free grammar that is distributed as addhaque.cup with this assignment.

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, the expression
(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.

Here is an informal description of the language:

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


All values computed in this language are integer-valued, including the result computed by a mean expression.



Setup

After installing the software for this assignment, you should find the tdn class in the lab2 package, which executes the top- down parser using the code you will write into the RecursiveDescent class. The parser can be launched on the input tests using ant build target tdn.



Assignment

Here is a summary of the files for the top-down parsing assignment:

RecursiveDescent.java The skeleton for your top-down, predictive parser.
addhaque.cup The CUP grammar specification file from which a bottom-up parser is automatically constructed.
TestFiles The directory of test files for this project
tdn.java Contains the main for your top-down (recursive-descent) parser. There is a corresponding ant target tdn that executes the top-down parser on each test file in the TestFiles directory.

1. Design a grammar free of left-recursion for the language Add Haque. You can use the provided addhaque.cup grammar file as a starting point. The text contains techinques for this part in Section 5.5

* The resulting grammar should be placed in the RecursiveDescent.java file, as indicated by the comments, as your answer for this part.

* Your implementation (next part) must agree with the grammar you develop for this part.



2. Compute the First() and Follow() sets for each nonterminal in the grammar. Place your answer in the RecursiveDescent.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.
* Modify only the file RecursiveDescent.java, replacing the loop in the RecursiveDescent constructor with a call to the method associated with your grammar's start symbol.

* Your code must throw an error anytime a parse error occurs. * You will need to take the end of the file into account. There is a special symbol called EOF for this purpose (check the jflex file to see how it is created). Note: A Symbol type has two components:

sym: the int reflecting the type of the symbol as defined in the sym class. That class is generated automatically in the autogen package when you run the build.

value: the object associated with the symbol. For example, for the number type, this is an Integer object



4. Document how you treated the result of a (mean ...) expression. Place your answer in the RecursiveDescent.java file, as indicated by the comments.



5. Make sure your solution works on all of the provided test files.

Note well the following:

* You should only modify the RecursiveDescent.java file for this lab. No other files should be changed!

* Beware the use of global variables in either of the files you modify: global variables generally don't work well when there is recursion.



AddHaque Grammar

CUP specification for AddHaque: addhaque.cup
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
	;