Consider the following grammar:

0) S ::= R $ 1) R ::= R b 2) R ::= awhich parses the R.E.

The DFA that recognizes the handles for this grammar is: (it will be explained later how it is constructed)

where 'r2' for example means reduce by rule 2 (ie, by `R :: = a`

)
and 'a' means accept. The transition from 0 to 3 is done when the
current state is 0 and the current input token is 'a'. If we are in
state 0 and have completed a reduction by some rule for R (either rule
1 or 2), then we jump to state 1.

The ACTION and GOTO tables that correspond to this DFA are:

state | action | goto | |||

a | b | `$` |
S | R | |

0 | s3 | 1 | |||

1 | s4 | s2 | |||

2 | a | a | a | ||

3 | r2 | r2 | r2 | ||

4 | r3 | r3 | r3 |

where for example s3 means shift a token into the stack and go to state 3. That is, transitions over terminals become shifts in the ACTION table while transitions over non-terminals are used in the GOTO table.

Here is the shift-reduce parser:

push(0); read_next_token(); for(;;) { s = top(); /* current state is taken from top of stack */ if (ACTION[s,current_token] == 'si') /* shift and go to state i */ { push(i); read_next_token(); } else if (ACTION[s,current_token] == 'ri') /* reduce by rule i: X ::= A1...An */ { perform pop() n times; s = top(); /* restore state before reduction from top of stack */ push(GOTO[s,X]); /* state after reduction */ } else if (ACTION[s,current_token] == 'a') success!! else error(); }Note that the stack contains state numbers only, not symbols.

For example, for the input `abb$`

, we have:

Stack rest-of-input Action ---------------------------------------------------------------------------- 0 abb$ s3 0 3 bb$ r2 (pop(), push GOTO[0,R] since R ::= a) 0 1 bb$ s4 0 1 4 b$ r1 (pop(), pop(), push GOTO[0,R] since R ::= R b) 0 1 b$ s4 0 1 4 $ r1 (pop(), pop(), push GOTO[0,R] since R ::= R b) 0 1 $ s2 0 1 2 accept