Module 3

Syntax Analysis

By,
Mrs Snitha Shetty,
Assistant Professor,
Dept. of CSE,
AJIET, Mangaluru
Outline
• Introduction
• Context free grammars
• Writing a grammar
• Top down parser
• Bottom up parser
Role of parser

token
Source Lexical Parse tree Semantic Intermediate
Parser
program Analyzer Analyser representation
getNext
Token

Symbol
table
Role of Parser
• We categorize the parsers into two groups:

• Top-Down Parser- The parse tree is created top to bottom, starting from the root.
• Bottom-Up Parser- The parse is created bottom to top; starting from the leaves

• Both top-down and bottom-up parsers scan the input from left to
right (one symbol at a time).
Common programming errors
• Lexical errors: include misspelling of identifiers, keywords,
or operators.

• Syntactic errors: include misplaced semicolons or extra or

missing braces.

• Semantic errors: include type mismatches between

operators and operands.

• Logical Errors: can be anything from incorrect reasoning on

the part of the programmer.
Error handler goals

• Report the presence of errors clearly and accurately

• Recover from each error quickly enough to detect subsequent errors
• Add minimal overhead to the processing of correct programmers
Error-recover strategies
• Panic mode recovery
• Discard input symbol one at a time until one of designated set of
synchronization tokens is found
• Phrase level recovery
• Replacing a prefix of remaining input by some string that allows the parser to
continue
• Error productions
• Augment the grammar with productions that generate the erroneous
constructs
• Global correction
• Choosing minimal sequence of changes to obtain a globally least-cost
correction
Context free grammars(CFG)
• It is a formal grammar which is used to generate all possible patterns of
strings in a given formal language.
• CFG can be defined by four tuples : G=(V,T,P,S)
• G is a grammar which consists of a set of production rules. It is used to
generate the string of language.
• V-Non terminals-Capital letters
• T- Terminals-lowercase letters
• P- Set of production rules which is used for replacing non-terminal symbol
in a string with other terminal or non-terminal symbols.
• S-Start symbol-used to derive the string
Eg for grammars

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

E -> TE’
E’ -> +TE’ | Ɛ
T -> FT’
T’ -> *FT’ | Ɛ
F -> (E) | id


Derivations
• Productions are treated as rewriting rules to generate a string
• Rightmost and leftmost derivations
• E -> E + E | E * E | -E | (E) | id
• Derivations for –(id+id)
• E => -E
=>-(E)
=>-(E+E)
=>-(id+E)
=>-(id+id)
Parse trees
• -(id+id)
• E => -E => -(E) => -(E+E) => -(id+E)=>-(id+id)

=>-(E+id)=>-(id+id)
Ambiguity
• For some strings there exist more than one parse tree
• Or more than one leftmost derivation
• Or more than one rightmost derivation
• Example: id+id*id
Consider the CFG S->SS+|SS*|a
string is aa+a*
1)Give a LMD
2)Give a RMD
3)Give a Parse tree
4) Whether Grammar is ambiguous or not?
 LMD RMD
S->S(S)S|ε (()()) S=>S(S)S S=>S(S)S
⇒ε(S)S =>S(S) ε
⇒(S(S)S)S =>S(S(S)S)
⇒(ε(S)S)S =>S(S(S)S(S)S)
⇒((ε)S)S =>S(S(S)S(S) ε)
⇒(()S(S)S)S =>S(S(S)S(ε))
⇒(() ε(S)S)S
=>S(S(S) ε())
⇒(()() ε)S
⇒(()()) ε =>S(S(ε)())
⇒(()()) =>S(ε()())
⇒ε(()())
⇒(()())
Eliminating Ambiguity
Left Recursion and Left Factoring
Left Recursion
• A production of grammar is said to have left recursion if the leftmost
variable of its RHS is same as variable of its LHS.
• A grammar containing a production having left recursion is called as
Left Recursive Grammar.

Eg:- S → Sa / ∈

• Left recursion is considered to be a problematic situation for Top

down parsers.
• Therefore, left recursion has to be eliminated from the grammar.
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
Eliminating Left Recursion
• Left recursion is eliminated by converting the grammar into a right
recursive grammar.
• If we have the left-recursive pair of productions-

A → Aα / β(Left Recursive Grammar) where β does not begin with an A.

Then, we can eliminate left recursion by replacing the pair of productions

