Consider the following grammar:

0) S ::= R $

1) R ::= R b

2) R ::= a

which parses the R.E. ab^*$.

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:

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