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