A bottom-up parser builds the parse tree from the bottom to the top. Bottom-up parsers make much less extravagant predictions and can handle grammars that top-down parsers cannot.
Let's do a bottom-up parse of n + n * n using the following grammar, from a previous page
| E | → | T |
| E | → | E + T |
| T | → | F |
| T | → | T * F |
| F | → | n |
| F | → | ( E ) |
To start off, the first token n, is added.
n
There is only one production F → n that can generate n.
F | n
Only two productions, T → F and T → T + F, have F on the right-hand side. But only one of those starts with F, so we need to use that one.
T | F | n
The same reasoning says to choose production E → T next.
E | T | F | n
Now the lookahead is +, and the only production that makes sense to build above the E is E → E + T.
But a bottom-up parser builds the parse tree strictly from bottom to top. Instead of building above E, it builds a leaf holding token +.
E | T | F | n +
The next token is n. The parser creates a new leaf holding n and reasons as above, up to a point.
E | T T | | F F | | n + n
The next two tokens are * and n. Keeping with the bottom-up philosophy, the parser builds a leaf holding *, and after that a leaf holding n. Then it builds what it must above n.
E | T T | | F F F | | | n + n * n
But, out of the blue, we see T * F at the right end of the 5 small trees, which is precisely the right-hand side of production T → T * F.
The parser does not need to predict that something of the form T * F is coming. It finds that empirically, after the right-hand side has already been built.
E T | /|\ T T * F | | | F F n | | n + n
Once again, the right-hand side of a production pops up. This time, the production is E → E + T.
E
/|\
/ + \
/ \
E T
| /|\
T T * F
| | |
F F n
| |
n n
You can see from the example that, although a bottom-up parser reads the sequence of tokens from left to right, it builds the parse tree from right to left.
A bottom-up parser can be thought of as creating a rightmost derivation.