Lecture 7
Syntax Analysis
Awanish Pandey
Department of Computer Science and Engineering
Indian Institute of Technology
Roorkee
February 4, 2025
February 4, 2025 1 / 12
Take aways from the last class
Overview of Syntax Analysis
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
Parse Tree
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
Parse Tree
Ambiguity
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
Parse Tree
Ambiguity
Resolving dangling if-else problem.
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
Parse Tree
Ambiguity
Resolving dangling if-else problem.
Top down parsing
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
Parse Tree
Ambiguity
Resolving dangling if-else problem.
Top down parsing
Recursive Descent Parsing
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
Parse Tree
Ambiguity
Resolving dangling if-else problem.
Top down parsing
Recursive Descent Parsing
Left Recursion
February 4, 2025 2 / 12
Take aways from the last class
Overview of Syntax Analysis
Derivation of string from a grammer
Parse Tree
Ambiguity
Resolving dangling if-else problem.
Top down parsing
Recursive Descent Parsing
Left Recursion
Left Factoring
February 4, 2025 2 / 12
Predictive Parser
A non recursive top down parsing method
February 4, 2025 3 / 12
Predictive Parser
A non recursive top down parsing method
Parser “predicts” which production to use
February 4, 2025 3 / 12
Predictive Parser
A non recursive top down parsing method
Parser “predicts” which production to use
It removes backtracking by fixing one production for every non- terminal and input
token(s)
February 4, 2025 3 / 12
Predictive Parser
A non recursive top down parsing method
Parser “predicts” which production to use
It removes backtracking by fixing one production for every non- terminal and input
token(s)
Predictive parsers accept LL(k) languages
February 4, 2025 3 / 12
Predictive Parser
A non recursive top down parsing method
Parser “predicts” which production to use
It removes backtracking by fixing one production for every non- terminal and input
token(s)
Predictive parsers accept LL(k) languages
▶ First L stands for left to right scan of input
February 4, 2025 3 / 12
Predictive Parser
A non recursive top down parsing method
Parser “predicts” which production to use
It removes backtracking by fixing one production for every non- terminal and input
token(s)
Predictive parsers accept LL(k) languages
▶ First L stands for left to right scan of input
▶ Second L stands for leftmost derivation
February 4, 2025 3 / 12
Predictive Parser
A non recursive top down parsing method
Parser “predicts” which production to use
It removes backtracking by fixing one production for every non- terminal and input
token(s)
Predictive parsers accept LL(k) languages
▶ First L stands for left to right scan of input
▶ Second L stands for leftmost derivation
▶ k stands for number of lookahead token
February 4, 2025 3 / 12
Predictive Parser
A non recursive top down parsing method
Parser “predicts” which production to use
It removes backtracking by fixing one production for every non- terminal and input
token(s)
Predictive parsers accept LL(k) languages
▶ First L stands for left to right scan of input
▶ Second L stands for leftmost derivation
▶ k stands for number of lookahead token
▶ In practice LL(1) is used
February 4, 2025 3 / 12
Predictive Parser
Predictive parser can be implemented by maintaining an external stack
February 4, 2025 4 / 12
Predictive Parser
Predictive parser can be implemented by maintaining an external stack
February 4, 2025 4 / 12
Predictive Parser
Predictive parser can be implemented by maintaining an external stack
Parse table is a two dimensional array M[X , a] where “X ” is a non terminal and “a” is a
terminal of the grammar
February 4, 2025 4 / 12
Example
Consider the following grammar:
E → TE ′
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
February 4, 2025 5 / 12
Parse table for the grammar
id + * ( ) $
′ ′
E E → TE E → TE
′ ′ ′ ′
E’ E → +TE E →ϵ E →ϵ
′ ′
T T → FT T → FT
′ ′ ′ ′ ′
T’ T →ϵ T → ∗FT T →ϵ T →ϵ
F F → id F → (E )
February 4, 2025 6 / 12
Parse table for the grammar
id + * ( ) $
′ ′
E E → TE E → TE
′ ′ ′ ′
E’ E → +TE E →ϵ E →ϵ
′ ′
T T → FT T → FT
′ ′ ′ ′ ′
T’ T →ϵ T → ∗FT T →ϵ T →ϵ
F F → id F → (E )
Blank entries are error states.
February 4, 2025 6 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
if X = a = $ then halt
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
if X = a = $ then halt
if X = a ̸= $ then pop(x) and ip + +
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
if X = a = $ then halt
if X = a ̸= $ then pop(x) and ip + +
if X is a non terminal
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
if X = a = $ then halt
if X = a ̸= $ then pop(x) and ip + +
if X is a non terminal
then if M[X , a] = X → UVW
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
if X = a = $ then halt
if X = a ̸= $ then pop(x) and ip + +
if X is a non terminal
then if M[X , a] = X → UVW
then begin pop(X); push(W,V,U)
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
if X = a = $ then halt
if X = a ̸= $ then pop(x) and ip + +
if X is a non terminal
then if M[X , a] = X → UVW
then begin pop(X); push(W,V,U)
end
February 4, 2025 7 / 12
Parsing Algorithm
The parser considers ’X ’ the symbol on top of stack, and ’a’ the current input symbol.
These two symbols determine the action to be taken by the parser.
Assume that ’$’ is a special token that is at the bottom of the stack and terminator for
the input string
if X = a = $ then halt
if X = a ̸= $ then pop(x) and ip + +
if X is a non terminal
then if M[X , a] = X → UVW
then begin pop(X); push(W,V,U)
end
else error
February 4, 2025 7 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
February 4, 2025 8 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
$E’T id+id*id $ expand by T → FT ′
February 4, 2025 8 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
$E’T id+id*id $ expand by T → FT ′
$E’T’F id+id*id $ expand by F → id
February 4, 2025 8 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
$E’T id+id*id $ expand by T → FT ′
$E’T’F id+id*id $ expand by F → id
$E’T’id id+id*id $ pop id and ip++
February 4, 2025 8 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
$E’T id+id*id $ expand by T → FT ′
$E’T’F id+id*id $ expand by F → id
$E’T’id id+id*id $ pop id and ip++
$E’T’ +id*id $ expand by T → ϵ
February 4, 2025 8 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
$E’T id+id*id $ expand by T → FT ′
$E’T’F id+id*id $ expand by F → id
$E’T’id id+id*id $ pop id and ip++
$E’T’ +id*id $ expand by T → ϵ
$E’ +id*id $ expand by E ′ → +TE ′
February 4, 2025 8 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
$E’T id+id*id $ expand by T → FT ′
$E’T’F id+id*id $ expand by F → id
$E’T’id id+id*id $ pop id and ip++
$E’T’ +id*id $ expand by T → ϵ
$E’ +id*id $ expand by E ′ → +TE ′
$E’T+ +id*id $ pop + and ip++
February 4, 2025 8 / 12
Example
Stack Input Action
$E id+id*id $ expand by E → TE ′
$E’T id+id*id $ expand by T → FT ′
$E’T’F id+id*id $ expand by F → id
$E’T’id id+id*id $ pop id and ip++
$E’T’ +id*id $ expand by T → ϵ
$E’ +id*id $ expand by E ′ → +TE ′
$E’T+ +id*id $ pop + and ip++
$E’T id*id $ expand by T → FT ′
February 4, 2025 8 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
$E’T’ *id $ expand by T ′ → ∗FT ′
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
$E’T’ *id $ expand by T ′ → ∗FT ′
$E’T’F* *id $ pop * and ip++
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
$E’T’ *id $ expand by T ′ → ∗FT ′
$E’T’F* *id $ pop * and ip++
$E’T’F id $ expand by F → id
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
$E’T’ *id $ expand by T ′ → ∗FT ′
$E’T’F* *id $ pop * and ip++
$E’T’F id $ expand by F → id
$E’T’id id $ pop id and ip++
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
$E’T’ *id $ expand by T ′ → ∗FT ′
$E’T’F* *id $ pop * and ip++
$E’T’F id $ expand by F → id
$E’T’id id $ pop id and ip++
$E’T’ $ expand by T ′ → ϵ
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
$E’T’ *id $ expand by T ′ → ∗FT ′
$E’T’F* *id $ pop * and ip++
$E’T’F id $ expand by F → id
$E’T’id id $ pop id and ip++
$E’T’ $ expand by T ′ → ϵ
$E’ $ expand by E ′ → ϵ
February 4, 2025 9 / 12
Example
Stack Input Action
$E’T’F id*id $ expand by F → id
$E’T’id id*id $ pop id and ip++
$E’T’ *id $ expand by T ′ → ∗FT ′
$E’T’F* *id $ pop * and ip++
$E’T’F id $ expand by F → id
$E’T’id id $ pop id and ip++
$E’T’ $ expand by T ′ → ϵ
$E’ $ expand by E ′ → ϵ
$ $ halt
February 4, 2025 9 / 12
Constructing Parse table
February 4, 2025 10 / 12
Constructing Parse table
Table can be constructed if for every non terminal, every lookahead symbol can be
handled by at most one production
February 4, 2025 10 / 12
Constructing Parse table
Table can be constructed if for every non terminal, every lookahead symbol can be
handled by at most one production
First(a) for a string of terminals and non terminals a is Set of symbols that might begin
the fully expanded (made of only tokens) version of a
February 4, 2025 10 / 12
Constructing Parse table
Table can be constructed if for every non terminal, every lookahead symbol can be
handled by at most one production
First(a) for a string of terminals and non terminals a is Set of symbols that might begin
the fully expanded (made of only tokens) version of a
Follow(X) for a non terminal X is set of symbols that might follow the derivation of X in
the input stream
February 4, 2025 10 / 12
Computation of FIRST set
February 4, 2025 11 / 12
Computation of FIRST set
If X is a terminal symbol then First(X ) = X
February 4, 2025 11 / 12
Computation of FIRST set
If X is a terminal symbol then First(X ) = X
If X → ϵ is a production then ϵ is in First(X).
February 4, 2025 11 / 12
Computation of FIRST set
If X is a terminal symbol then First(X ) = X
If X → ϵ is a production then ϵ is in First(X).
If X is a non terminal and X → Yl Y2 · · · Yk is a production then if for some ”i”, ”a” is in
First(Yi ) and ϵ is in all of First(Yj ) (such that j < i) then a is in First(X )
February 4, 2025 11 / 12
Computation of FIRST set
If X is a terminal symbol then First(X ) = X
If X → ϵ is a production then ϵ is in First(X).
If X is a non terminal and X → Yl Y2 · · · Yk is a production then if for some ”i”, ”a” is in
First(Yi ) and ϵ is in all of First(Yj ) (such that j < i) then a is in First(X )
If ϵ is in First(Y1 ) · · · First(Yk ) then ϵ is in First(X )
February 4, 2025 11 / 12
Example
For the expression grammar
′
E → TE
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
February 4, 2025 12 / 12
Example
For the expression grammar
′
E → TE
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
First(E ) = First(T ) = First(F ) = (, id
February 4, 2025 12 / 12
Example
For the expression grammar
′
E → TE
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
First(E ) = First(T ) = First(F ) = (, id
First(E ′ ) = +, ϵ
February 4, 2025 12 / 12
Example
For the expression grammar
′
E → TE
E ′ → +TE ′ |ϵ
T → FT ′
T ′ → ∗FT ′ |ϵ
F → (E )|id
First(E ) = First(T ) = First(F ) = (, id
First(E ′ ) = +, ϵ
First(T ′ ) = ∗, ϵ
February 4, 2025 12 / 12