Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction
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 |
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.