Lecture 8

Syntax Analysis

Awanish Pandey

Department of Computer Science and Engineering

Indian Institute of Technology
Roorkee

February 5, 2025

February 5, 2025 1 / 13
Take aways from the last class

Predictive Parser

February 5, 2025 2 / 13
Take aways from the last class

Predictive Parser
Parsing algorithm

February 5, 2025 2 / 13
Take aways from the last class

Predictive Parser
Parsing algorithm
Computing first for grammar symbols.

February 5, 2025 2 / 13
Compute follow sets

February 5, 2025 3 / 13
Compute follow sets

Place $ in follow (S)

February 5, 2025 3 / 13
Compute follow sets

Place $ in follow (S)

If there is a production A → αBβ then everything in first(β) (except ϵ) is in follow (B)

February 5, 2025 3 / 13
Compute follow sets

Place $ in follow (S)

If there is a production A → αBβ then everything in first(β) (except ϵ) is in follow (B)
If there is a production A → αB then everything in follow (A) is in follow (B)

February 5, 2025 3 / 13
Compute follow sets

Place $ in follow (S)

If there is a production A → αBβ then everything in first(β) (except ϵ) is in follow (B)
If there is a production A → αB then everything in follow (A) is in follow (B)
If there is a production A → αBβ and First(β) contains ϵ then everything in follow (A) is
in follow (B)

February 5, 2025 3 / 13
Example

For the expression grammar

E → TE ′
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id

February 5, 2025 4 / 13
Example

For the expression grammar

E → TE ′
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
follow (E ) = follow (E ′ ) = $, )

February 5, 2025 4 / 13
Example

For the expression grammar

E → TE ′
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
follow (E ) = follow (E ′ ) = $, )
follow (T ) = follow (T ′ ) = $, ), +

February 5, 2025 4 / 13
Example

For the expression grammar

E → TE ′
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
follow (E ) = follow (E ′ ) = $, )
follow (T ) = follow (T ′ ) = $, ), +
follow (F ) = $, ), +, ∗

February 5, 2025 4 / 13
Example

For the expression grammar

E → TE ′
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
follow (E ) = follow (E ′ ) = $, )
follow (T ) = follow (T ′ ) = $, ), +
follow (F ) = $, ), +, ∗

February 5, 2025 4 / 13
Construction of parse table

February 5, 2025 5 / 13
Construction of parse table

for each production A → α do

February 5, 2025 5 / 13
Construction of parse table

for each production A → α do

▶ for each terminal ‘a’ in first(α)
M[A, a] = A → α

February 5, 2025 5 / 13
Construction of parse table

for each production A → α do

▶ for each terminal ‘a’ in first(α)
M[A, a] = A → α
▶ If ϵ is in First(α)
M[A, b] = A → α
for each terminal b in follow (A)

February 5, 2025 5 / 13
Construction of parse table

for each production A → α do

▶ for each terminal ‘a’ in first(α)
M[A, a] = A → α
▶ If ϵ is in First(α)
M[A, b] = A → α
for each terminal b in follow (A)
▶ If ϵ is in First(a) and $ is in follow (A)
M[A, $] = A → α

February 5, 2025 5 / 13
Construction of parse table

for each production A → α do

▶ for each terminal ‘a’ in first(α)
M[A, a] = A → α
▶ If ϵ is in First(α)
M[A, b] = A → α
for each terminal b in follow (A)
▶ If ϵ is in First(a) and $ is in follow (A)
M[A, $] = A → α
A grammar whose parse table has no multiple entries is called LL(1)

February 5, 2025 5 / 13
Error handling

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly
Every reasonable compiler must recover from errors and identify as many errors as possible

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly
Every reasonable compiler must recover from errors and identify as many errors as possible
However, multiple error messages due to a single fault must be avoided

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly
Every reasonable compiler must recover from errors and identify as many errors as possible
However, multiple error messages due to a single fault must be avoided
Error recovery methods

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly
Every reasonable compiler must recover from errors and identify as many errors as possible
However, multiple error messages due to a single fault must be avoided
Error recovery methods
▶ Panic model

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly
Every reasonable compiler must recover from errors and identify as many errors as possible
However, multiple error messages due to a single fault must be avoided
Error recovery methods
▶ Panic model
▶ Phase level recovery

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly
Every reasonable compiler must recover from errors and identify as many errors as possible
However, multiple error messages due to a single fault must be avoided
Error recovery methods
▶ Panic model
▶ Phase level recovery
▶ Error production

