Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 21

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

  1. β is the right-hand side of some production A → β, and
  2. 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