(Continued from last class)

Bottom-up parsing

As you might guess, bottom-up parsing works the opposite to top-down parsing. Rather than starting at the root of the parse tree (the start symbol), we start at the leaves (tokens) and build our way up.

Specifically, the bottom-up parser will maintain a list of partial parse trees. (Well, technically it’s just as a stack, but it’s easier to think of as a list since we visualize it left to right.) Initially this list of partial trees is empty.

At each step of the parse, one of two things happens:

Shift: Add another token from the input stream as a new single-node tree at the end of the list.
Reduce: If the root nodes at the end of the list match up with the right-hand side of some grammar rule, then we combine them into a single tree according to that rule.

Notice that a reduce is essentially going “backwards” in the grammar, starting with the right-hand side and moving left.

Let’s look at the same example from before. As a reminder, here is the grammar:

prog -> stmt prog
     -> ε

stmt -> PRINT LP expr RP
     -> SAVE LP expr RP

expr -> INT
     -> X
     -> ADDOP expr
     -> expr MULOP expr
     -> expr ADDOP expr

and here is the token stream we are trying to parse:

SAVE  LP  INT  RP  PRINT  LP  INT  MULOP  X  RP
save  (   10   )   print  (    2     *    x  )

For a bottom-up parse, we start with an empty list. There is actually one reduction we could take here, prog -> ε, but we can see that’s not the right choice yet. Instead, let’s shift on the first token:

SAVE
save

Now this doesn’t match the right-hand side of any grammar rule, so we shift again:

SAVE  LP
save  (

Now the list has two partial parse trees, each with just a single node. Still no reductions are possible, so we shift a third time:

SAVE  LP  INT
save  (   10

Now a reduction is possible! We can’t reduce the whole list yet, but remember we are allowed to reduce whenever the end of the list matches the right-hand side of a grammar rule. In this case, the relevant rule is expr -> INT. So we run this rule backwards and build up the tree with our first reduce:

          expr
           |
SAVE  LP  INT
save  (   10

Now the list has three trees, with roots SAVE, LP, and expr. No reductions are possible, so we shift again.

          expr
           |
SAVE  LP  INT  RP
save  (   10   )

At this point, we can do a big reduction, according to the rule stmt -> SAVE LP expr RP. This will reduce the current list to just a single tree with root stmt.

    ___stmt___
   /   /   |  \
   |   |  expr |
   |   |   |   |
SAVE  LP  INT  RP
save  (   10   )

No more reductions can happen here, so we continue the process with three shifts and a reduce, similar to what just happened:

    ___stmt___
   /   /   |  \
   |   |  expr |              expr
   |   |   |   |               |
SAVE  LP  INT  RP  PRINT  LP  INT
save  (   10   )   print  (    2

At this point the list has 4 partial trees. Recall from top-down parsing that look-ahead was needed to figure out what to do here: we had to predict whether it was going to just be a single integer or some kind of arithmetic operation. But bottom-up parsing doesn’t have to do that! At this stage, we would be ready if the print statement ended with an RP, but we can also keep going for an arithmetic operation; no look-ahead was needed.

The next steps for a bottom-up parse are two more shifts and a reduce according to expr -> X:

    ___stmt___
   /   /   |  \
   |   |  expr |              expr        expr
   |   |   |   |               |           |
SAVE  LP  INT  RP  PRINT  LP  INT  MULOP   X
save  (   10   )   print  (    2     *     x

And now, after the fact, we see that in fact it was an arithmetic expression, and we reduce the last three partial trees in the list:

    ___stmt___                     _expr_
   /   /   |  \                   /  |   \
   |   |  expr |              expr   |    expr
   |   |   |   |               |     |     |
SAVE  LP  INT  RP  PRINT  LP  INT  MULOP   X
save  (   10   )   print  (    2     *     x

Now we shift the last token and reduce the print statement:

                        ______ __stmt_________
                       /   /         |        \
    ___stmt___         |   |       _expr_      |
   /   /   |  \        |   |      /  |   \     |
   |   |  expr |       |   |  expr   |    expr |
   |   |   |   |       |   |   |     |     |   |
SAVE  LP  INT  RP  PRINT  LP  INT  MULOP   X   RP
save  (   10   )   print  (    2     *     x   )

What now? We still have two partial trees, so the parse isn’t finished. But we’ve reached the end of the token sequence so we can’t shift again.

But technically one reduction is possible, the epsilon reduction for prog. In a bottom-up parse, an epsilon reduction is always allowed, and just adds an extra node at the end with the relevant non-terminal:

                        ______ __stmt_________
                       /   /         |        \
    ___stmt___         |   |       _expr_      |
   /   /   |  \        |   |      /  |   \     |
   |   |  expr |       |   |  expr   |    expr |   prog
   |   |   |   |       |   |   |     |     |   |    |
SAVE  LP  INT  RP  PRINT  LP  INT  MULOP   X   RP   ε
save  (   10   )   print  (    2     *     x   )

This kicks off a series of two final reductions to finish off the parse:

            ___________prog______________
           /                             \
          |                           ____prog____
          |                          /            \
          |             ______ __stmt_________     |
          |            /   /         |        \    |
    ___stmt___         |   |       _expr_      |   |
   /   /   |  \        |   |      /  |   \     |   |
   |   |  expr |       |   |  expr   |    expr |   prog
   |   |   |   |       |   |   |     |     |   |    |
SAVE  LP  INT  RP  PRINT  LP  INT  MULOP   X   RP   ε
save  (   10   )   print  (    2     *     x   )

Even thought it’s drawn kind of funny, make sure you notice that this is the exact same tree as we got from the top-down parse.

How a bottom-up parser makes decisions

As we have seen, the crucial decision at each step of a bottom-up parse is shift or reduce (and, if multiple reductions are possible, which rule should we reduce by).

But generally speaking, this decision is much easier to make for bottom-up parsers than for top-down predictive parsers. In the above parse, we were able to follow the simple strategy of “do every reduction as soon as you can”.

This doesn’t always work. For example, if you consider the expression 2 + 3 * 4, in order to follow order of operations and perform the multiplication first, the parser needs to know not to reduce 2 + 3 to an expression (as it could do), but instead to shift on the * and 4 , and then perform the two expr reductions.

In many cases, a bottom-up parser can resolve these shift/reduce questions with zero or one token of look-ahead. Because the decision-making is a bit simpler than with top-down parsers, it is a bit easier and more efficient to generate a bottom-up parser automatically from a grammar specification. Many early compilers, especially ones designed for speed, took this approach.