Chapter 5: Top-Down Parsing


Getting Started

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




Here is a summary of the files for the top-down parsing assignment: 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 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
  2. Compute the First() and Follow() sets for each nonterminal in the grammar. Place your answer in the file, as indicated by the comments.
  3. Implement a recursive-descent, predictive parser for this language.
    Note: A Symbol type has two components:
    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.
    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 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 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
	::= File

	::= Lists

	::= Lists List
	|   List

	::= lparen Expression rparen

	::= plus    Operand Operand
	|   minus   Operand Operand
	|   times   Operand Operand
	|   negate  Operand
	|   sum     Operands
	|   product Operands
	|   mean    Operands

	::= Atom

	::= Operands Operand
	|   Operand

	::= List
	|   number