Java Reference
In-Depth Information
2. Revise the grammar to achieve the desired parse tree.
3. Verify that the revised grammar is still suitable for parser construction.
For example, if JavaCUP or yacc must process the grammar, then the
grammar should remain LALR(1) after revision.
4. Verify that the grammar still generates the same language. This is usu-
ally accomplished using (grammar-specific) proof techniques or rigorous
testing.
For the problem at hand, we can avoid a global
base
variable if we can process
the base early, and then have it propagate up the parse tree along with the
value of the processed input string. The semantic value synthesized up the
tree becomes a
tuple
(i.e., a struct in C or a class in Java
TM
) containing both
the value of the digits thus far and the base used to compute that value.
Figure 7.8(b) sketches the parse tree we desire for the input x5431$.
The x and the first d (which specifies the base) are processed in the triangle; the
base can then propagate up the tree and participate in the semantic actions.
From this tree we rewrite the rules for Digs to obtain the grammar shown in
Figure 7.8(a).
The grammar in Figure 7.8(a) reflects the newly structured parse tree. The
semantic value for Digs consists of two components,
val
and
base
, that represent
respectively the interpreted value of the input string thus far and the base for
the interpretation. The semantic actions for Rule 2 serve to copy the base from
its inception at Rule 3.
Experienced compiler writers make frequent use of rich semantic types
and grammar restructuring to localize the e
ects of semantic actions. The
resulting parsers are (mostly) free of global variables and easier to understand
and modify.
Unfortunately,ourgrammarmodification is deficient because it e
ff
ff
ected a
subtle change in the language (see Exercise 2).
In this section we discuss how semantic actions can be performed in top-down
parsers. Such parsers are typically generated by hand, using the
recursive-
descent
style discussed in Chapters 2 and 5. The result of such parser con-
struction is simply a program; semantic actions can be written directly into the
parser.
To illustrate this style of translation, we consider the processing of Lisp-
like [McC60, FF86] expressions, defined by the grammar shown in Figure 7.9.
