LR(0) and SLR(1) Parsers

C.Naga Raju
B.Tech(CSE),M.Tech(CSE),PhD(CSE),MIEEE,MCSI,MISTE
Professor
Department of CSE
YSR Engineering College of YVU
Proddatur

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570 1

Contents
• Introduction to bottom up parsers
• LR(0) Parser
• Example problem
• Gate Questions and solutions
• SLR(1) Parser
• Example problem
• Gate Questions and solutions

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Bottom up Parser
• Construction of parse tree for any given input string
beginning at the bottom and working towards the root is
called bottom up parser
For example the given input string : id*id

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

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

id id F id T*F

id F id

id
Prof.C.NagaRaju YSRCE of YVU CSE 9949218570
Shift-Reduce Parsing
• The general idea is to shift some symbols of input to the
stack until a reduction can be applied
• At each reduction step, if a specific substring is matched
then the body of a production is replaced by the Non
Terminal at the head of the production A—>ac/b
• The key decisions during bottom-up parsing are about when
to reduce and what production should apply
• A reduction is a reverse of a step in a derivation
• The goal of a bottom-up parser is to construct a derivation in
reverse:
– E=>T=>T*F=>T*id=>F*id=>id*id
Prof.C.NagaRaju YSRCE of YVU CSE 9949218570
LR Parsers
LR(k)
LR k

Left-to-Right Rightmost Derivation In Number Of Input

scan Reverse Symbols Of Look
Ahead

Prof.C.NagaRaju YSRCE of YVU 5

CSE 9949218570
❖ Types of LR Parsers
1.LR(0) Parser
2.Simple LR-Parser (SLR)
3.Canonical LR Parser (CLR)
4.LALR Parser.

Prof.C.NagaRaju YSRCE of YVU 6

CSE 9949218570
Comparison of LL & LR Methods

LL(1)

LR(1) LALR SLR LR(0) LL(0)

Prof.C.NagaRaju YSRCE of YVU 7

CSE 9949218570
▪ Advantages of LR Parsers
▪ LR parsers are constructed to recognize all
Programming Languages

▪ The LR-parsing is Non-Backtracking Shift-

Reduce Parser

▪ An LR parser can detect a syntactic errors

▪ It scans input string from left-to-right and use

left most derivation in reverse

Prof.C.NagaRaju YSRCE of YVU 8

CSE 9949218570
•The LR Parsing Algorithm
Input

a1 a2 … ai … an $ Scanner

sm LR Parsing Engine
Xm
sm-1
Xm-1
Compiler Construction
…
s0 Parser
Action Goto Grammar
Generator
Stack
LR Parsing Tables

Prof.C.NagaRaju YSRCE of YVU 9

CSE 9949218570
❖ The LR parser consists of 1) Input 2)Output
3)Stack 4) Driver Program 5) Parsing Table

❖ The Driver Program is same for all LR Parsers.

❖ Only the Parsing Table changes from one parser

to the other.

❖ In CLR method the stack holds the states from the

LR(0)automation and canonical LR and LALR
methods are same

Prof.C.NagaRaju YSRCE of YVU 10

CSE 9949218570
❖ The Driver Program uses the Stack to store a
string

s0X1s1X2…Xmsm

✓ Where sm is the Top of the Stack.

✓ The Sk‘s are State Symbols

✓ The Xi‘s are Grammar Symbols.

✓ Together State and Grammar Symbols

determine a Shift-reduce Parsing Decision.

Prof.C.NagaRaju YSRCE of YVU 11

CSE 9949218570
❖ The Parsing Program reads characters from an
Input Buffer one at a time

❖ The Current Input Symbols are used to index the

parsing table and determine the shift-reduce
parsing decision

❖ In an implementation, the grammar symbols need

not appear on the stack

Prof.C.NagaRaju YSRCE of YVU 12

CSE 9949218570
Parse Table
❖ The LR Shift-Reduce Parsers can be efficiently
implemented by computing a table to guide the
processing

❖ The Parsing Table consists of two parts:

1. A Parsing Action Function and

2. A GOTO function.

