Chapter 5: Top-Down Parsing
Getting Started (5 minutes)
- Review the
Studio Guidelines if necessary.
- Locate and install the studio5 project into your
eclipse workspace as directed by your instructor,
following the usual instructions.
- Open report.txt in eclipse, fill in your team members' names, and
keep the file open so that you can record your findings.
- Browse this studio document to get an idea of the work you will do in this session.
This studio is a continuation of the work you did in
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)
- Find the Main.java 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.
- Follow the instructions for ant builds.
- Have your book open to Chapter 5,
pages 145–149, to reference the material for computing
- Run the Main class as a Java Application
This should produce some output in the console window.
- Look at the output, and look at the Example class given
- Look at the method getTestFiles() and see how it
supplies the testfiles used for this grammar's parse.
- Look at the methods in this class (S() and B())
and see how they accurately
reflect the grammar.
- Look at how the terminal symbol a is referenced
as sym.a in the code. Open sym class to see
where those symbols appear. That file is automatically generated by
the compiler tools, so you will find it in the autogen package.
- Look at the use of int peek(), void expect(char),
and void oops(String) are used in the code.
- If you have time, glance at the build.xml file.
Discuss how it controls the build process you witnessed.
You will consider a sequence of grammars and use them to create
recursive-descent parsers. All of your work should be done in
Main.java, 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 Main.java
file. The information here is supplemental.
Before implementing any of these parsers,
check your Predict sets with a neighboring group or the professor or
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.
- 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.
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:
- 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 sym.java 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.
- 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)
Expressions There is just one grammar in this part -- an expression grammar with
- I already devoped a grammar suitable for Recursive Descent parsing.
- I implemented the methods for the parser.
- Your job: use parameter values and return values so that the
numerical computation is carried out by the parse.
Do not use any global varibles to do this, or the techinque
will fail when you do the Lab!
Part 4 (time permitting)
IfThenElse Do not implement a parser for this grammar, just try to make
the grammar suitable for top-down parsing.
Submit your work as directed by your instructor.
Copyright 2010 by Ron K. Cytron
Last modified 14:32:05 CDT 13 August 2010