Java Reference
In-Depth Information
The next incoming symbol is an
id
, so we consult the Action table Action[0,
id
] to
determine what to do in state 0 with an incoming token
id
. The entry is s5, so we shift
the
id
onto the stack and go into state 5 (pushing the new state onto the stack above the
id
).
Stack
Input
Action
0
id+id*id#
shift 5
0
id
5
+id*id#
Now, the 5 on top of the stack indicates we are in state 5 and the incoming token is
+
,
so we consult Action[5,
+
]; the r6 indicates a reduction using rule 6: F ::=
id
. To make the
reduction, we pop 2k items o the stack, where k is the number of symbols in the rule's
right-hand side; in our example, k = 1 so we pop both the 5 and the
id
.
Stack
Input
Action
0
id+id*id#
shift 5
0
id
5
+id*id#
reduce 6, output a 6
0
+id*id#
Because we are reducing the right-hand side to an F in this example, we push the F
onto the stack.
Stack
Input
Action
0
id+id*id#
shift 5
0
id
5
+id*id#
reduce 6, output a 6
0F
+id*id#
And finally, we consult Goto[0, F] to determine which state the parser, initially in state
0, should go into after parsing an F. Because Goto[0, F] = 3, this is state 3. We push the
3 onto the stack to indicate the parser's new state.
Stack
Input
Action
0
id+id*id#
shift 5
0
id
5
+id*id#
reduce 6, output a 6
0F3
+id*id#
From state 3 and looking at the incoming token
+
, Action[3,
+
] tells us to reduce using
rule 4: T ::= F.
Stack
Input
Action
0
id
+id*id#
shift 5
0
id
5
+id*id#
reduce 6, output a 6
0F3
+id*id#
reduce 4, output a 4
0T2
+id*id#
Search WWH ::
Custom Search