Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 22

User Rating:  / 0
PoorBest 

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

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.