Chapter 7: Syntax-Directed Translation
Getting Started (5 minutes)
- Review the
Studio Guidelines if necessary.
- Locate and install the studio7 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.
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)
- Follow the instructions for ant builds.
The ant build is relatively complex for this studio. Take a look at
the build.xml file if you have time.
As you work on each of the problems below, simply rerun the ant build, and
the results will be displayed on the console. (Recall you can click on the toolbox
green button to rerun the build.)
- If things seem to be messed up, run
the clean task followed by the default (run) build, and that should fix any problems.
Open the CUP User Manual
for quick reference.
You will consider a sequence of problems to be solved by bottom-up parsing.
This studio also includes a preview of the
syntax-directed parsing material from
Chapter 7, which
means that we will be translating inputs into some form as we parse.
Your work will be done in the various cup files found in the root
directory for this studio.
Part 1 (20 minutes)
- cup1a parses a comma-separated list of numerals.
The semantic actions are already in place to translate the numerals into
a numeric value.
numeral is parsed as a sequence of digits.
- Draw a parse tree for the numeral
431 and study how the bottom up parse computes the numeric value of the
digits from left to right. The semantic type used for the values is
the java.lang.Integer object.
- Be prepared to show (to a suitably curious observer)
when reductions take place. Be prepared to explain when the
semantic actions are performed and what they do.
- cup1b is the same problem, but uses a local class
in the action code block to carry the value up the parse tree.
Fill in your group's members' names.
You have to fill in the semantic actions.
Note to C++ programmars: declaring a variable in Java does not instantiate
it. Thus, RESULT is null unless you do something
Do not comment out your work so far. Instead, keep it going
forward so that at the end, everything you've done is still in the run.
- cup2 This grammar looks like the cup1 grammars.
This time, instead of producing the numeric value of the numerals, you are
to produce the count of the number of digits in the numeral.
Part 2 (20 minutes)
- cup3 Each sequence of numerals will now either be
interpreted base 10, as before, or
preceded by an x (terminal) and then interpreted base 16.
See the test files, both
good and bad, to get a better idea of how this works.
In your group, and with help from others as needed, develop a grammar to
parse and translate decimal and hexadecimal numerals into their numeric
Part 3 (20 minutes)
- cup4 An ordinary sequence of numerals is
still interpreted base 10.
Howeve, this time, if an x appears before the sequence,
the next numeral (d) value is one less than the base in which
the rest of the numerals should be interpreted. See the test files for
examples and counterexamples.
Submit your work as directed by your instructor.
Copyright 2010 by Ron K. Cytron
Last modified 14:32:05 CDT 13 August 2010