Chapter 5: Top-Down Parsing


Getting Started (5 minutes)

This studio is a continuation of the work you did in Studio 4.

In each of the following sections, go as far as you can in the time allotted, but move on to the next section so you'll have a chance to work on each section while in studio.

Warm Up: (10 minutes)

  1. Find the file in which you recorded the First and Follow sets from Studio 4. In eclipse, copy it from the studio4 package of the studio 4 project, and and then paste it into the studio5 package of the studio 5 project, replacing the Main that is there.

    Eclipse should refactor the copy so that its package header statement is correct.

  2. Follow the instructions for ant builds.
  3. Have your book open to Chapter 5, pages 145–149, to reference the material for computing Predict sets.
  4. Run the Main class as a Java Application
  5. This should produce some output in the console window.
  6. Look at the output, and look at the Example class given in

  7. If you have time, glance at the build.xml file. Discuss how it controls the build process you witnessed.

Main Problems

You will consider a sequence of grammars and use them to create corresponding recursive-descent parsers. All of your work should be done in, but you are welcome to create more test files if you wish.

For each rule of each grammar, you are asked which symbols predict that particular rule. Recall that the predict sets are computed primarily from First sets, but if a rule's right-hand side can derive the empty string, then the Follow set of the rule's left-hand side must also be included.

All of your work is given and can be done in the file. The information here is supplemental.

Before implementing any of these parsers, check your Predict sets with a neighboring group or the professor or TA.

Part 1 (20 minutes)

Complete the recursive-descent parsers for the grammars below, based on the First and Follow set analysis you developed in Studio 4. Be sure to use rule-specific Predict sets based on the First and Follow sets.
  1. MatchingParens A grammar that generates matching parentheses with an x in the middle. You should be able to write a recursive-descent parser for this grammar without changing the grammar at all.

  2. Problem1a
  3. Problem1d

Part 2 (20 minutes)

Do not comment out the work you have done so far. Instead, keep it going forward so that at the end, everything you've done is still in the run.
Continue with the following grammars, also using your work from Studio 4 to construct predict sets and implement the parser:
  1. Declarations This is a grammar that generates declaration statements for a list of variables. Take a look at the test files to get an idea of the language. To find out the names of the terminal symbols, look in the file. For example, the keyword "int" is represented by sym.INT.

    This grammar has left recursiion, which you must eliminate using the principled techniques for doing so.

  2. IfThenElseFi This grammar generates if-then-else-fi statements. The "fi" terminal always ends and brackets the "if". The grammar has problems you must address before you can write a recursive-descent parser.

Part 3 (20 minutes)

Part 4 (time permitting)

Finishing Up

Submit your work as directed by your instructor.

Copyright 2010 by Ron K. Cytron
Last modified 14:32:05 CDT 13 August 2010