Java Reference
In-Depth Information
b. As an
id
is the incoming token, table[E,
id
] = 1 tells us to apply rule 1, E ::= TE
0
, and
replace the E on the stack with the right-hand side, T and E
0
, with T on top. Basically,
we plan to accomplish the goal of parsing an E by accomplishing the two sub- goals of
parsing a T and then an E
0
.
c. Seeing an
id
for the incoming token, we apply rule 4, T ::= FT
0
, and replace the T on
the stack with the right-hand side F and T
0
, with F on top.
d. We apply rule 8, F ::=
id
, replacing the top goal of F with an
id
.
e. The goal of parsing the
id
on top of the stack is trivially satisfied: we pop the
id
from
the stack and scan the
id
in the input; the next incoming symbol is now a
+
.
f. Now we have the goal of parsing a T
0
when looking at the input,
+
. We apply rule 6, T
0
::= , replacing the T
0
on the stack with the empty string (that is, nothing at all). Just
the goal E
0
remains on the stack.
g. Now the goal E
0
, when looking at the input token
+
, is replaced using rule 2 by
+
, T and
E
0
, with the
+
on top.
h. The
+
is trivially parsed; it is popped from the stack and scanned from the input. The
next incoming token is
id
.
i. Applying rule 4, T ::= FT
0
, we replace the T on the stack by F and T
0
, with F on top.
j. Applying rule 8, we replace the F on the stack with
id
.
k. The goal of parsing the
id
on top of the stack is trivially satisfied: we pop the
id
from
the stack and scan the
id
in the input; the goal on the stack is now a T
0
and the next
incoming symbol is now a
*
.
l. We apply rule 5 to replace the T
0
on the stack with a
*
, F, and another T
0
. The
*
is on
top.
m. The
*
on top is easily parsed: it is popped from the stack and scanned from the input.
n. The goal F, atop the stack, when looking at an incoming
id
, is replaced by an id using
rule 8.
o. The
id
is popped from the stack and scanned from the input, leaving a T
0
on the stack
and the terminator
#
as the incoming token.
p. We apply rule 6, replacing T
0
by the empty string.
q. We apply rule 3, replacing E
0
by the empty string.
r. There is a
#
on top of the stack and a
#
as input. We are done!
An alternative to Figure 3.6 for illustrating the states that the parser goes through is as
follows:
Search WWH ::
Custom Search