with-
A → βA’
A’ → αA’ / ∈ (Right Recursive Grammar)
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
1.Consider the following grammar and
eliminate left recursion
B → Be / b

B → bB’
B’ → eB’ / ∈

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
2. Consider the following grammar and eliminate left
recursion
1. A → ABd / Aa / a

The grammar after eliminating left recursion is-

A → aA’
A’ → BdA’ / aA’ / ∈

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
3. Consider the following grammar and eliminate left recursion

S→A
A → Ad / Ae / aB / ac
B → bBc / f

The grammar after eliminating left recursion is-

S→A
A → aBA’ / acA’
A’ → dA’ / eA’ / ∈
B → bBc / f

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
4. Consider the following grammar and eliminate left recursion

E→E+T/T
T→T*F/F
F → id

The grammar after eliminating left recursion is-

E → TE’
E’ → +TE’ / ∈
T → FT’
T’ → *FT’ / ∈
F → id

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
Left Factoring
• Left factoring is a process by which the grammar with common
prefixes is transformed to make it useful for Top down parsers.
• In left factoring,
• We make one production for each common prefixes.
• The common prefix may be a terminal or a non-terminal or a
combination of both.
• Rest of the derivation is added by new productions.

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
Do left factoring in the following grammar-
S → iEtS / iEtSeS / a
E → b


Solution-
 
The left factored grammar is-
S → iEtSS’ / a
S’ → eS / ∈
E → b
 


Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Do left factoring in the following grammar-
A → aAB / aBc / aAc

 
Solution-
 
Step-01:
 
A → aA’
A’ → AB / Bc / Ac
Again, this is a grammar with common prefixes.
 
Step-02:
 
A → aA’
A’ → AD / Bc

D → B / c
This is a left factored grammar.
 


Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Do left factoring in the following grammar-
S → aSSbS / aSaSb / abb / b
 
Solution-
 
Step-01:
 
S → aS’ / b
S’ → SSbS / SaSb / bb
Again, this is a grammar with common prefixes.
 
Step-02:
 
S → aS’ / b
S’ → SA / bb
A → SbS / aSb

This is a left factored grammar.
 


Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Algorithm

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
TOP DOWN PARSER
Types of Parser

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
TDP without backtracking
• Grammar should not have left recursion
• Grammar should not be non deterministic-left factoring

Note: Only operator Precedence parser supports ambiguous grammar

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Example
Top Down parser is left most derivation.
Bottom up parser is reverse of right most
derivation.

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
LL(1) Parser-left to right, LMD

Before constructing parsing

table we should know two
functions.
i)FIRST()
ii)FOLLOW()

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
FIRST()-If we have variable and string, from that variable if we derive all the string
which terminal is coming in the beginning is known as first.

S →ABCD
A → b/ ∈ FIRST(S)={b, c,∈}
FIRST(A)={b, ∈}
B→c FIRST(B)={c}
FIRST(C)={d}
C→d FIRST(D)={e}
D→e

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Example for first()

S → aBDh
B → cC
C → bC / ∈
D → EF
E→g/∈
F→f/∈

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Example for first()

S → aBDh
B → cC •First(S) = { a }
•First(B) = { c }
C → bC / ∈ •First(C) = { b , ∈ }
D → EF •First(D) = { First(E) – ∈ } ∪ First(F) = { g , f , ∈ }
•First(E) = { g , ∈ }
E→g/∈ •First(F) = { f , ∈ }
F→f/∈

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
FOLLOW()-What is the terminal which can follow a variable in derivation process.

S → ABCD
A → b/ ∈
B→c
C→d
D→e

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
FOLLOW()-What is the terminal which can follow a variable in derivation process.

FIRST(S)={b, c,∈}
S → ABCD FIRST(A)={b, ∈}
FOLLOW(S)={$}
A → b/ ∈ FIRST(B)={c}
FOLLOW(A)={c}
FIRST(C)={d}
FOLLOW(B)={d}
B→c FIRST(D)={e}
FOLLOW(C)={e}
C→d FOLLOW(D)={$}

D→e

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Example for Follow()
Follow(S) = { $ }
Follow(B) = { First(D) – ∈ } ∪ First(h) = { g , f , h }
Follow(C) = Follow(B) = { g , f , h }
S → aBDh Follow(D) = { h }
Follow(E) = { First(F) – ∈ } ∪ Follow(D) = { f,h }
B → cC Follow(F) = Follow(D) = { h }

