Java Reference
In-Depth Information
One method of understanding an LR parse is to appreciate that such parses
construct rightmost derivations in reverse. Given a grammar and a rightmost
derivation of some string in its language, the sequence of productions applied
by an LR parser is the sequence used by the rightmost derivation, but played
backwards. Figure 6.2 shows a grammar and the rightmost derivation of a
string in the grammar's language. The language is suitable for expressing
sums in a prefix (Lisp-like) notation. Each step of the derivation is annotated
with the production number used at that step. For this example, the derivation
of the string plus num num $ is achieved by applying Rules 1, 2, 3, and 3.
A bottom-up (LR) parse is accomplished by playing this sequence back-
wards: Rules 3, 3, 2, and 1. In contrast to LL parsing, an LR parser finds
the RHS of a production and replaces it with the production's LHS. First, the
leftmost num is
reduced
to an E by the rule E
num. This rule is applied again
to obtain plus E E $. The sum is then reduced by E
→
plus E E to obtain E$.
This can then be reduced by Rule 1 to the goal symbol Start.
→
Section 6.2.1 presents the order in which productions are applied to perform
a bottom-up parse. We next examine
how
the RHS of a production is found so
that a reduction can occur. The actions of anLRparser are somewhat analogous
to
knitting
. Figure 6.1 illustrates this by showing a parse in progress for the
grammar and string of Figure 6.2. The right needle contains the currently
unprocessed portion of the string: num $. The left needle is the parser's stack,
plus num, which represents the processed portion of the input string.
A
shift
operation transfers a symbol from the right needle to the left
needle. When a
reduction
by the rule A
γ
must occur at the sharp end of the left needle—that is, at the
top
of the parse
stack. Reduction by A
→γ
is performed, the symbols in
and prepends the LHS
symbol A to the unprocessed input of the right needle. A is then treated as
an input symbol to be shifted onto the left needle. To illustrate the parse tree
under construction, Figure 6.1 shows the symbols in
→γ
removes the symbols in
γ
as children of A.
We now follow the parse that is illustrated in Figure 6.1. In Figure 6.1(a),
the left needle shows that two shifts have been performed. With plus num
on the left needle, it is time to reduce by E
γ
→
num. Figure 6.1(b) shows the
e
ect of this reduction, with the resulting E prepended to the input. This same
sequence of activities is repeated to obtain the state shown in Figure 6.1(c)
where the left needle contains plus E E. When reduced by E
ff
plus E E,we
obtain Figure 6.1(d). The resulting E$is shifted (Figure 6.1(e)) and reduced
by Start
→
E$(Figure 6.1(f)). The parse is accepted when the Start symbol is
moved from the right needle to the left needle (not shown).
→
