Chapter 5: Top-Down Parsing

• Overview
• Studio
• Lab

Lab

Getting Started

• Locate and install the lab5 project into your eclipse workspace as directed by your instructor, following the usual instructions, including those for an ant build.
• Browse this lab document to get an idea of the work you will do for this assignment.

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 lab5 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

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.

   Note: A Symbol type has two components:

   sym

   is 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

   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.
5. Make sure your solution works on all of the provided test files. Note well the following:

   • Be certainly only to 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

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
	;