Lecture 11

Syntax Analysis

Awanish Pandey

Department of Computer Science and Engineering

Indian Institute of Technology
Roorkee

February 12, 2025

February 12, 2025 1 / 12

Take aways from the last class

Parser State

February 12, 2025 2 / 12

Take aways from the last class

Parser State
Agumentation of the Grammar

February 12, 2025 2 / 12

Take aways from the last class

Parser State
Agumentation of the Grammar
LR(0) items

February 12, 2025 2 / 12

Take aways from the last class

Parser State
Agumentation of the Grammar
LR(0) items
Start State

February 12, 2025 2 / 12

Take aways from the last class

Parser State
Agumentation of the Grammar
LR(0) items
Start State
Closure

February 12, 2025 2 / 12

Take aways from the last class

Parser State
Agumentation of the Grammar
LR(0) items
Start State
Closure
Action

February 12, 2025 2 / 12

Take aways from the last class

Parser State
Agumentation of the Grammar
LR(0) items
Start State
Closure
Action
Goto

February 12, 2025 2 / 12

Take aways from the last class

Parser State
Agumentation of the Grammar
LR(0) items
Start State
Closure
Action
Goto
Parse Table creation

February 12, 2025 2 / 12

Applying symbols in a state

February 12, 2025 3 / 12

Applying symbols in a state

Create new state and include all the items that have appropriate input symbol just after
the ”.”

February 12, 2025 3 / 12

Applying symbols in a state

Create new state and include all the items that have appropriate input symbol just after
the ”.”
Advance ”.” in those items and take closure

February 12, 2025 3 / 12

Goto operation

February 12, 2025 4 / 12

Goto operation

Goto(I , X ) , where I is a set of items and X is a grammar symbol

February 12, 2025 4 / 12

Goto operation

Goto(I , X ) , where I is a set of items and X is a grammar symbol

▶ is closure of set of item A → αX .β

February 12, 2025 4 / 12

Goto operation

Goto(I , X ) , where I is a set of items and X is a grammar symbol

▶ is closure of set of item A → αX .β
▶ such that A → α.X β is in I

February 12, 2025 4 / 12

Goto operation

Goto(I , X ) , where I is a set of items and X is a grammar symbol

▶ is closure of set of item A → αX .β
▶ such that A → α.X β is in I
Intuitively if I is a set of items for some valid prefix α then goto(I , X ) is set of valid items
for prefix αX

February 12, 2025 4 / 12

Goto operation

Goto(I , X ) , where I is a set of items and X is a grammar symbol

▶ is closure of set of item A → αX .β
▶ such that A → α.X β is in I
Intuitively if I is a set of items for some valid prefix α then goto(I , X ) is set of valid items
for prefix αX
If I is E ′ → E .
E → E. + T
then goto(I,+) is
E → E + .T
T → .T ∗ F
T → .F
F → .(E )
F → .id

February 12, 2025 4 / 12

Sets of items

C : Collection of sets of LR(0) items for grammar G ′

C = closure ( S ′ → .S )
repeat
for each set of items I in C
and each grammar symbol X
such that goto (I,X) is not empty and not in C
ADD goto(I,X) to C
until no more additions

February 12, 2025 5 / 12

Construct SLR(Simple LR) parse table

Construct C = I0 , · · · , In the collection of sets of LR(0) items.

February 12, 2025 6 / 12

Construct SLR(Simple LR) parse table

Construct C = I0 , · · · , In the collection of sets of LR(0) items.

If A → α.aβ is in Ii and goto(Ii , a) = Ij then action[i,a] = shift j

February 12, 2025 6 / 12

Construct SLR(Simple LR) parse table

Construct C = I0 , · · · , In the collection of sets of LR(0) items.

If A → α.aβ is in Ii and goto(Ii , a) = Ij then action[i,a] = shift j
If A → α. is in Ii
then action[i,a] = reduce A → α for all a in follow (A)

February 12, 2025 6 / 12

Construct SLR(Simple LR) parse table

Construct C = I0 , · · · , In the collection of sets of LR(0) items.

If A → α.aβ is in Ii and goto(Ii , a) = Ij then action[i,a] = shift j
If A → α. is in Ii
then action[i,a] = reduce A → α for all a in follow (A)
If S ′ → S. is in Ii then action[i,$] = accept

February 12, 2025 6 / 12

Construct SLR(Simple LR) parse table

Construct C = I0 , · · · , In the collection of sets of LR(0) items.