February 5, 2025 6 / 13
Error handling

Stop at the first error and print a message

▶ Compiler writer friendly
▶ But not user friendly
Every reasonable compiler must recover from errors and identify as many errors as possible
However, multiple error messages due to a single fault must be avoided
Error recovery methods
▶ Panic model
▶ Phase level recovery
▶ Error production
▶ Global correction

February 5, 2025 6 / 13
Panic Model

Simplest and the most popular method

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected
▶ Discard tokens one at a time until a set of tokens is found whose role is clear

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected
▶ Discard tokens one at a time until a set of tokens is found whose role is clear
▶ Skip to the next token that can be placed reliably in the parse tree

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected
▶ Discard tokens one at a time until a set of tokens is found whose role is clear
▶ Skip to the next token that can be placed reliably in the parse tree
Consider following code
a = b + c;
x = p r;
h = x < 0;

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected
▶ Discard tokens one at a time until a set of tokens is found whose role is clear
▶ Skip to the next token that can be placed reliably in the parse tree
Consider following code
a = b + c;
x = p r;
h = x < 0;
Panic mode recovery for block skip ahead to next ‘;’ and try to parse the next expression

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected
▶ Discard tokens one at a time until a set of tokens is found whose role is clear
▶ Skip to the next token that can be placed reliably in the parse tree
Consider following code
a = b + c;
x = p r;
h = x < 0;
Panic mode recovery for block skip ahead to next ‘;’ and try to parse the next expression
It discards one expression and tries to continue parsing

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected
▶ Discard tokens one at a time until a set of tokens is found whose role is clear
▶ Skip to the next token that can be placed reliably in the parse tree
Consider following code
a = b + c;
x = p r;
h = x < 0;
Panic mode recovery for block skip ahead to next ‘;’ and try to parse the next expression
It discards one expression and tries to continue parsing
May fail if no further ‘;’ is found

February 5, 2025 7 / 13
Panic Model

Simplest and the most popular method

Most tools provide for specifying panic mode recovery in the grammar
When an error is detected
▶ Discard tokens one at a time until a set of tokens is found whose role is clear
▶ Skip to the next token that can be placed reliably in the parse tree
Consider following code
a = b + c;
x = p r;
h = x < 0;
Panic mode recovery for block skip ahead to next ‘;’ and try to parse the next expression
It discards one expression and tries to continue parsing
May fail if no further ‘;’ is found

February 5, 2025 7 / 13
Phase Level Recovery

February 5, 2025 8 / 13
Phase Level Recovery

Make local correction to the input

February 5, 2025 8 / 13
Phase Level Recovery

Make local correction to the input

Works only in limited situations

February 5, 2025 8 / 13
Phase Level Recovery

Make local correction to the input

Works only in limited situations
▶ A common programming error which is easily detected

February 5, 2025 8 / 13
Phase Level Recovery

Make local correction to the input

Works only in limited situations
▶ A common programming error which is easily detected
▶ For example insert a “;” after closing ”}” of a class definition

February 5, 2025 8 / 13
Phase Level Recovery

Make local correction to the input

Works only in limited situations
▶ A common programming error which is easily detected
▶ For example insert a “;” after closing ”}” of a class definition
▶ Does not work very well!

February 5, 2025 8 / 13
Error Production

February 5, 2025 9 / 13
Error Production

Add erroneous constructs as productions in the grammar

February 5, 2025 9 / 13
Error Production

Add erroneous constructs as productions in the grammar

Works only for most common mistakes which can be easily identified

February 5, 2025 9 / 13
Error Production

Add erroneous constructs as productions in the grammar

Works only for most common mistakes which can be easily identified
Essentially makes common errors as part of the grammar

February 5, 2025 9 / 13
Error Production

Add erroneous constructs as productions in the grammar

Works only for most common mistakes which can be easily identified
Essentially makes common errors as part of the grammar
Complicates the grammar and does not work very well

February 5, 2025 9 / 13
Global Correction

February 5, 2025 10 / 13
Global Correction

Considering the program as a whole find a correct “nearby” program

February 5, 2025 10 / 13
Global Correction

Considering the program as a whole find a correct “nearby” program

Nearness may be measured using certain metric

February 5, 2025 10 / 13
Global Correction

Considering the program as a whole find a correct “nearby” program

Nearness may be measured using certain metric
PL/C compiler implemented this scheme: anything could be compiled!

February 5, 2025 10 / 13
Global Correction

Considering the program as a whole find a correct “nearby” program

