Bottom-Up Parsing - Intro

Bottom up Parsing
Bottom Up Parsing
• Goal of parser : build a derivation

• top-down parser : build a derivation by working from the
start symbol towards the input.
• builds parse tree from root to leaves
• builds leftmost derivation
• bottom-up parser : build a derivation by working from the
input back toward the start symbol
• builds parse tree from leaves to root
• builds reverse rightmost derivation
a string  the starting symbol
reduced to
Basic Idea : Bottom- up parsing
• Goal: construct parse tree for input string

• Read input from left to right
• Build tree in a bottom-up fashion
• Use stack to hold pending sequences of terminals and nonterminals
Bottom up parsing
• Construct a parse tree for an input string beginning at leaves and going towards
root
OR
• Reduce a string w of input to start symbol of grammar
At each reduction step a particular substring matching the right side of a production is
replaced by the symbol on the left of that production, and if the substring is chosen
correctly at each step, a rightmost derivation is traced out in reverse.
For example,Consider the grammar
S  aABe
A  Abc | b
Bd
The input string, w=abbcde can be reduced to start symbol S by following steps:
a b b c d e [Substring b matches with right side of the production A->b]
aAbcde [Substring Abc matches the right side of the production AAbc]
aAde [Substring d matches the right side of the production Bd]
aABe [Substring aABe matches the right side of the production S->aABe]
S
Right most derivation
These reductions trace out the following right- SaABe
most derivation in reverse: aAde
aAbcde
abbcde
Handle
• A Handle of a string
• A substring that matches the RHS of some production and whose
reduction represents one step of a rightmost derivation in
reverse
• So we scan tokens from left to right, find the handle, and replace
it by corresponding LHS
• Formally:
• handle of a right sentential form  is a production A  , and
the location of  in  , that satisfies the above property.
• i.e. A   is a handle of  at the location immediately after
the end of , if:
S => A => 
Handle-pruning
The process of discovering a handle & reducing it to the
appropriate left-hand side is called handle pruning.
Handle pruning forms the basis for a bottom-up parsing

method.
Problems:
• locate a handle
• decide which production to use (if there are more than two
candidate productions).
• In many cases, the leftmost substring  which matches the
right side of some production A may not be a handle
because a reduction by this production may yield a string which
cannot be reduced to start symbol
Eg in the previous example

abbcde
aAbcde
aAAcde
Stack Implementation of Bottom-up parser
A bottom-up parser uses an explicit stack in its implementation
The main actions are shift and reduce
 A bottom-up parser is also known as shift-reduce parser
Four operations are defined:
• shift, reduce, accept, and error
 Shift: parser shifts the next token on the parser stack
 Reduce: parser reduces the RHS of a production to its LHS .The handle always appears on top of the
stack
 Accept: parser announces a successful completion of parsing
 Error: parser discovers that a syntax error has occurred
The parser operates by:
 Shifting tokens onto the stack
 When a handle β is on top of stack, parser reduces β to LHS of production
 Parsing continues until an error is detected or input is reduced to start symbol
Example
Consider the parsing of the input string id + id * id
$ is used to mark the

bottom of the stack as well
as the end of input
Issues in Bottom-up parsing
• There are several issues in bottom up parsing:
• How do we know which action to take
• whether to shift or reduce
• Which production to use for reduction?
Conflicts
• The general shift-reduce technique is:
• if there is no handle on the stack then shift
• If there is a handle then reduce
• There are two types of conflicts in shift reduce parsing

• shift-reduce conflict : occurs if both shift and reduce are valid
• reduce-reduce conflict : occurs if handle matches multiple

productions.
• Conflicts come either because of ambiguous grammars or

parsing method is not powerful enough
Example : shift/reduce Conflict
• Consider the Grammar
S if e then S
|if e then S else S
|other
If we have a shift-reduce parser in configuration
STACK Input
….if e then S else ….$ [shift/reduce Conflict]
we cannot tell whether if e then S is a handle
In general, shift/reduce conflicts are resolved by favouring shift opertion

Bottom-Up Parsing - Intro

Uploaded by

Copyright:

Available Formats

Bottom-Up Parsing - Intro

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Bottom-Up Parsing - Intro

Uploaded by

Copyright:

Available Formats

Bottom up Parsing

• Goal of parser : build a derivation

• Goal: construct parse tree for input string

Handle pruning forms the basis for a bottom-up parsing

Eg in the previous example

$ is used to mark the

• There are two types of conflicts in shift reduce parsing

• reduce-reduce conflict : occurs if handle matches multiple

• Conflicts come either because of ambiguous grammars or

we cannot tell whether if e then S is a handle

In general, shift/reduce conflicts are resolved by favouring shift opertion

You might also like