UNIT-III
Bottom-Up Parsing
Compiler Design- Unit-3
, Contents
• Bottom up Parsing
• Reductions
• Handle Pruning
• Shift Reduce Parsing
• Problems related to Shift Reduce Parsing
• Conflicts during Shift Reduce Parsing
• Operator Precedence Parser
• Computation of LEADING
• Computation of TRAILING
• Problems related to LEADING AND TRAILING
• LR Parsers – Why LR Parsers
• Items and LR(0) Automation
• Closure of Item sets
• LR Parsing Algorithm
• SLR Grammars
• SLR Parsing Tables
• Problems related to SLR
• Construction of Canonical LR(1) and LALR
• Construction of LALR
• Problems related to Canonical LR(1) and LALR Parsing Table
Compiler Design- Unit-3
, Bottom-Up Parsing
Introduction
• Bottom up parsing works in the opposite direction from top down.
• A top down parser begins with the start symbol at the top of the parse tree and works
downward, driving productions in forward order until it gets to the terminal leaves.
• A bottom up parse starts with the string of terminals itself and builds from the leaves
upward, working backwards to the start symbol by applying the productions in reverse.
• Along the way, a bottom up parser searches for substrings of the working string that
match the right side of some production. When it finds such a substring, it reduces it,
i.e., substitutes the left side non-terminal for the matching right side.
• The goal is to reduce all the way up to the start symbol and report a successful parse.
, Contd…
• A bottom-up parse corresponds to the construction of a parse tree for an input string
beginning at the leaves (the bottom) and working up towards the root (the top).
• It is the process of "reducing" a Input string w to the start symbol of the grammar.
• At each reduction step, a specific substring matching the body of a production is
replaced by the non terminal at the head of that production
• A reduction is the reverse of a step in a derivation, therefore bottom up parser is
rightmost derivation in reverse.
• The key decisions during bottom-up parsing are about when to reduce and about what
production to apply, as the parser proceeds.
Bottom-Up Parsing
Compiler Design- Unit-3
, Contents
• Bottom up Parsing
• Reductions
• Handle Pruning
• Shift Reduce Parsing
• Problems related to Shift Reduce Parsing
• Conflicts during Shift Reduce Parsing
• Operator Precedence Parser
• Computation of LEADING
• Computation of TRAILING
• Problems related to LEADING AND TRAILING
• LR Parsers – Why LR Parsers
• Items and LR(0) Automation
• Closure of Item sets
• LR Parsing Algorithm
• SLR Grammars
• SLR Parsing Tables
• Problems related to SLR
• Construction of Canonical LR(1) and LALR
• Construction of LALR
• Problems related to Canonical LR(1) and LALR Parsing Table
Compiler Design- Unit-3
, Bottom-Up Parsing
Introduction
• Bottom up parsing works in the opposite direction from top down.
• A top down parser begins with the start symbol at the top of the parse tree and works
downward, driving productions in forward order until it gets to the terminal leaves.
• A bottom up parse starts with the string of terminals itself and builds from the leaves
upward, working backwards to the start symbol by applying the productions in reverse.
• Along the way, a bottom up parser searches for substrings of the working string that
match the right side of some production. When it finds such a substring, it reduces it,
i.e., substitutes the left side non-terminal for the matching right side.
• The goal is to reduce all the way up to the start symbol and report a successful parse.
, Contd…
• A bottom-up parse corresponds to the construction of a parse tree for an input string
beginning at the leaves (the bottom) and working up towards the root (the top).
• It is the process of "reducing" a Input string w to the start symbol of the grammar.
• At each reduction step, a specific substring matching the body of a production is
replaced by the non terminal at the head of that production
• A reduction is the reverse of a step in a derivation, therefore bottom up parser is
rightmost derivation in reverse.
• The key decisions during bottom-up parsing are about when to reduce and about what
production to apply, as the parser proceeds.