Nearness may be measured using certain metric
PL/C compiler implemented this scheme: anything could be compiled!
It is complicated and not a very good idea!

February 5, 2025 10 / 13
Error Recovery in LL(1) parser

February 5, 2025 11 / 13
Error Recovery in LL(1) parser

Error occurs when a parse table entry M[A, a] is empty

February 5, 2025 11 / 13
Error Recovery in LL(1) parser

Error occurs when a parse table entry M[A, a] is empty

Skip symbols in the input until a token in a selected set (synch) appears

February 5, 2025 11 / 13
Error Recovery in LL(1) parser

Error occurs when a parse table entry M[A, a] is empty

Skip symbols in the input until a token in a selected set (synch) appears
Place symbols in follow(A) in synch set. Skip tokens until an element in follow(A) is seen.
Pop(A) and continue parsing

February 5, 2025 11 / 13
Error Recovery in LL(1) parser

Error occurs when a parse table entry M[A, a] is empty

Skip symbols in the input until a token in a selected set (synch) appears
Place symbols in follow(A) in synch set. Skip tokens until an element in follow(A) is seen.
Pop(A) and continue parsing
Add symbol in first(A) in synch set. Then it may be possible to resume parsing according
to A if a symbol in first(A) appears in input.

February 5, 2025 11 / 13
Error Recovery in LL(1) parser

Error occurs when a parse table entry M[A, a] is empty

Skip symbols in the input until a token in a selected set (synch) appears
Place symbols in follow(A) in synch set. Skip tokens until an element in follow(A) is seen.
Pop(A) and continue parsing
Add symbol in first(A) in synch set. Then it may be possible to resume parsing according
to A if a symbol in first(A) appears in input.

February 5, 2025 11 / 13
Bottom up parsing

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
a b b c d e

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
a b b c d e
a A b c d e

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
a b b c d e
a A b c d e
a A d e

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
a b b c d e
a A b c d e
a A d e
a A B e

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
a b b c d e
a A b c d e
a A d e
a A B e
S

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
Rightmost derivation
a b b c d e
a A b c d e
a A d e
a A B e
S

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
Rightmost derivation
a b b c d e
S → aABe
a A b c d e
a A d e
a A B e
S

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
Rightmost derivation
a b b c d e
S → aABe
a A b c d e
S → aAde
a A d e
a A B e
S

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
Rightmost derivation
a b b c d e
S → aABe
a A b c d e
S → aAde
a A d e
S → aAbcde
a A B e
S

February 5, 2025 12 / 13
Bottom up parsing

Construct a parse tree for an input string beginning at leaves and going towards root
Reduce a string w of input to start symbol of grammar
Consider the following grammar
S → aABe
A → Abc|b
B→d
Reduction of the string
Rightmost derivation
a b b c d e
S → aABe
a A b c d e
S → aAde
a A d e
S → aAbcde
a A B e
S → abbcde
S

February 5, 2025 12 / 13
Shift reduce parsing

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

▶ Two parts are separated by a special character ”.”

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

▶ Two parts are separated by a special character ”.”
▶ Left part is a string of terminals and non terminals

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

▶ Two parts are separated by a special character ”.”
▶ Left part is a string of terminals and non terminals
▶ Right part is a string of terminals

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

▶ Two parts are separated by a special character ”.”
▶ Left part is a string of terminals and non terminals
▶ Right part is a string of terminals
Initially the input is Bottom up parsing .w

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

▶ Two parts are separated by a special character ”.”
▶ Left part is a string of terminals and non terminals
▶ Right part is a string of terminals
Initially the input is Bottom up parsing .w
Bottom up parsing has two actions

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

▶ Two parts are separated by a special character ”.”
▶ Left part is a string of terminals and non terminals
▶ Right part is a string of terminals
Initially the input is Bottom up parsing .w
Bottom up parsing has two actions
Shift: move terminal symbol from right string to left string if string before shift is then
string after shift is α.pqr αp.qr

February 5, 2025 13 / 13
Shift reduce parsing

Split string being parsed into two parts

▶ Two parts are separated by a special character ”.”
▶ Left part is a string of terminals and non terminals
▶ Right part is a string of terminals
Initially the input is Bottom up parsing .w
Bottom up parsing has two actions
Shift: move terminal symbol from right string to left string if string before shift is then
string after shift is α.pqr αp.qr
Reduce: immediately on the left of “.” identify a string same as RHS of a production and
replace it by LHS if string before reduce action is αβ.pqr and A → β is a production then
string after reduction is αA.pqr

February 5, 2025 13 / 13