Prof.C.NagaRaju YSRCE of YVU 13

CSE 9949218570
❖ The Action Table
❖ The Action Table specifies the actions of the parser
(e.g., shift or reduce), for the given parse state and
the next token

✓ Rows are State Names;

✓ Columns are Terminals

Prof.C.NagaRaju YSRCE of YVU 14

CSE 9949218570
LR Driver Program
❖ The LR driver Program determines Sm, the state on
top of the stack and ai, the Current Input symbol.

❖ It then consults Action[ Sm, ai ] which can take one

of four values:

✓ Shift

✓ Reduce

✓ Accept

✓ Error

Prof.C.NagaRaju YSRCE of YVU 15

CSE 9949218570
❖ If Action[ Sm, ai ] = Shift S

✓ Where S is a State, then the Parser pushes

ai and S on to the Stack.

❖ If Action[ Sm, ai ] = Reduce A → β,

✓ Then ai and Sm are replaced by A

✓ if S was the state appearing below ai in the

Stack, then GOTO[S, A] is consulted and the
state pushed onto the stack.

Prof.C.NagaRaju YSRCE of YVU 16

CSE 9949218570
❖ If Action[ Sm, ai ] = Accept,

✓ Parsing is completed

❖ If Action[ Sm, ai ] = Error,

✓ The Parser discovered an Error.

Prof.C.NagaRaju YSRCE of YVU 17

CSE 9949218570
❖ GOTO Table
❖ The GOTO table specifies which state to put on
top of the stack after a reduce

✓Rows are State Names;

✓Columns are Non-Terminals

18
Prof.C.NagaRaju YSRCE of YVU CSE 9949218570
❖ The GOTO Table is important to find out the next
state after every reduction.

❖ The GOTO Table is indexed by a state of the

parser and a Non Terminal (Grammar Symbol)

ex : GOTO[S, A]

❖ The GOTO Table simply indicates what the next

state of the parser if it has recognized a certain
Non Terminal. Prof.C.NagaRaju YSRCE of YVU
CSE 9949218570
19
❖ Right Sentential Form is a Sentential Form in a
Rightmost Derivation

Example: (S)S , ( (S)S)

❖ Viable Prefix is a sequence of symbols on the

parsing stack

Example:

