Java Reference
In-Depth Information
1 Start
→
S$
2 S
→
AC
3 C
→
c
4
| λ
5 A
→
aBCd
6
|
BQ
7 B
→
bB
8
| λ
9 Q
→
q
10
| λ
Rule Derivation
1
Start
⇒
rm
S$
2
⇒
rm
AC$
3
⇒
rm
Ac$
5
⇒
rm
aBCdc$
4
⇒
rm
aBdc$
7
⇒
rm
abBdc$
7
⇒
rm
abbBdc$
8
⇒
rm
abbdc$
Figure 6.4: Grammar and rightmost derivation of a bbdc$.
The parser accepts when the Start symbol is shifted in the parser's starting
state.
Using the table in Figure 6.5, Figures 6.6 and 6.7 show the steps of a
bottom-up parse. For pedagogical purposes, each stack cell is shown as two
elements:
n
The bottom element
n
is the parser state entered when the cell is pushed. The
top symbol
a
is the symbol causing the cell to be pushed. The parsing engine
described in Figure 6.3 keeps track only of the state.
The reader should verify that the reductions taken in Figures 6.6 and 6.7
trace a rightmost derivation in reverse. Moreover, shift actions are essentially
implied by the inability to performa useful reduction. The shifted tokens must
make progress toward developing a handle. Tokens are therefore shifted until
a handle appears at the top of the parse stack, at which time the next reduction
in the reverse derivation can be applied.
