## CS 431 (Spring 2002)

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:
• 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.
 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 ; ```