Lecture 7
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 32
Bottom-Up Parsing
The term "Bottom-Up Parsing" refer to the order in which
nodes in the parse tree are constructed, construction starts at the
leaves and proceeds towards the root. Bottom-Up Parsing can
handle a large class of grammars.
1. Shift-Reduce Parsing: Is a general style of Bottom-up
syntax analysis , it attempts to construct a parse tree for an
input string beginning at leaves and working up towards
the root,(reducing a string w to the start symbol of
grammar).At each reduction step a particular substring
matching the right side of production is replaced by the
symbol on the left of that production.
Example : consider the grammar
And the input is abbcde
The implementation Bottom-Up Parsing is
Handle : Is a substring that matches the right side of a
production.
Stack Implementation of Shift-Reduce Parsing:
A convenient way to implement a shift-reduce parser is to use a
Stack to hold a grammar symbols and an input buffer to hold the
sting w to be parsed. We use $ to mark the bottom of stack and
also the right end of the input string. There are actually four
possible actions:
S aABe
A Abc b
B d
a b b c d e
a A b c d e
a A d e
a A B e
S
Accept
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 33
1. Shift : The next input symbol is Shifted onto the top
of stack.
2. Reduce : Replace the handle with nonterminal.
3. Accept : The parser announces successful
completion of parsing .
4. Error : The parser discovers that syntax error has
occurred and calls an error recovery routine.
Example: Consider the following grammar
And the input string is id + id * id, then the
implementation is :
| Stack | Input Buffer | Action |
| $ $id $E $E+ $E+id $E+E $E+E* $E+E*id $E+E*E $E+E $E |
id+id*id$ +id*id$ +id*id$ id*id$ *id$ *id$ id$ $ $ $ $ |
Shift Reduce: E→id Shift Shift Reduce: E→id Shift(*) Shift Reduce: E→id Reduce: E→E*E Reduce: E→E+E Accept |
Conflicts During Shift-Reduce Parsing:
There are context free grammars for which shift-reduce
parsing cannot be used. Ambiguous grammars lead to parsing
conflicts. Can fix by rewriting grammar or by making
appropriate choice of action during parsing. There are two type
of conflicts :
E E+E E*E (E) id
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 34
Example is Better than Precept
1. Shift/Reduce conflicts: should we shift or reduce? (See
previous example (*))
2. Reduce/Reduce conflicts: which production should we
reduce with? for example:
stmt → id(param)
param → id
expr → id(expr) | id
| Stack $...id(id |
Input Buffer ,id)...$ |
Action Reduce by ?? |
Should we reduce to param or to expr ?
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
