    Next: 3.3.3 Table Construction Up: 3.3 Bottom-up Parsing Previous: 3.3.1 Bottom-up Parsing   Contents

### 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);
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);
}
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
```    Next: 3.3.3 Table Construction Up: 3.3 Bottom-up Parsing Previous: 3.3.1 Bottom-up Parsing   Contents
2015-01-20