Java Reference
In-Depth Information
Sentential
Transitions
Resulting
Prefix
Sentential Form
plus plus num num num $
plus plus num
States 1, 1, and 2
plus plus E num num $
plus plus E num States 1, 1, 5, and 2
plus plus E E num $
plus plus E E
States 1, 1, 5, and 6
plus E num $
plus E num
States 1, 5, and 2
plus E E $
plus E E
States 1, 5, and 6
E$
E$
States 1, 3, and 4
Start
Figure 6.12: Processing of plus plus num num num $ by the LR(0)
machine in Figure 6.11.
prefixes. Each transition shifts the symbols of a valid sentential form. When
the automaton arrives in a double-boxed state, it has processed a viable prefix
that ends with a handle. The handle is the RHS of the (unique) reducible item
in the state. At this point, a reduction can be performed. The sentential form
produced by the reduction can be processed anew by the CFSM. This process
can be repeated until the grammar's goal symbol is shifted (successful parse)
or the CFSM blocks (an input error).
For the input string plus plus num num num $, Figure 6.12 shows the re-
sults of repeatedly presenting the (reverse) derived sentential forms to the
CFSM. This approach serves to illustrate how a CFSM recognizes viable pre-
fixes. However, it is unnecessary to make repeated passes over an input
string's sentential forms. For example, each of the repeated passes over the
input string's first two tokens (plus plus) causes the parser to enter State 1.
Because the CFSM is deterministic, processing a given sequence of vocabulary
symbols always has the same e
ect. Thus, the parsing algorithm given in
Figure 6.3 does not make repeated passes over the derived sentential forms.
Instead, the parse state is recorded after each shift so that the current parse
state is always associatedwith whatever symbol happens to be on top of stack.
As reductions eat into the stack, the symbol exposed at the new top-of-stack
bears the current state, which is the state the CFSMwould reach if it rescanned
the entire prefix of the current sentential formup to, and including, the current
top-of-stack symbol.
If a grammar is LR(0), then the construction discussed in this section has
the following properties (refer to Figure 6.11 as a reference):
ff
•
Given a syntactically correct input string, the CFSM will block only in
double-boxed states, which call for a reduction. The CFSM clearly shows
that no progress can occur unless a reduction takes place.