✓ (S)S, (S), (S, (,

✓ ((S)S, ((S), ((S , ((, (

Prof.C.NagaRaju YSRCE of YVU 20

CSE 9949218570
LR(0) Parser
❖ The LR Parser is a Shift-reduce Parser that makes
use of a Deterministic Finite Automata, recognizing
the Set Of All Viable Prefixes by reading the stack
from Bottom To Top.

❖ if a Finite-State Machine that recognizes viable

prefixes of the right sentential forms is constructed,
it can be used to guide the handle selection in the
Shift-reduce Parser.

Prof.C.NagaRaju YSRCE of YVU 21

CSE 9949218570
❖ Handle: Handle is a substring that matches the
body of a production
❖ Handle is a Right Sentential Form + position
where reduction can be performed + production
used for reduction

Example

( S ) S. With S → Є

( S ) .S With S → S

((S)S.) With S → ( S ) S

Prof.C.NagaRaju YSRCE of YVU 22

CSE 9949218570
• Handle pruning : Handle pruning specifies that the reduction
represents one step along the reverse of a rightmost
derivation

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

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Augmented Grammar
❖ If G is a Grammar with Start Symbol S, the
Augmented Grammar G’ is G with a New Start
Symbol S`, and New Production S` →S$.
.

❖ The Purpose of the Augmented Grammar is to

indicate to the parser when it should stop parsing
and announce acceptance of the input

Prof.C.NagaRaju YSRCE of YVU 24

CSE 9949218570
LR(0) Items
An LR(0) Item of a Grammar G is a Production of G
with a Dot ( ) at some position of the right side.

.Production A → XYZ yields the Four items:

1. A→•XYZ We hope to see a string derivable

from XYZ next on the input.

2. A→X•YZ We have just seen on the input a

string derivable from X and that we hope next
to see a string derivable from YZ next on the
input. Prof.C.NagaRaju YSRCE of YVU
CSE 9949218570
25
3. A→XY•Z

4. A→XYZ•

❖ The production A→ generates only one item,

A→•.

❖ Each of this item is a Viable prefixes

❖ Closure Item : An Item created by the closure

operation on a state.

❖ Complete Item : An Item where the Item Dot is

at the end of the RHS.
Prof.C.NagaRaju YSRCE of YVU 26
CSE 9949218570
LR(0) Example

Context Free Grammar:

S→E rule1: (S→S’)
E→T Augumented Grammar
E→E+T
T→i S → •E
T→(E) E → •T
E → •E+T
T → •i
T → •(E)
Prof.C.NagaRaju YSRCE of YVU 27
CSE 9949218570
Construction of LR(0) Closure Items
S6
E → T•

T T S7
S0
S → •E$ T → (•E)
E → •T E → •T
( E → •E+T
E → •E+T
T → •i T → •i
T → •(E) S5 T → •(E) (
i
i

E T → i• E
( S8
S1
S → E•$ T → (E•)
E → E•+T i E → E•+T

+ +
)
$ E → E+•T
S3 T → •i
S2 T → •(E) S9

S → E$• T → (E)•
T
S4
Prof.C.NagaRaju YSRCE of YVU 28
E → E+T•
CSE 9949218570
Construction of LR(0) Items

I0: I1:Goto(I0,E) I2 :Goto(I1,$ ) I3 :Goto(I1,+ ) I4 :Goto(I3,T )

S → •E$ S→E•$ S→E$• E →E+T •
E→E+•T
E→•T E→E•+T
T→•i
E→•E+T T → • (E)
I5 :Goto(I0,i) I5 :Goto(I3,i) I7 :Goto(I0,( )
T→•i T →( •E)
T→i• T→i•
T → • (E) I6 :Goto(I0,T) E→•T
E→T• E→•E+T
I8 :Goto(I7,E) I9 :Goto(I7, ) )
T→•i
T →( E•) T →( E )•
T → • (E)
T → E•+ T

Prof.C.NagaRaju YSRCE of YVU 29

CSE 9949218570
Construction of DFA for LR(0) Items
$
I1 I2
+
E
T
i I3 I4
I5
i

I0 T i (
I6
T
( I9

I7 I8 S
E

Prof.C.NagaRaju YSRCE of YVU 30

CSE 9949218570
Construction of LR(0) Parsing Table
Input
States Action Part (Terminals) Goto Part
(Non-
Terminals)
i + ( ) $ E T
0 5 7 1 6 Shift
1 3 2 Shift
2 S→E$ Reduce
3 5 7 4 Shift
4 E→E+T Reduce
5 T→i Reduce
6 E→T Reduce
7 5 7 8 6 Shift
8 3 9 Shift
9 T→(E) Reduce
Prof.C.NagaRaju YSRCE of YVU 31
CSE 9949218570
String Acceptance
Input
States Action Part (Terminals) Goto Part (Non-
Terminals)
i + ( ) $ E T
0 5 7 1 6 Shift
1 3 2 Shift
2 S→E$ Reduce
3 5 7 4 Shift
4 E→E+T Reduce
5 T→i Reduce
6 E→T Reduce
7 5 7 8 6 Shift
8 3 9 Shift
9 T→(E) Reduce

Stack Input Action

S0 i + (i + i) $ Shift
S0 i S5 + (i + i) $ Reduce by T→i
S0 T S6 + (i + i) $ Reduce by E→T
S0 E S1 + (i + i) $ Shift
Prof.C.NagaRaju YSRCE of YVU 32
S0 E S1 + S3 (i + i) $
CSE 9949218570
Shift
String Acceptance
Input
States Action Part (Terminals) Goto Part (Non-
Terminals)
i + ( ) $ E T
0 5 7 1 6 Shift
1 3 2 Shift
2 S→E$ Reduce
3 5 7 4 Shift
4 E→E+T Reduce
5 T→i Reduce
6 E→T Reduce
7 5 7 8 6 Shift
8 3 9 Shift
9 T→(E) Reduce

Stack Input Action

S0 E S1 + S3 ( i + i) $ shift
S0 E S1 + S3 ( S7 i + i) $ shift
S0 E S1 + S3 ( S7iS5 + i)$ reduce by T→i
S0 E S1 + S3 ( S7TS6 + i)$ reduce by E→T
S0 E S1 + S3 ( S7ES8 Prof.C.NagaRaju
+ i)$YSRCE of YVU shift 33
CSE 9949218570
String Acceptance
Input
States Action Part (Terminals) Goto Part (Non-
Terminals)
i + ( ) $ E T
0 5 7 1 6 Shift
1 3 2 Shift
2 S→E$ Reduce
3 5 7 4 Shift
4 E→E+T Reduce
5 T→i Reduce
6 E→T Reduce
7 5 7 8 6 Shift
8 3 9 Shift
9 T→(E) Reduce

Stack Input Action

S0 E S1 + S3 ( S7ES8 +i)$ shift
S0 E S1 + S3 ( S7ES8+S3 i)$ shift
S0 E S1 + S3 ( S7ES8+S3iS5 ) $ reduce by T→i
S0 E S1 + S3 ( S7ES8+S3TS4 ) $ reduce by E→E+T
S0 E S1 + S3 ( S7ES
Prof.C.NagaRaju
8 ) $ of YVU
YSRCE shift 34
CSE 9949218570
String Acceptance
Input
States Action Part (Terminals) Goto Part (Non-
Terminals)
i + ( ) $ E T
0 5 7 1 6 Shift
1 3 2 Shift
2 S→E$ Reduce
3 5 7 4 Shift
4 E→E+T Reduce
5 T→i Reduce
6 E→T Reduce
7 5 7 8 6 Shift
8 3 9 Shift
9 T→(E) Reduce

Stack Input Action

S0 E S1 + S3 ( S7ES8 )$ shift
S0 E S1 + S3 ( S7ES8)S9 $ reduce by T→(E)
S0 E S1 + S3TS4 $ reduce by E→E+T
S0 E S1 $ shift
S0 E S1$S2 reduce by S→E$
S0 S Prof.C.NagaRaju YSRCE of YVU accept 35
CSE 9949218570
Draw backs of LR(0) Parser
❖ LR(0) is the Simplest Technique in the LR family.

❖ LR(0) Parsers are too weak to be of practical use

❖ LR(0) accepts only small class of LR(0) grammar

because if conflicts occurs.

❖ The Fundamental Limitation of LR(0) is that no look

ahead tokens are used.

❖ LR(0) Parsing is the weakest and it is not used

much in practice because of its limitations.
Prof.C.NagaRaju YSRCE of YVU 36
CSE 9949218570
GATE QUESTIONS AND SOLUTIONS

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 1
Consider the grammar
E→E+n|E×n|n
For a sentence n + n × n, the handles in the right-sentential form
of the reductions are ? (GATE 2005)

A. n, E + n and E + n × n
B. n, E + n and E + E × n
C. n, n + n and n + n × n
D. n, E + n and E × n

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• E → E * n {Applying E → E * n }
• E→ E + n * n {Applying E → E + n }
• E→ n + n * n {Applying E → n } Hence, the handles in right
sentential form is n, E + n and E × n.
• Hence Option D is the right choice

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 2
A bottom-up parser generates:

A. Left-most derivation in reverse

B. Right-most derivation in reverse
C. Left-most derivation
D. Right-most derivation

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• A bottom-up parser generates right-most derivation in reverse

• Option (B) is correct.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 3
Consider the following statements related to compiler
construction :
I. Lexical Analysis is specified by context-free grammars and
implemented by pushdown automata.
II. Syntax Analysis is specified by regular expressions and
implemented by finite-state machine.
Which of the above statement(s) is/are correct ?

A. Only I
B. Only II
C. Both I and II
D. Neither I nor II

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• Both statements are wrong for detailed information on lexical

analysis and syntax analysis
• option (D) is correct.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 4
Which of these is true about LR parsing?

A. Is most general non-backtracking shift-reduce parsing

B. It is still efficient
C. Both a and b
D. None of the mentioned

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• LR parsers are a type of bottom-up parsers that efficiently

handle deterministic context-free languages in guaranteed
linear time.
• option (C) is correct.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 5
Which of the following is incorrect for the actions of A LR-Parser
I) shift s
ii) reduce A->ß
iii) Accept
iv) reject?

A. Only I)
B. I) and ii)
C. I), ii) and iii)
D. I), ii) , iii) and iv)

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• Only reject out of the following is a correct LR parser action