If A → α.aβ is in Ii and goto(Ii , a) = Ij then action[i,a] = shift j
If A → α. is in Ii
then action[i,a] = reduce A → α for all a in follow (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 12, 2025 6 / 12

Construct SLR(Simple LR) parse table

Construct C = I0 , · · · , In the collection of sets of LR(0) items.

If A → α.aβ is in Ii and goto(Ii , a) = Ij then action[i,a] = shift j
If A → α. is in Ii
then action[i,a] = reduce A → α for all a in follow (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
All entries not defined are errors

February 12, 2025 6 / 12

Construct SLR(Simple LR) parse table

Construct C = I0 , · · · , In the collection of sets of LR(0) items.

If A → α.aβ is in Ii and goto(Ii , a) = Ij then action[i,a] = shift j
If A → α. is in Ii
then action[i,a] = reduce A → α for all a in follow (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
All entries not defined are errors
SLR is too weak to handle most languages!

February 12, 2025 6 / 12

Homework

Create SLR Parse table for the following grammar (homework)

S′ → S
S →L=R
S →R
L → ∗R
L → id
R→L

February 12, 2025 7 / 12

Parse Table

February 12, 2025 8 / 12

Problems in SLR parsing

No sentential form of this grammar can start with R = · · ·

February 12, 2025 9 / 12

Problems in SLR parsing

No sentential form of this grammar can start with R = · · ·

However, the reduce action in action[2,=] generates a sentential form starting with R=· · ·

February 12, 2025 9 / 12

Problems in SLR parsing

No sentential form of this grammar can start with R = · · ·

However, the reduce action in action[2,=] generates a sentential form starting with R=· · ·
Therefore, the reduce action is incorrect

February 12, 2025 9 / 12

Problems in SLR parsing

No sentential form of this grammar can start with R = · · ·

However, the reduce action in action[2,=] generates a sentential form starting with R=· · ·
Therefore, the reduce action is incorrect
In SLR parsing method state i calls for reduction on symbol ”a”, by rule A → α if Ii
contains [A → α.] and ”a” is in follow(A)

February 12, 2025 9 / 12

Problems in SLR parsing

No sentential form of this grammar can start with R = · · ·

However, the reduce action in action[2,=] generates a sentential form starting with R=· · ·
Therefore, the reduce action is incorrect
In SLR parsing method state i calls for reduction on symbol ”a”, by rule A → α if Ii
contains [A → α.] and ”a” is in follow(A)
However, when state I appears on the top of the stack, the viable prefix βα on the stack
may be such that βα can not be followed by symbol ”a” in any right sentential form

February 12, 2025 9 / 12

Problems in SLR parsing

No sentential form of this grammar can start with R = · · ·

However, the reduce action in action[2,=] generates a sentential form starting with R=· · ·
Therefore, the reduce action is incorrect
In SLR parsing method state i calls for reduction on symbol ”a”, by rule A → α if Ii
contains [A → α.] and ”a” is in follow(A)
However, when state I appears on the top of the stack, the viable prefix βα on the stack
may be such that βα can not be followed by symbol ”a” in any right sentential form
Thus, the reduction by the rule A → α on symbol ”a” is invalid

February 12, 2025 9 / 12

Problems in SLR parsing

No sentential form of this grammar can start with R = · · ·

However, the reduce action in action[2,=] generates a sentential form starting with R=· · ·
Therefore, the reduce action is incorrect
In SLR parsing method state i calls for reduction on symbol ”a”, by rule A → α if Ii
contains [A → α.] and ”a” is in follow(A)
However, when state I appears on the top of the stack, the viable prefix βα on the stack
may be such that βα can not be followed by symbol ”a” in any right sentential form
Thus, the reduction by the rule A → α on symbol ”a” is invalid
SLR parsers cannot remember the left context

February 12, 2025 9 / 12

Canonical LR Parsing

Carry extra information in the state so that wrong reductions by A → α will be ruled out

February 12, 2025 10 / 12

Canonical LR Parsing

Carry extra information in the state so that wrong reductions by A → α will be ruled out
Redefine LR items to include a terminal symbol as a second component (look ahead
symbol).

February 12, 2025 10 / 12

Canonical LR Parsing

Carry extra information in the state so that wrong reductions by A → α will be ruled out
Redefine LR items to include a terminal symbol as a second component (look ahead
symbol).
The general form of the item becomes [A → α.β, a] which is called LR(1) item.

February 12, 2025 10 / 12

Canonical LR Parsing

Carry extra information in the state so that wrong reductions by A → α will be ruled out
Redefine LR items to include a terminal symbol as a second component (look ahead
symbol).
The general form of the item becomes [A → α.β, a] which is called LR(1) item.
Item [A → α., a] calls for reduction only if next input is a. The set of symbols ”a”s will
be a subset of Follow (A)

February 12, 2025 10 / 12

Closure(I)

repeat
for each item [A → α.Bβ, a] in I
for each production B → γ in G ′
and for each terminal b in First(βa)
add item [B → .γ, b] to I
until no more additions to I

February 12, 2025 11 / 12

Example

Consider the following grammar

S′ → S
S → CC
C → cC |d

February 12, 2025 12 / 12

Example

Consider the following grammar

S′ → S
S → CC
C → cC |d
Compute closure(I) where I = [S ′ → .S, $]
S → .S, $

February 12, 2025 12 / 12

Example

Consider the following grammar

S′ → S
S → CC
C → cC |d
Compute closure(I) where I = [S ′ → .S, $]
S → .S, $
S → .CC , $

February 12, 2025 12 / 12

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

February 12, 2025 12 / 12

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

February 12, 2025 12 / 12

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

February 12, 2025 12 / 12

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 12, 2025 12 / 12