C → bC / ∈
D → EF •First(S) = { a }
•First(B) = { c }
E→g/∈ •First(C) = { b , ∈ }
•First(D) = { First(E) – ∈ } ∪ First(F) = { g , f , ∈ }
F→f/∈
•First(E) = { g , ∈ }
•First(F) = { f , ∈ }

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
 1. Calculate the first and follow functions for the given grammar-
 
S → A
A → aB / Ad
B → b First Functions-
C → g  
•First(S) = First(A) = { a }
After eliminating left recursion, we get the following •First(A) = { a }
grammar- •First(A’) = { d , ∈ }
  •First(B) = { b }
S → A •First(C) = { g }
A → aBA’  
A’ → dA’ / ∈ Follow Functions-
B → b  
C → g •Follow(S) = { $ }
•Follow(A) = Follow(S) = { $ }
•Follow(A’) = Follow(A) = { $ }
A → Aα / β •Follow(B) = { First(A’) – ∈ } ∪ Follow(A) = { d ,
A → βA’ $}
A’ → αA’ / ∈ •Follow(C) = NA
 
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
2. Calculate the first and follow functions for the given grammar
 
S → (L) / a
L → SL’
L’ → ,SL’ / ∈

FOLLOW(S)={$,,,)}
First Functions- FOLLOW(L)={)}
 
•First(S) = { ( , a }
•First(L) = First(S) = { ( , a }
•First(L’) = { , , ∈ }
 
Follow Functions-
 
•Follow(S) = { $ } ∪ { First(L’) – ∈ } ∪ Follow(L) ∪ Follow(L’) = { $ , , , ) }
•Follow(L) = { ) }
•Follow(L’) = Follow(L) = { ) }

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
3. Calculate the first and follow functions for the given grammar-
 
S → AaAb / BbBa

A→∈
B→∈
 
First Functions-
 
•First(S) = { First(A) – ∈ } ∪ First(a) ∪ { First(B) – ∈ } ∪ First(b) = { a
,b}
•First(A) = { ∈ }
•First(B) = { ∈ }
 
Follow Functions-
 
•Follow(S) = { $ }
•Follow(A) = { a , b }
•Follow(B) = { a , b }
 

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
4.Calculate the first and follow functions for the given
grammar-
  First Functions-
E→E+T/T  
T→T*F/F •First(E) = First(T) = First(F) = { ( , id }
F → (E) / id •First(E’) = { + , ∈ }
After eliminating left recursion, we get the following •First(T) = First(F) = { ( , id }
grammar- •First(T’) = { *, ∈ }
  •First(F) = { ( , id }
E → TE’
E’ → + TE’ / ∈
T → FT’
T’ → *FT’ / ∈ Follow Functions-
F → (E) / id  
•Follow(E) = { $ , ) }
•Follow(E’) = Follow(E) = { $ , ) }
•Follow(T) = { First(E’) – ∈ } ∪ Follow(E) ∪ Follow(E’) = { + , $ , )
}
•Follow(T’) = Follow(T) = { + , $ , ) }
•Follow(F) = { First(T’) – ∈ } ∪ Follow(T) ∪ Follow(T’) = { * , + , $
,)}

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Construction of LL(I) Parsing table
1.Construct LL(1) parsing table for the given grammar.
E → E + T / T

T → T * F / F

F → (E) / id

After eliminating left recursion, we get the following grammar-
 E → TE’
E’ → + TE’ / ∈
T → FT’
T’ → *FT’ / ∈
F → (E) / id
First Functions- Follow Functions-
   
•First(E) = First(T) = First(F) = { ( , id } •Follow(E) = { $ , ) }
•First(E’) = { + , ∈ } •Follow(E’) = Follow(E) = { $ , ) }
•First(T) = First(F) = { ( , id } •Follow(T) = { First(E’) – ∈ } ∪ Follow(E) ∪ Follow(E’) = { + , $ , )
•First(T’) = { *, ∈ } }
•First(F) = { ( , id } •Follow(T’) = Follow(T) = { + , $ , ) }
•Follow(F) = { First(T’) – ∈ } ∪ Follow(T) ∪ Follow(T’) = { * , + , $
,)}
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
 FIRST FOLLOW

