# CS606 - Compiler Construction - Lecture Handout 22

User Rating:  / 0
PoorBest

Example: here is the bottom-up parser’s action when it parses the expression grammar sentence

x – 2 × y

(tokenized as id – num * id)

 word Stack Handle Action 1 id ► - none - shift 2 – id ► 〈Factor → id,1〉 reduce 3 – Factor ► 〈Term → Factor,1〉 reduce 4 – Term ► 〈Expr → Term,1〉 reduce 5 – Expr ► - none - shift 6 num Expr – ► - none - shift 7 × Expr – num ► 〈Factor → num,3〉 reduce 8 × Expr – Factor ► 〈Term → Factor,3〉 shift 9 × Expr – Term ► - none - shift 10 id Expr – Term × ► - none - shift 11 \$ Expr – Term × id► 〈Factor → id,5〉 reduce 12 \$ Expr–Term × Factor► 〈Term→Term×Factor,5〉 reduce 13 \$ Expr – Term ► 〈Expr → Expr – Term,3〉 reduce 14 \$ Expr ► 〈Goal → Expr,1〉 reduce 15 \$ Goal - none - accept

## Handles

The handle-finding mechanism is the key to efficient bottom-up parsing. As it process an input string, the parser must find and track all potential handles. For example, every legal input eventually reduces the entire frontier to grammar’s goal symbol. Thus, 〈Goal → Expr,1〉 is a potential handle at the start of every parse. As the parser builds a derivation, it discovers other handles. At each step, the set of potential handles represent different suffixes that lead to a reduction. Each potential handle represent a string of grammar symbols that, if seen, would complete the right-hand side of some production.

For the bottom-up parse of the expression grammar string, we can represent the potential handles that the shift-reduce parser should track. Using the placeholder • to represent top of the stack, there are nine handles:

 Handles 1 〈Factor → id •〉 2 〈Term → Factor•〉 3 〈Expr → Term •〉 4 〈Factor → num•〉 5 〈Term → Factor•〉 6 〈Factor → id •〉 7 〈Term → Term × Factor •〉 8 〈Expr → Expr – Term •〉 9 〈Goal → Expr •〉

This notation shows that the second and fifth handles are identical, as are first and sixth.
It also create a way to represent the potential of discovering a handle in future. Consider the parser’s state in step 6: The parser has recognized Expr –. Using the stack-relative notation, we can represent the parser’s state as Expr → Expr – • Term. The parser has already recognized an Expr and a –. If the parser reaches a state where it shifts a Term
on top of Expr and –, it will complete the handle Expr → Expr – Term •. How many potential handles must the parser recognize? The right-hand side of each production can have a placeholder at its start, at its end and between any two consecutive symbols.

Expr → • Expr –Term
Expr → Expr • – Term
Expr → Expr – •Term
Expr → Expr – Term •

If the right-hand side of a production has k symbols, it has k +1 placeholder positions.