Bottom-Up (Shift-Reduce) Parsing

In bottom-up parsing we start with the sentence and try to apply the production rules in reverse, in order to finish up with the start symbol of the grammar. This corresponds to starting at the leaves of the parse tree, and working back to the root.

• Each application of a production rule in reverse is known as a reduction.
• The r.h.s. of a rule to which a reduction is applied is known as a handle.
  

Thus the operation of a bottom-up parser will be as follows:

1. Start with the sentence to be parsed as the initial sentential form
2. Until the sentential form is the start symbol do:
   1. Scan through the input until we recognise something that corresponds to the r.h.s. of one of the production rules (this is called a handle)
   2. Apply a production rule in reverse; ie. replace the r.h.s. of the rule which appears in the sentential form with the l.h.s. of the rule (an action known as a reduction)

In step 2(a) above we are ``shifting'' the input symbols to one side as we move through them; hence a parser which operates by repeatedly applying steps 2(a) and 2(b) above is known as a shift-reduce parser.

A shift-reduce parser is most commonly implemented using a stack, where we proceed as follows:

• start with the sentence to be parsed on top of the stack
• a "shift" action correponds to pushing the current input symbol onto the stack
• a "reduce" action occurrs when we have a handle on top of the stack. To perform the reduction, we pop the handle off the stack and replace it with the terminal on the l.h.s. of the corresponding rule.
  

In a top-down parser, the main decision was which production rule to pick. In a bottom-up shift-reduce parser there are two decisions:

1. Should we shift another symbol, or reduce by some rule?
2. If reduce, then reduce by which rule?
   

Observe that the basic operation of a shift reduce parser is going through the input symbols from left-to-right looking for one of a particular set of strings (the r.h.ss. of the production rules).

Thus the basis of any shift-reduce parser will be a machine which can shift input symbols until it recognises a handle. We have already met such a machine - what we need is simply a (handle-recognising) DFA.

• A parser action such as "shift a" corresponds to making a transition from one state to another based on symbol `a' in the DFA
• An action such as reduce by $A\, \rightarrow\, \alpha$ means that we have recognised all the symbols in $\alpha$ and have now reached what is effectively a final state for that handle.
  

In order to construct the DFA from a grammar we need some way of representing the current status of the parse as a state in the DFA.