E –> TE’ { id, ( } { $, ) }

E’ –>
{ +, ∈ } { $, ) }
+TE’/∈
T –> FT’ { id, ( } { +, $, ) }
T’ –>
{ *, ∈ } { +, $, ) }
*FT’/∈
F –> { *, +, $, )
{ id, ( }
id/(E) }

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
2. Construct LL(1) parsing table for the given grammar.

S->A|a
A->a FIRST FOLLOW

S –> A/a {a} {$}

A –>a {a} {$}

This grammar is not LL(1)

a $

S –> A, S –>
S
a
A A –>a

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
3. Check the given grammar is LL(I) or not.

1. S->aSbS/bSaS/ ∈


a

 b $
This is not LL(1) grammar
S –> bSaS
S –> aSbS
S S->∈
S-> ∈
S->∈

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Check the given grammar is LL(I) or not
2.S->aABb
A->c/ ∈
B->d/ ∈ a b c d
S

 A
B



Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Non-Recursive Predictive parsing
Types of Parser

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Non Recursive Predictive Parsing LL(1)

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
1.Construct LL(1) parsing table for the given grammar. Parse the given string id+id*id for the
grammar
E → E + T / T

T → T * F / F

F → (E) / id

After eliminating left recursion, we get the following grammar-
 E → TE’
E’ → + TE’ / ∈
T → FT’
T’ → *FT’ / ∈
F → (E) / id
First Functions- Follow Functions-
   
•First(E) = First(T) = First(F) = { ( , id } •Follow(E) = { $ , ) }
•First(E’) = { + , ∈ } •Follow(E’) = Follow(E) = { $ , ) }
•First(T) = First(F) = { ( , id } •Follow(T) = { First(E’) – ∈ } ∪ Follow(E) ∪ Follow(E’) = { + , $ , )
•First(T’) = { *, ∈ } }
•First(F) = { ( , id } •Follow(T’) = Follow(T) = { + , $ , ) }
•Follow(F) = { First(T’) – ∈ } ∪ Follow(T) ∪ Follow(T’) = { * , + , $
,)}
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
 Matched Stack Input Action
E$ id+id*id$
TE’$ id+id*id$ Replace E->TE’
FT’E’$ id+id*id$ Replace T->FT’
idT’E’$ id+id*id$ Replace F->id
id T’E’$ +id*id$ Matched id
id E’$ +id*id$ Replace T’->ε
id +TE’$ +id*id$ Replace E’->+TE’
Id+ TE’$ id*id$ Matched +
Id+ FT’E’$ id*id$ Replace T->FT’
Id + idT’E’$ Id*id$ Replace F->id
Id+id T’E’$ *id$ Matched id
Id+id *FT’E’$ *id$ Replace T’->*FT’
Id+id* FT’E’$ Id$ Matched *
Id+id* idT’E’$ Id$ Replace F->id
Id+id*id T’E’$ $ Matched id
Mrs Snitha Shetty, Asst. Professor,
Id+id*id E’$Dept. of CSE, AJIET, $ Replace T’->ε
Mangaluru
The given string is id+id*id

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
What is error recovery?
• Consider a string )id*+id
• How to parse the string?

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Error Recovery in Parsing table
• There are two types of error recovery mechanism. They are

i)Panic mode error recovery

ii)Phrase Level error recovery

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Panic mode error recovery
There are 3 possibilities
1)Pop non-terminal from the stack
2)Remove or discard the terminal from input
3)Introduce the non-terminal by which the terminal can be produced.

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Synchronizing tokens added to the parsing table

FIRST FOLLOW

E –> TE’ { id, ( } { $, ) }

E’ –>
{ +, ∈ } { $, ) }
+TE’/∈
T –> FT’ { id, ( } { +, $, ) }
T’ –>
{ *, ∈ } { +, $, ) }
*FT’/∈
F –> { *, +, $, )
{ id, ( }
id/(E) }

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Synchronizing tokens added to the parsing table

FIRST FOLLOW

E –> TE’ { id, ( } { $, ) }

E’ –>
{ +, ∈ } { $, ) }
+TE’/∈
T –> FT’ { id, ( } { +, $, ) }
T’ –>
{ *, ∈ } { +, $, ) }
*FT’/∈
F –> { *, +, $, )
{ id, ( }
id/(E) }

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
 Parse the given string using same grammar )id*+id
