Java Reference
In-Depth Information
•
Consider the parse tree shown in Figure 7.4(b). As was the case with
our previous example, the first d symbol is processed first by Rule 5 and
the remaining d symbols are processed by Rule 4. If the string is to be
interpreted base-8, then the semantic action for Rule 4 should multiply
the number passed up the parse tree by 8; otherwise, 10 should be used
at the multiplier.
Unfortunately, the grammar of Figure 7.4(a) will cause the o to be shifted
on the stack. Because semantic actions are allowed only at reductions,
no action is possible at that point. When the semantic actions for Rule 4
execute, it is unknown whether we are processing a base-10 or base-8
number.
Such situations arise often in the context of syntax-directed translation. The
structure of the parse (as seen in Figure 7.4(b)) is not well suited to the transla-
tion task at hand. In terms of attribute propagation up the parse tree (synthe-
sized attributes), the information required at a semantic action is not available
from below.
We next discuss a number of approaches for remedying this problem
and consider their advantages and disadvantages. Each approach involves
some modification to the grammar, so a word of caution is in order before
we begin: In general, there can be no algorithm that determines whether the
languages denoted by two context-free grammars are the same. This means
that when a grammar is modified, it cannot in general be proved that the
modification did not change the language in some unacceptable way. Also,
grammar modification can a
ect the suitability of the grammar for a given
parsing technique. Thus, grammar modifications must be performed with
great care:
ff
•
At the beginning of such a project, sample inputs should be written for
submission to the parser. The samples should include inputs that should
and should not be accepted by the parser, and the sample set should be
as complete as possible.
•
Grammar changes should be planned and carried out in small steps.
•
After each step,
regression tests
should ensure that the parser based on
the new grammar accepts and rejects the proper set of strings.
As dictated by common software engineering practices, bugs that develop
because of faults in the parser or grammar should be resolved and then turned
into new regression tests. This will ensure the bug does not resurface if the
grammar or parsing actions are subsequently modified.