next up previous contents
Next: 3.3.2 Shift-Reduce Parsing Using Up: 3.3 Bottom-up Parsing Previous: 3.3 Bottom-up Parsing   Contents

3.3.1 Bottom-up Parsing

Recall the original CFG G1:

0)  S :: = E $
1)  E ::= E + T
2)      | E - T
3)      | T
4)  T ::= T * F
5)      | T / F
6)      | F
7)  F ::= num
8)      | id
Here is a trace of the bottom-up parsing of the input x-2*y$:
      Stack          rest-of-the-input          Action
---------------------------------------------------------------
 1)                    id - num * id $      shift
 2)   id               - num * id $         reduce by rule 8
 3)   F                - num * id $         reduce by rule 6
 4)   T                - num * id $         reduce by rule 3
 5)   E                - num * id $         shift
 6)   E -              num * id $           shift
 7)   E - num          * id $               reduce by rule 7
 8)   E - F            * id $               reduce by rule 6
 9)   E - T            * id $               shift
10)   E - T *          id $                 shift
11)   E - T * id       $                    reduce by rule 8
12)   E - T * F        $                    reduce by rule 4
13)   E - T            $                    reduce by rule 2
14)   E $                                   shift
15)   S                                     accept (reduce by rule 0)
We start with an empty stack and we finish when the stack contains the non-terminal S only. Every time we shift, we push the current token into the stack and read the next token from the input sequence. When we reduce by a rule, the top symbols of the stack (the handle) must match the rhs of the rule exactly. Then we replace these top symbols with the lhs of the rule (a non-terminal). For example, in the line 12 above, we reduce by rule 4 (T ::= T * F). Thus we pop the symbols F, *, and T (in that order) and we push T. At each instance, the stack (from bottom to top) concatenated with the rest of the input (the unread input) forms a valid bottom-up derivation from the input sequence. That is, the derivation sequence here is:
 1)       id - num * id $
 3)  =>   F - num * id $
 4)  =>   T - num * id $
 5)  =>   E - num * id $
 8)  =>   E - F * id $
 9)  =>   E - T * id $
12)  =>   E - T * F $
13)  =>   E - T $
14)  =>   E $
15)  =>   S
The purpose of the above example is to understand how bottom-up parsing works. It involves lots of guessing. We will see that we don't actually push symbols in the stack. Rather, we push states that represent possibly more than one potentials for rule reductions.

As we learned in earlier sections, a DFA can be represented by transition tables. In this case we use two tables: ACTION and GOTO. ACTION is used for recognizing which action to perform and, if it is shifting, which state to go next. GOTO indicates which state to go after a reduction by a rule for a nonterminal symbol. We will first learn how to use the tables for parsing and then how to construct these tables.


next up previous contents
Next: 3.3.2 Shift-Reduce Parsing Using Up: 3.3 Bottom-up Parsing Previous: 3.3 Bottom-up Parsing   Contents
2015-01-20