User Rating: / 0
**Related Content:** CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

## Shift-Reduce: The Stack

A stack can be used to hold the content of the left string. The Top of the stack is marked
by the ► symbol. The shift action pushes a terminal on the stack. Reduce pops zero or
more symbols from the stack (production rhs) and pushes a non-terminal on the stack
(production lhs)

## Discovering Handles

A bottom-up parser builds the parse tree starting with its leaves and working toward its
root. The upper edge of this partially constructed parse tree is called its upper frontier. At
each step, the parser looks for a section of the upper frontier that matches right-hand side
of some production. When it finds a match, the parser builds a new tree node with the
production’s left-hand non-terminal thus extending the frontier upwards towards the root.

The critical step is developing an efficient mechanism that finds matches along the tree’s
current frontier

Formally, the parser must find some substring β, of the upper frontier where

- β is the right-hand side of some production A → β, and
- A → β is one step in right-most derivation of input stream

We can represent each potential match as a pair 〈A→β,k〉, where k is the position on the
tree’s current frontier of the right-end of β. The pair 〈A→β,k〉, is called the handle of the
bottom-up parse.

## Handle Pruning

A bottom-up parser operates by repeatedly locating handles on the frontier of the partial
parse tree and performing reductions that they specify. The bottom-up parser uses a stack
to hold the frontier. The stack simplifies the parsing algorithm in two ways.

First, the stack trivializes the problem of managing space for the frontier. To extend the
frontier, the parser simply pushes the current input token onto the top of the stack.
Second, the stack ensures that all handles occur with their right end at the top of the
stack. This eliminates the need to represent handle’s position.

## Shift-Reduce Parsing Algorithm

push $ onto stack

sym ← nextToken()

repeat until (sym == $ and the stack contains exactly Goal on top of $)

if a handle for A → β on top of stack

pop |β| symbols off the stack

push A onto the stack

else if (sym ≠ $ )

push sym onto stack

sym ← nextToken()

else /* no handle, no input */

report error and halt