Java Reference
In-Depth Information
1 Start
→
E$
2 E
→
plus E E
3
|
num
Rule Derivation
1
Start
⇒
rm
E$
2
⇒
rm
plus E E $
3
⇒
rm
plus E num $
3
⇒
rm
plus num num $
Figure 6.2: Grammar and rightmost derivation of plus num num $.
Based on the input string and the sequence of shift and reduce actions,
symbols transfer back and forth between the needles. The artifact of the
knitting is the parse tree, shown on the last needle if the input string is accepted.
Before considering an example in some detail, we present a simple driver
for our shift-reduce parser in Figure 6.3. The parsing engine is driven by
a table, whose entries are discussed in Section 6.2.4. The table is indexed at
Marker
1
using the parser's
current state
and the next (as yet, unprocessed)
input symbol. The
current state
of the parser is defined by the contents of the
parser's stack. To avoid rescanning the stack's contents prior to each parser
action, state information is computed and storedwith each symbol shifted onto
the stack. Thus, Marker
1
need only consult the state information associated
with the stack's topmost symbol. The parse table calls for a shift or reduce as
follows:
•
Marker
2
performs a shift of the next input symbol to state
s
.
•
A reduction occurs at Markers
4
and
5
. The RHS of a production is
popped o
ff
the stack and its LHS symbol is prepended to the input.
The parser continues to perform shift and reduce actions until one of the
following situations occurs:
•
The input is reduced to the grammar's goal symbol at Marker
3
.The
input string is
accepted
.
•
No valid action is found at Marker
1
. In this case, the input string has
asyntaxerror.
