[go: up one dir, main page]
Scribd
Upload
12 views11 pages

Compiler Design Syntax Analysis Bottom Up

This document introduces bottom-up parsing, explaining how it constructs a parse tree from the leaves to the root using techniques like handle pruning and shift-reduce parsing. It outlines the basic operations of a shift-reduce parser, including shifting, reducing, accepting, and error handling, along with examples to illustrate these concepts. The document also provides a specific example of a grammar and asks for the handle of a right sentential form.

Uploaded by

mainakroni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views11 pages

Compiler Design Syntax Analysis Bottom Up

This document introduces bottom-up parsing, explaining how it constructs a parse tree from the leaves to the root using techniques like handle pruning and shift-reduce parsing. It outlines the basic operations of a shift-reduce parser, including shifting, reducing, accepting, and error handling, along with examples to illustrate these concepts. The document also provides a specific example of a grammar and asks for the handle of a right sentential form.

Uploaded by

mainakroni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Left and Right most derivation

Introduction to Bottom Up Parsing

• Constructs parse tree for an input string beginning at the leaves (the
bottom) and working towards the root (the top)
• Example: id*id

G: E -> E + T | T
T -> T * F | F
F -> (E) | id
id*id F * id T * id T*F T E

id F F id T*F T

id id F id T*F

id F id

id
Handle pruning
• A Handle is a substring that matches the body of a production and
whose reduction represents one step along the reverse of a rightmost
derivation
G: E -> E + T | T
T -> T * F | F
F -> (E) | id
Example: id*id

Right sentential form Handle Reducing production


id*id id F->id
F*id F T->F
T*id id F->id
T*F T*F T->T*F
T T E->T
Example.
For the grammar S-> 0S1|01,
a. Indicate the handle for the following right sentential form : 000111
b. Give bottom-up parses
Shift-reduce parser
• The general idea is to shift some symbols of input to the stack until a
reduction can be applied
• At each reduction step, a specific substring matching the body of a
production is replaced by the nonterminal at the head of the
production
• The key decisions during bottom-up parsing are about when to
reduce and about what production to apply
• A reduction is a reverse of a step in a derivation

• Shift-reduce parsing is a form of bottom-up parsing in which a stack


holds grammar symbols and an input buffer holds the rest of the
string to be parsed.
• The goal of a bottom-up parser is to construct a derivation in reverse:
• E=>T=>T*F=>T*id=>F*id=>id*id
Shift reduce parsing

• A stack is used to hold grammar symbols


• Handle always appear on top of the stack
• Initial configuration:
Stack Input
$ w$
• Acceptance configuration
Stack Input
$S $
Shift reduce parsing (cont.)
• Basic operations:
• Shift: Shift the next input symbol onto the top of the stack.
• Reduce: The right end of the string to be reduced must be at the top of the stack.
• Accept: Announce success
• Error: Discover a syntax error and call an error recovery routine

• Example:

Configurations of a shift-reduce parser on input


Example of another string
Thank You

You might also like