• Option C is correct

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 6
If a state does not know whether it will make a shift operation or
reduction for a terminal is called

A. Shift/reduce conflict
B. Reduce /shift conflict
C. Shift conflict
D. Reduce conflict

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• As the name suggests that the conflict is between shift and

reduce hence it is called shift reduce conflict
• Option A is correct

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 7
When there is a reduce/reduce conflict?

A. If a state does not know whether it will make a shift operation

using the production rule i or j for a terminal.
B. If a state does not know whether it will make a shift or
reduction operation using the production rule i or j for a
terminal.
C. If a state does not know whether it will make a reduction
operation using the production rule i or j for a terminal.
D. None of the mentioned

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• It occurs when If a state does not know whether it will make a

reduction operation using the production rule i or j for a
terminal.
• Option C is correct

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

SLR(1) Parser
❖ We will find that it allows for a much larger class of
grammars to be parsed.
❖ SLR(1) Parser is used for accepting the certain
grammar which is not accepted by LR(0) parser
❖ The letters “SLR” stand for “Simple”, “Left” and
“Right”.
✓ “Left” indicates that the input is read from left
to right and
✓ The “Right” indicates that a right-derivation is
built. Prof.C.NagaRaju YSRCE of YVU
CSE 9949218570
52
❖ SLR(1) Parser stands for Simple LR(1).

