Scribd
Upload
5 views

Unit 2 Bottom-up Parsing

The document discusses bottom-up parsing, which constructs a parse tree from the leaves to the root, using examples to illustrate the process. It covers concepts such as handle pruning, shift-reduce parsing, and provides examples of grammar and input strings for practical understanding. The parsing operations include shifting symbols to a stack, reducing handles, and accepting or rejecting input based on the stack's contents.

Uploaded by

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

Unit 2 Bottom-up Parsing

The document discusses bottom-up parsing, which constructs a parse tree from the leaves to the root, using examples to illustrate the process. It covers concepts such as handle pruning, shift-reduce parsing, and provides examples of grammar and input strings for practical understanding. The parsing operations include shifting symbols to a stack, reducing handles, and accepting or rejecting input based on the stack's contents.

Uploaded by

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

Bottom-up Parsing

Dr. Sushil Kumar


Introduction
• Constructs parse tree for an input string beginning at the leaves (the
bottom) and working towards the root (the top) (Bottom to UP)

• Example: id*id

E -> E + T | T id*id F * id T * id T*F F E


T -> T * F | F
T*F F
F -> (E) | id id F F id

id id F id T*F

id F id

id
Example: Construction of Bottom-Up
parser
• Grammar:
S->TL;
T->int | float
L->L,id | id
• Input: int id, id;
Sentential form of parse tree
int id,id,id;
T id,id,id;
T L,id,id;
T L,id;
TL;
S

Note:
• Parsing is done through rightmost derivation in reverse order
• Reduction of input string to start symbol
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
• Example: id*id
E -> E + T | T
T -> T * F | F
F -> (E) | 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 E->T*F
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 symbols from input
buffer to STACK Stack Input Action
• Reduce: If handle appears on the $ id*id$ shift
top of the STACK, we do reduction $id *id$ reduce by F->id
of it by appropriate rule $F *id$ reduce by T->F
• Accept: Input string will accept $T *id$ shift
when STACK contains start symbol $T* id$ shift
and input buffer is empty $T*id $ reduce by F->id
$T*F $ reduce by T->T*F
• Error: if the parser is not able to reduce by E->T
perform shift or reduce. $T $
$E $ accept

• Example: id*id
Perform Shift-Reduce parsing
Example 1:
E -> E+E | E*E | id

Input: id1+id2*id3
Example 2: Perform Shift-Reduce
parsing
Grammar:
S -> (L) | a
S -> L,S | S

Input: (a, (a, a))


Example 3: Perform Shift-Reduce
parsing
Grammar:
S -> 0S0 | 1S1 |2

Input: 10201

You might also like