Stack Input
E$ )id*+id$
E$ id*+id$
TE’$ Id*+id$
FT’E’$ Id*+id$
idT’E’$ Id*+id$
T’E’$ *+id$
*FT’E’$ *+id$
FT’E’$ +id$
T’E’$ +id$
E’$ +id$
+TE’$ +id$
TE’$ Id$
FT’E’$ Id$
idT’E’$ Id$
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
T’E’$ $ Mangaluru
Parse the given string using same grammar )id*+id

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Phrase Level Error Recovery

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Recursive Descent Parser
Recursive Descent Parser
For every variable in a given grammar we are writing function .
E->iE’
E’->+iE’|ε

E() E’() match(char t)

{ main()
{ {
if(l==‘+’) {
If(l==t)
If(l==‘i’) { E()
l=getchar();
{ match(‘+’); If(l==‘$’)
else
match(‘i’); printf(“Parsing Success”);
match(‘i’); printf(“error”);
E’(); }
E’(); }
}
} else
} return; i+i$
}
Bottom Up Parsing
Types of Parser

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Introduction to bottom up parser
• A bottom up corresponds to the construction of parse tree for an input string beginning at the
leaves(Bottom) and working up towards the root node(the top).

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Reduction

E
T
T*F
T*id
F*id
id*id
Reverse of RMD
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
Handle Pruning

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
Shift Reduce Parsing
• Shift Reduce parsing is a process of reducing a string to the start
symbol of the grammar.
• It uses stack to hold the grammar and input to hold the string.
• A shift reduce parsing performs two action
i)Shift- A current symbol in the input string is pushed to the stack
ii)Reduce- At each reduction , the symbol will be replaced by
non-terminals.
Stack F
Input *id

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
For the given grammar show shift reduce parsing using the input string id1*id2.

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
4 Possible option in Shift Reduce parser

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
1.Consider the following grammar-
E→E–E
E→E*E
E → id
Parse the input string id – id * id using a shift-reduce parser.

Stack Input Buffer Parsing Action

$ id – id * id $ Shift
$ id – id * id $ Reduce E → id
$E – id * id $ Shift
$E– id * id $ Shift
$ E – id * id $ Reduce E → id
$E–E * id $ Shift
$E–E* id $ Shift
$ E – E * id $ Reduce E → id
$E–E*E $ Reduce E → E * E
$E–E $ Reduce E → E – E
$E $ Accept
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
2. Consider the following grammar. Parse the input string ( a , ( a , a ) ) using a shift-reduce parser.
S→(L)|a
L→L,S|S Stack Input Buffer Parsing Action
$ (a,(a,a))$ Shift
$( a,(a,a))$ Shift
$(a ,(a,a))$ Reduce S → a
$(S ,(a,a))$ Reduce L → S
$(L ,(a,a))$ Shift
$(L, (a,a))$ Shift
$(L,( a,a))$ Shift
$(L,(a ,a))$ Reduce S → a
$(L,(S ,a))$ Reduce L → S
$(L,(L ,a))$ Shift
$(L,(L, a))$ Shift
$(L,(L,a ))$ Reduce S → a
$(L,(L,S ))$ Reduce L → L , S
$(L,(L ))$ Shift
$(L,(L) )$ Reduce S → (L)
$(L,S )$ Reduce L → L , S
$(L )$ Shift
$(L) $ Reduce S → (L)
$S $ Accept
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
Mangaluru
3.Considering the string “10201”, design a shift-reduce parser for the following grammar.
S → 0S0 | 1S1 | 2
Stack Input Buffer Parsing Action

$ 10201$ Shift
$1 0201$ Shift
$10 201$ Shift
$102 01$ Reduce S → 2
$10S 01$ Shift
$10S0 1$ Reduce S → 0 S 0
$1S 1$ Shift
$1S1 $ Reduce S → 1 S 1
$S $ Accept

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
4.Consider the following grammar-
S → T L;
T → int | float
L → L , id | id
Parse the input string int id , id ; using a shift-reduce parser.

Stack Input Buffer Parsing Action

