Lecture No. 21
Dated: 09-04-2025
Shift Reduce: the Stack
The shift action pushes a terminal1 on the stack.
Reduce
- Pops one or more symbols from the
stack(right hand side ofproduction1) - Pushes a
non terminal1 on thestack(left hand side ofproduction1)
Discovering Handles
The upper edge of a partially constructed parse tree2 is called its upper frontier.
The parser3 must find some substring \(\beta\) of the upper frontier where
- \(\beta\) is the right hand side of some production \(A \to \beta\) and
- \(A \to \beta\) is one step in right most derivation of input stream
Each potential match is represented as a pair \(<A \to \beta, k>\) where \(k\) is the position on the tree2's current frontier of the right end of \(\beta\).
This pair is called the handle of the bottom up parser.3
Handle Pruning
The use of stack simplifies the parsing algorithm in 2 ways.
- It trivializes the problem of managing space for the
frontierby pushing the input characters at top of thestack. - It makes sure that all
handlesoccur with their right ends at the top of thestack, eliminating the need to keep track of position \(k\).
Shift-reduce Parsing Algorithm
push $ onto stack
sym ← nextToken()
repeat until
stack.push("$")
sym = nextToken()
while (not (sym == "$" and stack[1] == "G")): # Goal symbol right above $ symbol
if (stack.top() == "A -> B"):
stack.pop() # pops all B
stack.push("A")
else if (sym != "$"):
stack.push(sym)
sym = nextToken()
else:
# report error and halt