Module -3

Chapter 4
Syntax Analysis

Prof. Maya B S
Assistant Professor
Department of CS&E
BIT, Bangalore
Syllabus- Chapter 4

4.5 Bottom up parsing

Prof. Maya B S, Assistant Professor, CSE,BIT 2

Parsing

• Syntax analyzers follow production rules defined by means of context-

free grammar. The way the production rules are implemented
(derivation) divides parsing into two types : top-down parsing and
bottom-up parsing.

Prof. Maya B S, Assistant Professor, CSE,BIT 3

Prof. Maya B S, Assistant Professor, CSE,BIT 4
Prof. Maya B S, Assistant Professor, CSE,BIT 5
Bottom-up Parsing
• As the name suggests, bottom-up parsing starts with the input symbols and tries to
construct the parse tree up to the start symbol.
• Example:
• Input string : a + b * c
• Production rules:
• S→E
• E→E+T
• E→E*T
• E→T
• T → id

Prof. Maya B S, Assistant Professor, CSE,BIT 6

• Let us start bottom-up parsing
• a+b*c
• Read the input and check if any production matches with the input:
• a+b*c
• T+b*c
• E+b*c
• E+T*c
• E*c
• E*T
•E
•S

Prof. Maya B S, Assistant Professor, CSE,BIT 7

Prof. Maya B S, Assistant Professor, CSE,BIT 8
Prof. Maya B S, Assistant Professor, CSE,BIT 9
Prof. Maya B S, Assistant Professor, CSE,BIT 10
Prof. Maya B S, Assistant Professor, CSE,BIT 11
Construct bottom up parse tree for input id*id using grammar
EE+T|T ,TT*F|F ,F( E ) |id

Prof. Maya B S, Assistant Professor, CSE,BIT 12

Prof. Maya B S, Assistant Professor, CSE,BIT 13
Define Reduction? [2Marks]

Prof. Maya B S, Assistant Professor, CSE,BIT 14

• The key decision during bottom up parsing are “when to reduce and about what
production to apply “ as the parse proceeds.

• EX: The above strings shows sequences of reduction, then reduction can be
expressed in terms of sequence of strings like

• id*id, F*id, T*id, T*F, T,E.

• If the substring is chosen correctly at each step, the reduction steps could be an
exact reverse of RMD.

• ETT*FT*idF*idid*id

Prof. Maya B S, Assistant Professor, CSE,BIT 15

Handle Pruning [4M]
1.What is mean by handle pruning? How it helps in shift reduce parsing? List the
action of a shift reduce parser.
2.What is handle and handle pruning? Show the working of a shift reduce parser for
accepting id1*id2 considering the grammar
EE + T |T , TT*F |F, F ( E ) |id
Ans:
During BUP , a left to right scan of the input construct a right most derivation in
reverse.
Informally, “A Handle is a substring that matches the body of production and whose
reduction represents one step along the reverse of a RMD.”
“A RMD in reverse called canonical reduction sequence is obtained by the process
of handle pruning”

Prof. Maya B S, Assistant Professor, CSE,BIT 16

Prof. Maya B S, Assistant Professor, CSE,BIT 17
Prof. Maya B S, Assistant Professor, CSE,BIT 18
Prof. Maya B S, Assistant Professor, CSE,BIT 19
Prof. Maya B S, Assistant Professor, CSE,BIT 20
Prof. Maya B S, Assistant Professor, CSE,BIT 21
Prof. Maya B S, Assistant Professor, CSE,BIT 22
1. Construct Shift-reduce parsing table for given input id+id*id
using above grammar.

Prof. Maya B S, Assistant Professor, CSE,BIT 23

2. Shift-reduce parsing for given input () using below
grammar.

Prof. Maya B S, Assistant Professor, CSE,BIT 24

Viable Prefixes
• The set of prefixes of right sentential forms that can appear on the stack of a shift
–reduce parser are called viable prefixes.

• Construct shift-reduce action for string n+n using below grammar

• E’E

• EE+n |n

Prof. Maya B S, Assistant Professor, CSE,BIT 25

