Lecture 12
Syntax Analysis
Awanish Pandey
Department of Computer Science and Engineering
Indian Institute of Technology
Roorkee
February 14, 2025
February 14, 2025 1 / 14
Take aways from the last class
Applying symbols to state
February 14, 2025 2 / 14
Take aways from the last class
Applying symbols to state
Goto Operations
February 14, 2025 2 / 14
Take aways from the last class
Applying symbols to state
Goto Operations
Sets of Item
February 14, 2025 2 / 14
Take aways from the last class
Applying symbols to state
Goto Operations
Sets of Item
Limitations of SLR Parser
February 14, 2025 2 / 14
Take aways from the last class
Applying symbols to state
Goto Operations
Sets of Item
Limitations of SLR Parser
Closure operation on LR(1)
February 14, 2025 2 / 14
Example
Consider the following grammar
S′ → S
S → CC
C → cC |d
Compute closure(I) where I = [S ′ → .S, $]
S → .S, $
S → .CC , $
C → .cC , c
C → .cC , d
C → .d, c
C → .d, d
February 14, 2025 3 / 14
Example
Construct sets of LR(1) items for the grammar on previous slide
I3 : goto(I0 , c)
I0 : S → .S, $ C → c.C , c/d
S → .CC , $ C → .cC , c/d
C → .cC , c/d C → .d, c/d I7 : goto(I2 , d)
C → .d, c/d I4 : goto(I0 , d) C → d.,$
I1 : goto(I0 , S) C → d., c/d I8 : goto(I3 , C )
S ′ → S.,$ I5 : goto(I2 , C ) C → cC .,c/d
I2 : goto(I0 , C ) S → CC .,$ I9 : goto(I6 , C )
S → C .C ,$ I6 : goto(I2 , c) C → cC .,$
C → .cC ,$ C → c.C ,$
C → .d,$ C → .cC ,$
C → .d,$
February 14, 2025 4 / 14
Construction of Canonical LR parse table
Construct C = I0 , · · · , In the sets of LR(1) items
February 14, 2025 5 / 14
Construction of Canonical LR parse table
Construct C = I0 , · · · , In the sets of LR(1) items
If [A → α.aβ, b] is in Ii and goto(Ii , a) = Ij then action[i,a]=shift j
February 14, 2025 5 / 14
Construction of Canonical LR parse table
Construct C = I0 , · · · , In the sets of LR(1) items
If [A → α.aβ, b] is in Ii and goto(Ii , a) = Ij then action[i,a]=shift j
If [A → α., a] is in Ii then action[i,a] reduce A → α
February 14, 2025 5 / 14
Construction of Canonical LR parse table
Construct C = I0 , · · · , In the sets of LR(1) items
If [A → α.aβ, b] is in Ii and goto(Ii , a) = Ij then action[i,a]=shift j
If [A → α., a] is in Ii then action[i,a] reduce A → α
If [S ′ → S., $] is in Ii then action[i,$] = accept
February 14, 2025 5 / 14
Construction of Canonical LR parse table
Construct C = I0 , · · · , In the sets of LR(1) items
If [A → α.aβ, b] is in Ii and goto(Ii , a) = Ij then action[i,a]=shift j
If [A → α., a] is in Ii then action[i,a] reduce A → α
If [S ′ → S., $] is in Ii then action[i,$] = accept
If goto(Ii , A) = Ij then goto[i,A] = j for all non terminals A
February 14, 2025 5 / 14
February 14, 2025 6 / 14
LALR Parse Table
Look Ahead LR parsers
February 14, 2025 7 / 14
LALR Parse Table
Look Ahead LR parsers
Consider a pair of similar looking states (same kernel and different lookaheads) in the set
of LR(1) items
February 14, 2025 7 / 14
LALR Parse Table
Look Ahead LR parsers
Consider a pair of similar looking states (same kernel and different lookaheads) in the set
of LR(1) items
I4 : C → d., c/d
I7 : C → d., $
February 14, 2025 7 / 14
LALR Parse Table
Look Ahead LR parsers
Consider a pair of similar looking states (same kernel and different lookaheads) in the set
of LR(1) items
I4 : C → d., c/d
I7 : C → d., $
Replace I4 and I7 by a new state I47 consisting of (C → d., c/d/$)
February 14, 2025 7 / 14
LALR Parse Table
Look Ahead LR parsers
Consider a pair of similar looking states (same kernel and different lookaheads) in the set
of LR(1) items
I4 : C → d., c/d
I7 : C → d., $
Replace I4 and I7 by a new state I47 consisting of (C → d., c/d/$)
Similarly I3 & I6 and I8 & I9 form pairs
February 14, 2025 7 / 14
LALR Parse Table
Look Ahead LR parsers
Consider a pair of similar looking states (same kernel and different lookaheads) in the set
of LR(1) items
I4 : C → d., c/d
I7 : C → d., $
Replace I4 and I7 by a new state I47 consisting of (C → d., c/d/$)
Similarly I3 & I6 and I8 & I9 form pairs
Merge LR(1) items having the same core
February 14, 2025 7 / 14
Construct LALR parse table
Construct C = I0 , · · · , In set of LR(1) items
February 14, 2025 8 / 14
Construct LALR parse table
Construct C = I0 , · · · , In set of LR(1) items
For each core present in LR(1) items find all sets having the same core and replace these
sets by their union
February 14, 2025 8 / 14
Construct LALR parse table
Construct C = I0 , · · · , In set of LR(1) items
For each core present in LR(1) items find all sets having the same core and replace these
sets by their union
Let C ′ = J0 , · · · , Jm be the resulting set of items
February 14, 2025 8 / 14
Construct LALR parse table
Construct C = I0 , · · · , In set of LR(1) items
For each core present in LR(1) items find all sets having the same core and replace these
sets by their union
Let C ′ = J0 , · · · , Jm be the resulting set of items
Construct action table as was done earlier
February 14, 2025 8 / 14
Construct LALR parse table
Construct C = I0 , · · · , In set of LR(1) items
For each core present in LR(1) items find all sets having the same core and replace these
sets by their union
Let C ′ = J0 , · · · , Jm be the resulting set of items
Construct action table as was done earlier
Let J = I1 ∪ I2 · · · ∪ Ik
since I1 , I2 · · · , Ik have same core, goto(J, X ) will have the same core
Let K = goto(I1 , X ) ∪ goto(I 2, X ) · · · goto(Ik , X ) the goto(J, X ) = K
February 14, 2025 8 / 14
February 14, 2025 9 / 14
Important points
SLR and LALR parse tables have same number of states.
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
New conflicts can not be of shift reduce kind:
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
New conflicts can not be of shift reduce kind:
▶ Assume there is a shift reduce conflict in some state of LALR parser with items
[X → α., a], [Y → γ.aβ, b]
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
New conflicts can not be of shift reduce kind:
▶ Assume there is a shift reduce conflict in some state of LALR parser with items
[X → α., a], [Y → γ.aβ, b]
▶ Then there must have been a state in the LR parser with the same core
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
New conflicts can not be of shift reduce kind:
▶ Assume there is a shift reduce conflict in some state of LALR parser with items
[X → α., a], [Y → γ.aβ, b]
▶ Then there must have been a state in the LR parser with the same core
▶ Contradiction; because LR parser did not have conflicts
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
New conflicts can not be of shift reduce kind:
▶ Assume there is a shift reduce conflict in some state of LALR parser with items
[X → α., a], [Y → γ.aβ, b]
▶ Then there must have been a state in the LR parser with the same core
▶ Contradiction; because LR parser did not have conflicts
LALR parser can have new reduce-reduce conflicts
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
New conflicts can not be of shift reduce kind:
▶ Assume there is a shift reduce conflict in some state of LALR parser with items
[X → α., a], [Y → γ.aβ, b]
▶ Then there must have been a state in the LR parser with the same core
▶ Contradiction; because LR parser did not have conflicts
LALR parser can have new reduce-reduce conflicts
▶ Assume states [X → α., a], [Y → α., b]and[X → α., b], [Y → α., a]
February 14, 2025 10 / 14
Important points
SLR and LALR parse tables have same number of states.
Merging items never produces shift/reduce conflicts but may produce reduce/reduce
conflicts.
New conflicts can not be of shift reduce kind:
▶ Assume there is a shift reduce conflict in some state of LALR parser with items
[X → α., a], [Y → γ.aβ, b]
▶ Then there must have been a state in the LR parser with the same core
▶ Contradiction; because LR parser did not have conflicts
LALR parser can have new reduce-reduce conflicts
▶ Assume states [X → α., a], [Y → α., b]and[X → α., b], [Y → α., a]
▶ Merging the two states produces [X → α., a/b], [Y → α., a/b]
February 14, 2025 10 / 14
Important points
Practical LALR parsers are not built by first making canonical LR parse tables
February 14, 2025 11 / 14
Important points
Practical LALR parsers are not built by first making canonical LR parse tables
There are direct, complicated but efficient algorithms to develop LALR parsers
February 14, 2025 11 / 14
Important points
Practical LALR parsers are not built by first making canonical LR parse tables
There are direct, complicated but efficient algorithms to develop LALR parsers
Relative power of various classes
February 14, 2025 11 / 14
Important points
Practical LALR parsers are not built by first making canonical LR parse tables
There are direct, complicated but efficient algorithms to develop LALR parsers
Relative power of various classes
▶ SLR(1) ≤ LALR(1) ≤ LR(1)
February 14, 2025 11 / 14
Important points
Practical LALR parsers are not built by first making canonical LR parse tables
There are direct, complicated but efficient algorithms to develop LALR parsers
Relative power of various classes
▶ SLR(1) ≤ LALR(1) ≤ LR(1)
▶ SLR(k) ≤ LALR(k) ≤ LR(k)
February 14, 2025 11 / 14
Important points
Practical LALR parsers are not built by first making canonical LR parse tables
There are direct, complicated but efficient algorithms to develop LALR parsers
Relative power of various classes
▶ SLR(1) ≤ LALR(1) ≤ LR(1)
▶ SLR(k) ≤ LALR(k) ≤ LR(k)
▶ LL(k) ≤ LR(k)
February 14, 2025 11 / 14
Error Recovery
An error is detected when an entry in the action table is found to be empty.
February 14, 2025 12 / 14
Error Recovery
An error is detected when an entry in the action table is found to be empty.
Panic mode error recovery can be implemented as follows:
February 14, 2025 12 / 14
Error Recovery
An error is detected when an entry in the action table is found to be empty.
Panic mode error recovery can be implemented as follows:
▶ scan down the stack until a state S with a goto on a particular nonterminal A is found.
February 14, 2025 12 / 14
Error Recovery
An error is detected when an entry in the action table is found to be empty.
Panic mode error recovery can be implemented as follows:
▶ scan down the stack until a state S with a goto on a particular nonterminal A is found.
▶ Discard zero or more input symbols until a symbol a is found that can legitimately follow (A).
February 14, 2025 12 / 14
Error Recovery
An error is detected when an entry in the action table is found to be empty.
Panic mode error recovery can be implemented as follows:
▶ scan down the stack until a state S with a goto on a particular nonterminal A is found.
▶ Discard zero or more input symbols until a symbol a is found that can legitimately follow (A).
▶ stack the state goto[S, A] and resume parsing.
February 14, 2025 12 / 14
Error Recovery
An error is detected when an entry in the action table is found to be empty.
Panic mode error recovery can be implemented as follows:
▶ scan down the stack until a state S with a goto on a particular nonterminal A is found.
▶ Discard zero or more input symbols until a symbol a is found that can legitimately follow (A).
▶ stack the state goto[S, A] and resume parsing.
Choice of A: Normally these are non terminals representing major program pieces such as
an expression, statement or a block. For example if A is the nonterminal stmt, a might be
semicolon or end
February 14, 2025 12 / 14
Parser Generator
Some common LR parser generators
▶ YACC: Yet Another Compiler Compiler
▶ Bison: GNU Software
Yacc/Bison source program specification (accept LALR grammars)
declaration
%%
translation rules
%%
supporting C routines
February 14, 2025 13 / 14
February 14, 2025 14 / 14