❖ SLR(1) parsers use the same LR(0) Configurating

Sets and have the Same Table Structure and Parser
Operation, So everything you've already learned
about LR(0) applies here.

❖ The difference in SLR(1) Parser with LR(0) Parser

comes in Assigning Table Actions,

Prof.C.NagaRaju YSRCE of YVU 53

CSE 9949218570
❖ SLR(1) Parsers are going to use one token of
lookahead to eliminate the conflicts.

❖ In LR(0) parsing, Reduce Actions that cause the

problem

❖ The Simple Improvement that SLR(1) makes on the

basic LR(0) parser is to reduce only if the next input
token is a member of the Follow Set of the non-
terminal being reduced.

Prof.C.NagaRaju YSRCE of YVU 54

6/16/2020© Copyright 2007 Stephen M. Watt CSE 9949218570
❖ SLR(1) parser will perform a reduce action for
configuration B→a• if the lookahead symbol is in
the set Follow(B)

❖ A Grammar is an SLR(1) grammar if there is no

conflict in the grammar.
❖ Clearly SLR(1) is a proper superset of LR(0)

SLR(1) LR(0)

Prof.C.NagaRaju YSRCE of YVU 55 55

CSE 9949218570
Example: SLR(1) Parser
❖ Construct the SLR(1) Parser for the Following
Grammar

Context Free Grammar:

E→E+T
E→T
T→T * F
T→F
F→(E)
F → id
Prof.C.NagaRaju YSRCE of YVU 56
6/16/2020© Copyright 2007 Stephen M. Watt CSE 9949218570
Step 1: Define a Augmented Grammar
Context Free Grammar: Augmented Grammar:
E→E+T E’ → E#
E→T E→E+T
T→T * F E→T
.
T→F T→T * F
F→(E) T→F
F → id F→(E)
F → id

Prof.C.NagaRaju YSRCE of YVU 57

CSE 9949218570
Step2 : Constructing SLR(1) Automaton

Context Free Grammar: Adding the SLR(1) Item

E’ → E# E’ →.E#
E → .E + T
E→E+T
E→T

E → .T
T→T * F
T→F

T → .T * F
F→(E)
F → id

T → .F

F → .( E )

Prof.C.NagaRaju YSRCE of YVU F → . id 58