• E, E+, E+n are all viable prefixes of the right sentential form E+n

Prof. Maya B S, Assistant Professor, CSE,BIT 26

1. Give BUP parse tree for the following input=abbcde for grammar SaAcBe ,AAB|b ,Bd
.Find the handle for the above string each with right sentential form and also write shift-reduce
configuration for the same input.

Solution: 1. Handle prunning

Prof. Maya B S, Assistant Professor, CSE,BIT 27

2.Shift-Reduce Configuration
Stack Input Production
$ abbcde$ Shift ‘a’
$a bbcde$ Shift ‘b’
$ab bcde$ Reduce Ab
$aA bcde$ Shift ‘b’
$aAb cde$ Reduce AAb
$aA cde$ Shift ‘c’
$aAc de$ Shift ‘d’
$aAcd e$ Reduce Bd
$aAcB e$ Shift ‘e’
$aAcBe $ Reduce SaAcBe
$S $ Accept
Prof. Maya B S, Assistant Professor, CSE,BIT 28
3. Construct bottom up tree for input

• There are 2 rules as follows,

1. When an input symbol ‘a’ shift on to the stack a new node is created and it is
labeled as ‘a’.
2. When X1,X2, …..Xn is reduced to ‘A’ , a new node labled ‘A’ is created whose
children's are X1,X2….Xn.
S

a A B e
A b d
b c

Prof. Maya B S, Assistant Professor, CSE,BIT 29

Problems on Handle and shift reduce configuration, construct tree.

Prof. Maya B S, Assistant Professor, CSE,BIT 30

4. EE+E
|E*E
|(E)
| id for input id+id*id
5. Sa |^ | (T)
TT,S |S input (a,(a,a))

Prof. Maya B S, Assistant Professor, CSE,BIT 31

Conflicts during shift reduce parsing [V.V.IMP] [4M]

1. Shift- Reduce Conflict

2. Reduce –Reduce Conflict

[ Note: Refer Module-4: Yacc chapter for information]

Prof. Maya B S, Assistant Professor, CSE,BIT 32

LR Parser
The LR parser is a non-recursive, shift-reduce, bottom-up parser.

 It uses a wide class of context-free grammar which makes it the most efficient
syntax analysis technique.

LR parsers are also known as LR(k) parsers, where L stands for left-to-right
scanning of the input stream, R stands for the construction of right-most derivation
in reverse, and k denotes the number of lookahead symbols to make decisions.

Prof. Maya B S, Assistant Professor, CSE,BIT 33

Prof. Maya B S, Assistant Professor, CSE,BIT 34
• There are three widely used algorithms available for constructing an LR parser:

• SLR(1) – Simple LR Parser:

• Works on smallest class of grammar
• Few number of states, hence very small table
• Simple and fast construction

• LR(1) – LR Parser:
• Works on complete set of LR(1) Grammar
• Generates large table and large number of states
• Slow construction

• LALR(1) – Look-Ahead LR Parser:

• Works on intermediate size of grammar
• Number of states are same as in SLR(1)

Prof. Maya B S, Assistant Professor, CSE,BIT 35

Difference between LL and LR
LL LR
Does a leftmost derivation. Does a rightmost derivation in reverse.

Starts with the root nonterminal on the stack. Ends with the root nonterminal on the stack.

Ends when the stack is empty. Starts with an empty stack.

Uses the stack for designating what is still to be Uses the stack for designating what is already seen.
expected.
Builds the parse tree top-down. Builds the parse tree bottom-up.

Continuously pops a nonterminal off the stack, and Tries to recognize a right hand side on the stack,
pushes the corresponding right hand side. pops it, and pushes the corresponding nonterminal.

Expands the non-terminals. Reduces the non-terminals.

Reads the terminals when it pops one off the stack. Reads the terminals while it pushes them on the
stack.
Pre-order traversal of the parse tree. Post-order traversal of the parse tree.

Prof. Maya B S, Assistant Professor, CSE,BIT 36

LL V/S LR Parsing

Prof. Maya B S, Assistant Professor, CSE,BIT 37