$ int id , id ; $ Shift
$ int id , id ; $ Reduce T → int
$T id , id ; $ Shift
$ T id , id ; $ Reduce L → id
$TL , id ; $ Shift
$TL, id ; $ Shift
Reduce L → L ,
$ T L , id ;$
id
$TL ;$ Shift
Reduce S → T
$TL; $
L;
$S Mrs Snitha
$ Shetty, Asst. Professor, Dept. ofAccept
CSE, AJIET,
Mangaluru
Introduction to LR(0) Parser and SLR(1) Parser
Types of Parser

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
Introduction to LR Parser

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
LR Parser

In order to construct LR(0) parser canonical collection of LR(0) items will be used.

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
LR Parser
• Here we are using two function
1) Closure
2) GOTO

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
LR(0) Parser-Items, Closure and GOTO
Consider a grammar
S->AA
A->aA |b

• Add new production to form augmented grammar.

S’->S
S->AA
A->aA |b

• Any production dot in Right Hand Side is known as item.

Eg:- S->.AA
S->A.A
S->AA.
Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,
Mangaluru
Closure and GOTO
S’->S
S->AA
A->aA |b
• Take LR(0) item for first production
S’->.S
Now apply closure- when there is dot in the LHS of the variable, add all the production of the
variable with dot in the beginning.
S’->.S
S->.AA
A->.aA |.b
GOTO- Generate another state by moving the dot to the RHS.
• In new state apply closure once again.
• Repeat until we get final item(dot in RHS).
Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,
Mangaluru
GOTO and Closure

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
GOTO and Closure- Canonical collection of LR(0) items.

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
Name the states
canonical collection of LR(0) items

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
Construct LR(0) parsing table
• It has two parts.
i)GOTO
ii)Action
• Number of rows is equal to number of states.
• Whenever there is a transition for variable write the new state number under
GOTO part.
• Whenever there is a transition for terminal write the new state number under
ACTION part with suffix S(shift).
• When the state contains final item and the production is augmented grammar
then it is known as accept state.
• If any state contains final item other than augmented grammar then in that
particular row write reduce completely with the production number.

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
Construction of LR(0) parsing table
S’->S
1. S->AA
2. A->aA
3. A->b

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
Construction of LR(0) parsing table
S’->S
1. S->AA
2. A->aA
3. A->b

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
Parse for the input aabb$

Stack Symbol Input Action

0 aabb$ Shift S3
03 a abb$ Shift S3
033 aa bb$ Shift S4
033 aab b$ r3 A->b
03 aaA b$ r2 A->aA
0 aA b$ R2 A->aA
02 A b$ Shift S4
02 Ab $ R3 A->b
0 AA $ R1 S->AA
01 S $ Accept

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
Parse for the input aabb$

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
SLR(1)
• Almost same as LR(0). The difference is reduce item is not placed in
entire row.
• It is placed in follow of LHS variable

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
SLR(1) Parsing table

Mrs Snitha Shetty, Assistant Professor, Dept. of CSE, AJIET,

Mangaluru
LR(0) and SLR(1) Parser Example Problem
Construct LR(0) or SLR(1) parsing table for the given grammar and parse the input string id*id+id
E->E+T | T
T->T*F | F
F->(E)
F->id

Solution:
E’->E
• Generate the Augmented grammar 1 E->E+T
• Generate the LR(0) items 2 E->T
3 T->T*F
• Apply Closure and goto 4 T-> F
5 F->(E)
6 F->id

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
E’->E
E->E+T
E->T
T->T*F
T-> F
F->(E)
F->id
Canonical representation of LR(0) items are

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
LR(0) Parsing table

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
SLR(1) Parsing table

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru
 Parsing the input string id*id+id
1. E->E+T
2. E->T
3. T->T*F
4. T-> F
5. F->(E)
6. F->id

Stack symbol Input action

0 Id*id+id$ Shift s5
0 id *id+id$ R6 F->id
0 F *id+id$ R4 T->F
02 T *id+id$ Shift s7
027 T* id+id$ Shift s5
027 T*id +id$ R6 F->id
0 T*F +id$ R3 T->T*F
0 T +id$ R2 E->T
01 E +id$ Shift s6
016 E+ Id$ Shift s5
016 E+id $ R6 F->id
Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,
016 E+F $ R4 T->F Mangaluru
Parsing the input string id*id+id
1. E->E+T
2. E->T
3. T->T*F
4. T-> F
5. F->(E)
6. F->id

Mrs Snitha Shetty, Asst. Professor, Dept. of CSE, AJIET,

Mangaluru