CSE 9949218570
E → E+.T S9
S1 E’ → E.# +
T → .T*F T E → E + T.
E → E.+T T → .F T → T.* F
F F → .(E) S6
F → .id
E
S3 id
( *
S5
S0 E’ →.E# T S4
S
E →.E+T E2→ T. S10
E →.T T→ T. * F * T → T*F.
F
T →.T*F S7
T →.F T → T*.F
F →.(E) F →.(E)
T F →.id
F →.id (
S11
id ( id
S4 F → (E).
S5 F →(.E) S5
F F → id. id E →.E+T
)
E →.T
F T →.T*F E
T →.F F → (E.)
S3 F →.(E) E → E.+T
T → F. F →.id S8
(
Prof.C.NagaRaju YSRCE of YVU + 59
CSE 9949218570 S6
Constructing the SLR(1) Items
I0: I1:Goto(I0,E ) I6:Goto(I1,+) I3:Goto(I4,F) I4:Goto(I7,( )
E→ E.# T→ F.
E’ →.E# E →E+.T
E→ E.+T I5:Goto(I7,id)
E →.E + T T→.T * F I4:Goto(I4,( )
E →.T I2:Goto(I0,T) T→.F
E→ T. F→.( E ) I5:Goto(I4,id) I3:Goto(I4,F)
T →.T * F
E→ T.*F F →.id
T →.F I9:Goto(I6,T) I7:Goto(I9,* )
F →.( E ) I3:Goto(I0,F) I7:Goto(I2,*)
E →E+T.
F →.id T→ F. E→ T*.F I6:Goto(I8,+)
T→ T.* F
F→ .( E )
I4:Goto(I0,( ) I5:Goto(I0,id) I4:Goto(I6,( )
F→ .id
T→id.
F→(. E)
I10:Goto(I7,F) I5:Goto(I6,id)
E→.E+T I8:Goto(I4,E)
T→T * F . T→id.
E→.T E→ (E.)
T→.T * F E →E.+T I3:Goto(I6,F)
I11:Goto(I8,) )
T→.F T→ F.
I2:Goto(I4,T) T→(E).
F→.( E ) E→ T. Prof.C.NagaRaju YSRCE of YVU 60
F →.id E→ T.*F CSE 9949218570
Construction of DFA for SLR(1) Items

+ T
S6 S9 *
S1
( S7
F
id
E S3
S4
S2 S5
T *
T ( F
( S10
S0 S7
S4 S3 (
id id
F S4
id E
F S5
S5
S8 )
S11
+
S3
S6 YSRCE of YVU
Prof.C.NagaRaju 61
CSE 9949218570
Construction of Follow Function
E’ →.E# Follow (E) = { # , + , ) }
E →.E + T ( r1 )
Follow (T) = { * , # , + , ) }
E →.T ( r2 )
T →.T * F ( r3 ) Follow (F) = { * , # , + , ) }
T →.F ( r4 )
F →.( E ) ( r5 )

F →.id ( r6 )

Prof.C.NagaRaju YSRCE of YVU 62

CSE 9949218570
Constructing the SLR(1) Parsing Table
Input
States Action Part Goto Part

id + * ( ) $ E T F
0 S5 S4 1 2 3
1 S6 Acc
2 r2 S7 r2 r2
3 r4 r4 r4 r4
4 S5 S4 8 2 3
5 r6 r6 r6 r6
6 S5 S4 9 3
7 S5 S4 10
8 S6 S11
9 r1 S7 r1 r1
10 r3 r3 r3 YSRCE
Prof.C.NagaRaju r3 of YVU 63

11 r5 r5 r5 r5
CSE 9949218570
Input Acceptance

Prof.C.NagaRaju YSRCE of YVU 64

CSE 9949218570
String Acceptance
id * id + id id * id + id$

In S0 with input
symbol id, shift the
symbol onto the stack
and enter state S5

Prof.C.NagaRaju YSRCE of YVU 65

CSE 9949218570
String Acceptance
id * id + id id * id + id$

S5 with input symbol *

Reduce
using grammar
production6

Prof.C.NagaRaju YSRCE of YVU 66

CSE 9949218570
String Acceptance
id * id + id id * id + id$

S5 with input symbol *

Reduce
using grammar
production6

Prof.C.NagaRaju YSRCE of YVU 67

CSE 9949218570
String Acceptance
id * id + id id * id + id$

T2

Reduction exposes S0
and goto of S0 gives
next state for the
leading non-terminal,
T. The next state is S2

Prof.C.NagaRaju YSRCE of YVU 68

CSE 9949218570
String Acceptance
id * id + id id * id + id$

Prof.C.NagaRaju YSRCE of YVU 69

CSE 9949218570
String Acceptance
id * id + id id * id + id$

Prof.C.NagaRaju YSRCE of YVU 70

CSE 9949218570
String Acceptance
id * id + id id * id + id$

Prof.C.NagaRaju YSRCE of YVU 71

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(7) 0T2*7 F 10

Reduction exposes S7
and goto of S7 gives
next state for the
leading non-terminal,
F. The next state is S10

Prof.C.NagaRaju YSRCE of YVU 72

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(7) 0 T 2 * 7 F 10 + id $ Reduce T → T*F

(8) 0T2 + id $

Prof.C.NagaRaju YSRCE of YVU 73

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(8) 0T 2 + id $ Reduce E → T

Prof.C.NagaRaju YSRCE of YVU 74

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(8) 0T + id $ Reduce E → T
(9) 0 E 1 + id $

Prof.C.NagaRaju YSRCE of YVU 75

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(9) 0E 1 + id $ Shift
(10) 0E1+6 id $

Prof.C.NagaRaju YSRCE of YVU 76

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(10) 0E1+6 id $ Shift

(11) 0 E 1 + 6 id 5 $

Prof.C.NagaRaju YSRCE of YVU 77

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(11) 0 E 1 + 6 id 5 $ Reduce F → id
(12) 0E1+6 F $

Prof.C.NagaRaju YSRCE of YVU 78

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(12) 0E1+6 F 3 $

(12) 0E1+6 F3 $

Prof.C.NagaRaju YSRCE of YVU 79

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(12) 0E1+6 F3 $ Reduce T → F

(13) 0E1+6 T $

Prof.C.NagaRaju YSRCE of YVU 80

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(13) 0E1+6 T 9 $

Prof.C.NagaRaju YSRCE of YVU 81

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(13) 0E1+6 T9 $ Reduce E→E+T

(14) 0E1 $

Prof.C.NagaRaju YSRCE of YVU 82

CSE 9949218570
String Acceptance
id * id + id id * id + id$

(13) 0E1 $ Accept

Prof.C.NagaRaju YSRCE of YVU 83

CSE 9949218570
String Acceptance id * id + id$
STACK INPUT ACTION

(1) 0 id * id +id$ shift

(2) 0 id 5 * id +id$ reduced by F → id
(3) 0 F5 * id +id$ reduced by T→F
(4) 0 T2 * id +id$ shift
(5) 0 T2*7 id +id$ shift
(6) 0 T 2 * 7 id 5 +id$ reduced by F → id
(7) 0 T 2 * 7 F 10 +id$ reduced by T → T*F
(8) 0 T2 +id$ reduced by E→T
(9) 0 E1 +id$ shift
(10) 0 E1+6 id$ shift
(11) 0 E 1 + 6 id 5 $ reduced by F → id
(12) 0 E1+6F3 $ reduced by T→F
(13) 0 E1+6T9 $ E→E+T
(14) 0 E1 Prof.C.NagaRaju YSRCE of $
YVUaccept 84
CSE 9949218570
Observation
❖ the Shift/Reduce Conflict arises from the fact that
the SLR parser construction method is not powerful
enough to remember enough left context to decide
what action the parser should take on input = has
seen a string reducible to L.

❖ That is “R=“ cannot be a part of any Right

Sentential Form. So when “L” appears on the top of
stack and “=“ is the current character of the input
buffer , we can not reduce “L” into “R”.
Prof.C.NagaRaju YSRCE of YVU 85
CSE 9949218570
❖ Every SLR Grammar is Unambiguous, but Every
Unambiguous Grammar is not a SLR grammar.

❖ If the SLR parsing table of a grammar G has a Conflict,

we say that Grammar is not SLR Grammar.

Prof.C.NagaRaju YSRCE of YVU 86

CSE 9949218570
Drawbacks
❖ SLR(1) parsers cannot parse some LR grammars.

❖ The Main Problem of SLR(1) Parser is that Lookahead

Information is added to LR(0) parser at the end of
construction based on FOLLOW sets

❖ In SLR(1) parsing, we reduce A→α for ANY lookahead a

Є FOLLOW(A), which is too general such that
sometimes a reduction cannot occur for some a Є
FOLLOW(A)
Prof.C.NagaRaju YSRCE of YVU 87
CSE 9949218570
Drawbacks
❖ if the Grammar contains Reduce/Reduce Conflict then,
we say that Grammar is not SLR(1) Grammar.

Prof.C.NagaRaju YSRCE of YVU 88

CSE 9949218570
GATE QUESTIONS AND SOLUTIONS

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 1
• Consider the following two statements: P: Every regular
grammar is LL(1) Q: Every regular set has a LR(1) grammar
Which of the following is TRUE? (GATE 2007)

A. Both P and Q are true

B. P is true and Q is false
C. P is false and Q is true
D. Both P and Q are false

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation
• A regular grammar can also be ambiguous also For example,
consider the following grammar, S → aA/a A → aA/ε In above
grammar, string 'a' has two leftmost derivations.
• (1) S → aA (2) S → a S->a (using A->ε) And LL(1) parses only
unambiguous grammar, so statement P is False.
• Statement Q is true is for every regular set, we can have a
regular grammar which is unambiguous so it can be parse by
LR parser.
• So option C is correct choice

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 2
A canonical set of items is given below
S → L. > R
Q → R.
On input symbol < the set has? (GATE 2014)

A. a shift-reduce conflict and a reduce-reduce conflict.

B. a shift-reduce conflict but not a reduce-reduce conflict.
C. a reduce-reduce conflict but not a shift-reduce conflict.
D. neither a shift-reduce nor a reduce-reduce conflict

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation
• The question is asked with respect to the symbol ' < ' which is
not present in the given canonical set of items.
• Hence it is neither a shift-reduce conflict nor a reduce-reduce
conflict on symbol '<‘.
• So option D is correct choice
• But if the question would have asked with respect to the
symbol ' > ' then it would have been a shift-reduce conflict.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 3
Which of the following is true?

A. Canonical LR parser is LR (1) parser with single look ahead

terminal
B. All LR(K) parsers with K > 1 can be transformed into LR(1)
parsers.
C. Both (A) and (B)
D. None of the above

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• Canonical LR parser is LR (1) parser with single look ahead

terminal. All LR(K) parsers with K > 1 can be transformed into
LR(1) parsers.
• Option (C) is correct.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 4
The construction of the canonical collection of the sets of LR (1)
items are similar to the construction of the canonical collection of
the sets of LR (0) items. Which is an exception?

A. Closure and goto operations work a little bit different

B. Closure and goto operations work similarly
C. Closure and additive operations work a little bit different
D. Closure and associatively operations work a little bit different

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• Closure and goto do work differently in case of LR (0) and LR

(1)
• Option (A) is correct.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 5
When ß ( in the LR(1) item A -> ß.a,a ) is not empty, the look-
head

A. Will be affecting.
B. Does not have any affect.
C. Shift will take place.
D. Reduction will take place.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• There is no terminal before the non terminal beta

• Option (B) is correct.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Question 6
When ß is empty (A -> ß.,a ), the reduction by A-> a is done

A. If next symbol is a terminal

B. Only If the next input symbol is a
C. Only If the next input symbol is A
D. Only if the next input symbol is a

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Explanation

• The next token is considered in this case it’s a

• Option (D) is correct.

Prof.C.NagaRaju YSRCE of YVU CSE 9949218570

Thank U

Prof.C.NagaRaju YSRCE of YVU 102

CSE 9949218570