Prof. Maya B S, Assistant Professor, CSE,BIT 38
Prof. Maya B S, Assistant Professor, CSE,BIT 39
Prof. Maya B S, Assistant Professor, CSE,BIT 40
Prof. Maya B S, Assistant Professor, CSE,BIT 41
Steps for construction of SLR Parser

Prof. Maya B S, Assistant Professor, CSE,BIT 42

Step1: Augmented grammar

Prof. Maya B S, Assistant Professor, CSE,BIT 43

Step2: Construction of LR(0) items

Prof. Maya B S, Assistant Professor, CSE,BIT 44

LR(0) items

Prof. Maya B S, Assistant Professor, CSE,BIT 45

Prof. Maya B S, Assistant Professor, CSE,BIT 46
LR(0) Automata

Prof. Maya B S, Assistant Professor, CSE,BIT 47

Prof. Maya B S, Assistant Professor, CSE,BIT 48
Algorithm for Closure of item sets

Prof. Maya B S, Assistant Professor, CSE,BIT 49

Prof. Maya B S, Assistant Professor, CSE,BIT 50
Example to computation of CLOSURE

Prof. Maya B S, Assistant Professor, CSE,BIT 51

Definition Kernel and Non-kernel items

Prof. Maya B S, Assistant Professor, CSE,BIT 52

Computation of GOTO( )

Prof. Maya B S, Assistant Professor, CSE,BIT 53

Algorithm to computation of GOTO( )

Prof. Maya B S, Assistant Professor, CSE,BIT 54

1.LR(0) Automata for grammar with closure and GOTO ( ).
[V.V.V.IMP] 8M EE+T |T, TT*F|F ,F(E) |id

Prof. Maya B S, Assistant Professor, CSE,BIT 55

Construction of SLR parsing table using Action and GOTO ()

Prof. Maya B S, Assistant Professor, CSE,BIT 56

2.LR(0) Automata for grammar with closure and GOTO ( ),
SL=R | R, L*R|id, RL [V>V.V.IMP] 8M

Prof. Maya B S, Assistant Professor, CSE,BIT 57

Construction of SLR parsing table

Prof. Maya B S, Assistant Professor, CSE,BIT 58

3.LR(0) Automata for grammar with closure and GOTO ( ) SE+S | E ,
Enum

Prof. Maya B S, Assistant Professor, CSE,BIT 59

Construction of SLR parsing table

Prof. Maya B S, Assistant Professor, CSE,BIT 60

LR Parsing Table

Prof. Maya B S, Assistant Professor, CSE,BIT 61

Algorithm for construction of SLR parse table [5M]

Prof. Maya B S, Assistant Professor, CSE,BIT 62

Prof. Maya B S, Assistant Professor, CSE,BIT 63
LR Parsing with Stack operation

Prof. Maya B S, Assistant Professor, CSE,BIT 64

Prof. Maya B S, Assistant Professor, CSE,BIT 65
Prof. Maya B S, Assistant Professor, CSE,BIT 66
Algorithm for LR-parsing [5M] IMP

Prof. Maya B S, Assistant Professor, CSE,BIT 67

Continue….

Prof. Maya B S, Assistant Professor, CSE,BIT 68

Problem 1: Continue to parse input

Prof. Maya B S, Assistant Professor, CSE,BIT 69

LR Parsing for input id+id*id

Prof. Maya B S, Assistant Professor, CSE,BIT 70

Problems on SLR
1. SA
Aa |ab
2. SA
A(A ) | ( )
3. SSA |A
Aa input=aa [hint:state=5]
4. E(L) |a
LEL |E input=(aa) [hint:state=8]
5. S(L) |a
LL,S |S input=(a,a) [hint:state=9]

Prof. Maya B S, Assistant Professor, CSE,BIT 71

6. SaSbS |bSaS |Є input=abab [hint:state=10]

7. SAaAb | BbBa

A Є

B Є input=ab [hint:state=10]

8.SL=R |R

L*R |id

RL input=id=*id [hint:state=10]

Prof. Maya B S, Assistant Professor, CSE,BIT 72

THANK YOU

Prof. Maya B S, Assistant Professor, CSE,BIT 73