3.3.2 Shift-Reduce Parsing Using the ACTION/GOTO Tables

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:

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