The basic idea of a bottom-up parser is that we use grammar
productions in the opposite way (from right to left). Like for predictive
parsing with tables, here too we use a stack to push symbols. If the
first few symbols at the top of the stack match the rhs of some rule,
then we pop out these symbols from the stack and we push the lhs (left-hand-side) of
the rule. This is called a *reduction*. For example, if the stack
is `x * E + E`

(where `x`

is the bottom of stack) and there
is a rule `E ::= E + E`

, then we pop out `E + E`

from the
stack and we push `E`

; ie, the stack becomes `x * E`

. The
sequence `E + E`

in the stack is called a *handle*. But
suppose that there is another rule `S ::= E`

, then `E`

is also a handle in the stack. Which one to choose? Also what happens
if there is no handle? The latter question is easy to answer: we push
one more terminal in the stack from the input stream and check again
for a handle. This is called *shifting*. So another name for
bottom-up parsers is shift-reduce parsers. There two actions only:

- shift the current input token in the stack and read the next token, and
- reduce by some production rule.

A DFA though can only be used if we always have one choice for each
symbol. But this is not the case here, as it was apparent from the
previous example: there is an ambiguity in recognizing handles in the
stack. In the previous example, the handle can either be `E + E`

or `E`

. This ambiguity will hopefully be resolved later when we
read more tokens. This implies that we have multiple choices and each
choice denotes a valid potential for reduction. So instead of a DFA we
must use a NFA, which in turn can be mapped into a DFA as we learned
in Section 2.3. These two steps (extracting the NFA and map
it to DFA) are done in one step using *item sets* (described below).

- 3.3.1 LR(0) Grammar
- 3.3.2 SLR(1), LR(1), and LALR(1) Grammars
- 3.3.3 Practical Considerations for LALR(1) Grammars

2002-08-26