Overview

• This lab requires that you install or set up some infrastructure that we'll be using throughout the rest of this course. Please follow the "setup" portion of this lab right away.
  If there is a problem, we can resolve it quickly and get you underway
• 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

Setup

1. Download the following files for use the rest of the semester.

   Make sure they are saved as .jar files! Internet Explorer tried to save them as zip files in CEC

   Put them in a reliable place (for example,

   Windows	Linux	Mac OS X
   C:\CS431Tools\	/usr/lib/	/Library/431Tools/

   because you'll need to reference them from the ant build file.

   • Download this java-cup-11a.jar file from the CUP project.
   • Download this JFlex.jar file from the JFlex project.
2. Now download and install the eclipse project for this lab:
   1. Download this hw2.zip file and put it in a temporary but handy spot (like your Desktop).
   2. From eclipse, click File → Import … and choose Existing Projects into Workspace
   3. Click Select archive file and browse to select the hw2.zip archive file you downloaded
   4. The project CSE431hw2 should appear and be selected for installation. Click Finish
3. In the Package Explorer, open the CSE431hw2 project.

   Eclipse, in its eagerness, has probably already tried to compile your project, but there are some automatically generated files that are missing, because we haven't really built the project yet.

   Silly eclipse.

   So don't worry about problems just yet.
4. In the Package Explorer, open the build.xml file for editing, because we are going to use eclipse's ant facility to build projects this semester; eclipse's built-in project builder doesn't know about the tools we're using.
   1. You must change the value of the toolpath property (currently "YourToolPath") to the directory or folder containing the CUP and JFlex jar files you've installed.
   2. Save your work on the build.xmlfile.
5. In some of the files for this lab, including some of the automatically generated Java files, there are references to CUP's runtime library, in the package java_cup.runtime. We must make eclipse aware of this:
   1. Click on the CSE431hw2 in the Package Explorer
   2. Click File→Properties
   3. Click Java Build Path
   4. Select the Libraries tab
   5. Click Add External JARs…
   6. Add the java-cup-11a.jar file to the list by browsing for the location at which you stored the file. You do not need the JFlex jar file.
6. Now we will build the project using eclipse's ant facility:
   1. From the Package Explorer, right-click build.xml and select Run as → Ant build…
   2. On the JRE tab, click Run in the same JRE as the workspace.

      This makes eclipse's internal Java compiler available to the build process.

   3. On the Refresh tab, click Refresh resources on completion

      This makes eclipse aware of the new files generated by the build process (the scanner and parser).

   4. Click Run to execute the build file. If all goes well, you should see in the Console window:
      1. cup output showing code written to Parser.java and sym.java
      2. jflex output showing Yylex.java was generated
      3. javac showing that files were compiled.
   • If you encountered problems in the above, seek help from the TA or the professor, preferably using IM.
   • If you didn't have problems, then the next time you need to build, you don't need to go through the above steps. Just click on the handy green arrow with the red toolkit icon to run the build process again with the same options as previously.

     Go ahead and try that.

7. Next let's try executing the project, even though it won't do much yet.
   1. Select the tdn or bup class from the default package (you may have to expand the package to see the classes) in the Package Explorer.
   2. Right-click the file, select Run as → Run…
   3. Choose Java Application
      • In the Classpath tab add java-cup-11a.jar to the list as an External Jar File
      • In the Arguments tab, specify the input file, such as TestFiles/good1
   4. Click Run
   You can rerun the application using the green arrow button without having to respecify the above information.

Assignment

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 RecursiveDescent.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 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. For this part, you will modify only the file RecursiveDescent.java.

   Something you need to know: A Symbol type has two components:

   sym

   is the int reflecting the type of the symbol as defined in sym.java

   value

   is 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.

   To turn in this part, send mail to legrand@cs.wustl.edu with the subject line 'homework 2a lastname_firstname', and attach your RecursiveDescent.java

5. [To be done in studio on 18 February 2008] 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, send mail to legrand@cs.wustl.edu with the subject line 'homework 2b lastname_firstname', and attach your addhaque.cup

Notes

• 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 RecursiveDescent.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.

Appendix: Grammar for addhaque calculator

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
	;