Compiler Design

BCB604A
MODULE-2

Syntax Analysis

Text Book: Alfred V Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman ,
“Compilers Principles, Techniques and Tools”

Course Coordinator
Dr Archana R A

Department of Computer Science and Engg

3/15/2026 1
 Contents

• The Role of Parser

• Error Recovery strategies
• Writing a Grammar
• Top Down Parsers
• Bottom Up Parsers

Department of Computer Science and Engg

3/15/2026 2
 The Role of the Parser

• What is Parsing?
• Parsing is the process of getting tokens from the lexical
analyzer and obtains a derivation for the sequence of tokens
and builds a parse tree.
• Thus, if the program is syntactically correct, the parse tree is
generated.
• If a derivation for the sequence of tokens does not exist i.e.,
if the program is syntactically wrong, it results in syntax error
and the parser displays the appropriate error messages

Department of Computer Science and Engg

3/15/2026 3
 The block diagram that shows the interaction of
parser with other modules and phases is shown
below:

Department of Computer Science and Engg

3/15/2026 4
 The role of the parser

• Parser reads sequence of tokens from the lexical analyzer

• The parser checks whether the tokens obtained from lexical
analyzer can be successfully generated. This is done by obtaining a
derivation for the sequence of tokens and builds the parse tree.
• If a derivation is obtained using the sequence of tokens it indicates
that program is syntactically correct and the parse tree is
generated.
• If a derivation is not obtained using the sequence of tokens it
indicates that program is syntactically wrong and the parse tree is
not generated. Now, the parser reports appropriate error
messages clearly and accurately along with line numbers

Department of Computer Science and Engg

3/15/2026 5
 Syntax Error Handling:
Locate and Track Errors
Common Programming Errors can occur at many different levels:
Lexical errors: include misspellings of identifiers, keywords or
operators eg: elipseSize instead of ellipseSize and missing quotes
around text intended as a string.
Syntactic errors: include misplaced semicolons or extra or missing
braces;or the appearance of a case statement without an enclosing
switch is syntactic error
Semantic errors: include type mismatches between operators and
operands, eg: the return of a value in Java method with result type
void.
Logical errors can be anything from incorrect reasoning on the part
of the programmar to the use in a C program of the assignment
operator = instead of the comparison operator ==.

Department of Computer Science and Engg

3/15/2026 6
 The error handler in a parser has following 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

programs.

Department of Computer Science and Engg

3/15/2026 7
 Error Recovery strategies

• The following activities are performed whenever errors are detected

by the parser:
• Detect the syntax errors accurately and produce appropriate error
messages so that the programmer can correct the program.
• It has to recover from the errors quickly and detect subsequent
errors in the program.
• Error handler should take all the actions very fast and should not
slowdown the compilation process.

Department of Computer Science and Engg

3/15/2026 8
 What are error recovery strategies of the
parser ?
• The various error recovery techniques are:
• Panic mode recovery
• Error productions
• Phrase level recovery
• Global correction

Department of Computer Science and Engg

3/15/2026 9
 Panic Mode Recovery

• It is the simplest and most popular error recovery method.

• When an error is detected, the parser discards symbols one
at a time until next valid token (called synchronizing token) is
found.
• The typical synchronizing tokens are:
Statement terminators such as semicolon
 Expression terminators such as \n

Department of Computer Science and Engg

3/15/2026 10
 Example
consider the erroneous expression: (5 ** 2) +8
• The parser scans the input from left to right and finds no mistake
after reading (, 5 and *.
• After reading the second *, it knows that no expression has
consecutive * operators and it displays an error “Extra * in the
input”
• Now, it has to recover from the error. In panic mode recovery, it
skips all input symbols till the next integer 2 is encountered.
Here, 2 is the synchronizing token.
• Thus, error is detected and recovered from the error in panic
mode recovery

Department of Computer Science and Engg

3/15/2026 11
 Error Productions

• The error productions specify commonly known mistakes in

the grammar.
• When we implement the parser, when an error production is
used, it displays the appropriate error message.
• For example, consider the expression 10x. Mathematically it
means multiply 10 with x.
• But, in a programming language we should write 10*x.
• Such errors can be identified very easily by incorporating
error productions and within the body of the function,
display appropriate error messages.

Department of Computer Science and Engg

3/15/2026 12
 Phrase Level Recovery
• It is an error correcting method.
• On discovering an error, a parser may perform local
correction on the remaining input.
• This is normally done by inserting, deleting or/and replacing
the input and enable the parser to continue parsing.
Ex: Replacing a comma by a semicolon, deleting an
extraneous semicolon, or inserting a missing semicolon.
• Disadvantages
• Very difficult to implement
• Slows down the parsing of correct programs
• Proper care must be taken while choosing replacements
as they may lead to infinite loops.

Department of Computer Science and Engg

3/15/2026 13
 Global Correction
• These methods replace incorrect input with correct input
using least-cost-correction algorithms.
• These algorithms take an incorrect input string x and
grammar G, and find a parse tree for a related string y,
• such that the number of insertions, deletions and changes
of tokens required to transform x into y is as small as
possible.
• These methods are costly to implement in terms of time
and space and hence are only of theoretical interest.

Department of Computer Science and Engg

3/15/2026 14
 Context-free Grammars

Definition: The context free grammar in short a CFG is 4-tuple

G = (V, T, P, S) where
• V is set of variables. The variables are also called non-terminals.
• T is set of terminals.
• P is set of produc ons. All produc ons in P are of the form A→ α
where A is a non- terminal and α is string of grammar symbols.
• S is the start symbol.
Ex : Grammar to generate one of more a‟s is shown below: A → a | aA

Department of Computer Science and Engg

3/15/2026 15
 Grammar to recognize an if-statement is
shown below:
S → i C t S |i C t S e S | a
C→b
Where
• i – stands for if keyword
• t – stands for then keyword
• e – stands for else keyword
• a – stands for a statement
• b – stands for a statement

Department of Computer Science and Engg

3/15/2026 16
“What are the various notations used when we
write the grammars?”
The following symbols are terminals
a) The keywords such as if, for, while, do-while etc.
b) Digits from 0 to 9
c) Symbols such as +, -, *, / etc
d) The lower case letters near the beginning of
alphabets such as a, b, c, d etc.
e) The letters such as id

Department of Computer Science and Engg

3/15/2026 17
 • The following symbols are non-terminals
a) The lower case names such as expression,
operand, statement etc
b) The capital letters near the beginning of the
alphabets such as A, B, C, D etc
c) The letter S is the start symbol
• The lower case letters near the end of the alphabets
such as u, v, w, x, y, z represents string of terminals.

Department of Computer Science and Engg

3/15/2026 18
 • The capital letters near the end of the alphabets
such as U, V, W, X, Y, Z etc represent grammar
symbols. A grammar symbol can be a terminal or a
non-terminal.
• The Greek letters such as α, β, γ, δ etc. represent
string of grammar symbols.

Department of Computer Science and Engg

3/15/2026 19
 Derivation
• Definition: The process of obtaining string of terminals
and/or non-terminals from the start symbol by applying
some set of productions (it may include all productions) is
called derivation.
• For example, if A → ∝B𝛾 and B →𝛽 are the productions, the
string ∝B𝛾 can be obtained from A- production as shown
below:
A => ∝B𝛾 [ Apply the produc on A → ∝B𝛾 ]
=> ∝ 𝛽 𝛾 [ Replace B by 𝛽 using the produc on B → 𝛽]
The above derivation can also be written as shown below:
A => ∝ 𝛽 𝛾

Department of Computer Science and Engg

3/15/2026 20
 “What are the two types of derivations?”

• Leftmost derivation
• Rightmost derivation

Leftmost derivation :
Definition: The process of obtaining a string of terminals from a
sequence of replacements such that only leftmost non-terminal is
replaced at each and every step is called leftmost derivation.
E-> E + E
E-> E - E
E-> E * E
E-> E / E
E-> id
Department of Computer Science and Engg
3/15/2026 21
 The leftmost derivation for the string id + id * id can be obtained as shown below:

E => E + E
=> id + E
=> id + E * E
=> id + id * E
=> id + id * id
• Rightmost derivation
Definition: The process of obtaining a string of terminals from a
sequence of replacements such that only right most non-terminal is
replaced at each and every step is called rightmost derivation.

Department of Computer Science and Engg

3/15/2026 22
 For example, consider the following grammar:
E-> E + E
E-> E * E
E-> ( E )
E-> id
The rightmost derivation for the string id + id * id can be obtained as
shown below:

E => E + E
=> E+ E * E
=> E + E * id
=> E + id * id
=> id + id * id

Department of Computer Science and Engg

3/15/2026 23
 Example 1:Consider the grammar shown below from which any
arithmetic
expression can be obtained.
E-> E + E
E-> E - E
E-> E * E
E-> E / E
E-> id

• Obtain the string id + id * id and show the derivation for the same.

Department of Computer Science and Engg

3/15/2026 24
 • Solution: The derivation to get the string id + id * id is shown below.

E => E + E
=> id + E
=> id + E * E
=> id + id * E
=> id + id * id
E => id + id * id

Department of Computer Science and Engg

3/15/2026 25
[Link] the Ambiguity
for the string ibtibtaea with the production below
• S → iCtS|iCtSeS|a
• C→b
• where
• i stands for keyword if
• C stands for Condition to be satisfied. Here C is a
non-terminal
• t stands for keyword then
• S stands statement for non-terminal
• e stands for keyword else
• a stands for other statement
• b stands for other statement
Department of Computer Science and Engg
3/15/2026 26
 [Link] for Ambiguity
E-> E + E
E-> E - E
E-> E * E
E-> E / E
E-> (E)/ E
E-> id

• Obtain the string id + id * id and show the derivation for the same.

Department of Computer Science and Engg

3/15/2026 27
 [Link] for Ambiguity
• S->AB/aaB
• A->/Aa
• B->b
• String is aab

4. Check for Ambiguity

A->aA/Aa/a
S->A

String is aaa

Department of Computer Science and Engg

3/15/2026 28
 What is left recursion?

• Definition: A grammar G is said to be left recursive if it has non-

terminal A such that there is a derivation of the form:
• A =>A𝛼
• where 𝛼 is string of terminals and non-terminals.
• whenever the first symbol in a partial derivation is same as the
symbol from which this partial derivation is obtained, then the
grammar is said to be left-recursive grammar.
A grammar may have:
• immediate left recursion
• indirect left recursion

Department of Computer Science and Engg

3/15/2026 29
 Immediate left recursion:
• A grammar G is said to have immediate left recursion if it has a production of
the form:
A → A𝛼
For example, consider the following grammar:
E → E + T |T
T → T * F |F
F → (E) | id
• In the above grammar consider the first two productions:
E → E +T
T→ T * F
• Observe that in the above two productions, the first symbol on the right
hand side of the production is same as the symbol on the left hand side of
the production. So, the given grammar has immediate left recursion in two
productions.
Department of Computer Science and Engg
3/15/2026 30
 Indirect left recursion:

• A left recursion involving derivations of two or more steps so that the

first symbol on the right hand side of the partial derivation is same as
the symbol from which the derivation started is called indirect left
recursion. For example, consider the following grammar:
• E→ T
T→ F
F → E + T | id
• Consider the following derivation:
E => T => F => E +T

Department of Computer Science and Engg

3/15/2026 31
 Elimination of 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’ / ∈

Department of Computer Science and Engg

3/15/2026 32
 Department of Computer Science and Engg
3/15/2026 33
1>Eliminate left recursion from the following grammar
• E → E +T | T
• T → T * F |F
• F → (E)|id
Soln:
1) E→ E +T | T
↓ ↓ ↓. ↓
A→A 𝛼|β
2. ) T→ T *F | F
↓ ↓↓ ↓
A→A 𝛼|β
3) F→ (E) | id

Department of Computer Science and Engg

34
 • The final grammar obtained after eliminating left recursion can be
written as shown below:
• A → βA’
• A’ → αA’ / ∈

• E→ TE'
• E'→ +TE'| ε
• T → FT'
• T'→ *FT'| ε
• F→ (E)|id

Department of Computer Science and Engg

3/15/2026 35
 2>Eliminate left recursion from the following grammar:
(Indirect Left Recursion)
• S → Aa|b
• A → Ac | Sd | ε
Solution:
First eliminate immediate left recursion
A → Ac | Sd | ε
Second Replace A in S-> Aa/b
Third remove indirect left recursion
Final production:
• S → A'aS' | bS'
S' → dA'aS' | ε
A → SdA' | A'
A' → cA' | ε
Department of Computer Science and Engg
3/15/2026 36
 Left factoring

• Definition: A grammar in which two or more productions from a non-

terminal A do not have a common prefix of symbols on the right hand
side of the A-productions is called left factored grammar.
• The left-factored grammar is suitable for top-down parser such as
recursive descent parser with or without backtracking.
Ex 1: The grammar to generate string consisting of at least one „a‟
followed by at least one „b‟ can be written as shown below:
S → aAbB
A→ aA | ε Left factored grammar
B → bB | ε

Department of Computer Science and Engg

3/15/2026 37
 Observe the following points:
• The S-production has only one production and it cannot have
common prefix on the right side of the production.
• The two A-productions do not have any common prefix on the right
side.
• Finally two B-productions do not have any common prefix on the
right side of that production

Department of Computer Science and Engg

3/15/2026 38
 • Ex 2: The grammar that generates string consisting of at least one „a‟
followed by at least one „b‟ can also be written as shown below:
S → AB
A→ aA | a Non Left factored grammar
B → bB | b
Observe the following points:
• The S-production has only one production and it is not having
common prefix on the right side of the production.
• The two A-productions have a common prefix “a” on the right side of
the production.
• The two B-productions have a common prefix “b” on the right side of
the production.
• Since common prefix is present in both A-productions and B-
productions, it is not left-factored grammar.

Department of Computer Science and Engg

3/15/2026 39
 What is the use of left factoring?

• Left factoring is must for top down parser such as recursive descent
parser with backtracking or predictive parser which is also recursive
descent parser without backtracking.
• This is because, if A-production has two or more alternate
productions and they have a common prefix, then the parser has
some confusion in selecting the appropriate production for
expanding the non-terminal A

Department of Computer Science and Engg

3/15/2026 40
 How to do left factoring?

1) Consider two A-productions with common prefix

α: A → αβ1| αβ2
2) Let the input begins with string derived from α. Since α is the
common prefix,
we retain α and we replace either β1 or β2 by the non-terminal A’.
So, we can write the above production as:
• A → α A’
where A' can produce either β1 or β2 using the
production:

• A'→ β1|β2
Department of Computer Science and Engg
3/15/2026 41
 Left Factoring

Department of Computer Science and Engg

3/15/2026 42
 Algorithm for Left Factoring
1) For each non-terminal A, find the longest prefix α which is common
to two or more of its alternatives.
2) If there is a produc on of the form: A → αβ1 | αβ2 | αβ3 |... αβn| γ
where γ do not start with α, then the above A-production can be
written as shown below:
• A→ α A' | γ
A'→ β1 | β2 | β3 |..... βn
Here, A' is a new non-terminal.
3) Repeatedly apply the transformation in step 2 as long as two
alternatives for a non- terminal have a common prefix
4) Return the final grammar which is left-factored

Department of Computer Science and Engg

3/15/2026 43
 Example

1>S->abA/abB
A->aa
B->ab

2>S->iEtS/ iEtSeS/a
E->b

3>A->aAB/aBC/aAC

Department of Computer Science and Engg

3/15/2026 44
 Parsing techniques

Department of Computer Science and Engg

3/15/2026 45
 Top-down Parsing

• The process of constructing a parse tree for the string of

tokens from top i.e., starting from the root node and
creating the nodes of the parse tree is called top down
parsing

• The parser that uses this approach is called top down parser.

• Since the parsing starts from top i.e., root down to the
leaves, it is called top down parser.

Department of Computer Science and Engg

3/15/2026 46
 • Example :
Show the top-down parsing process for the string id + id * id for the
grammar
E → E +E E→E*E E → (E) E→ id

E => E +E
=> id+E
=> id + E * E
=> id + id * E
=> id + id * id

Department of Computer Science and Engg

3/15/2026 47
 The above derivation can be written in the form of a parse tree
from the start symbol using top-down approach as shown
below:

Department of Computer Science and Engg

3/15/2026 48
 Recursive descent parser

• A recursive descent parser is a top down parser in which parse tree is

constructed from the top starting from root node and selecting the
productions from left to right
• For every non-terminal there exists a recursive procedure and the
right hand of the production of that non-terminal is implemented as
the body of the procedure
• The sequence of terminals and non-terminals on the right hand side
of the production correspond to matching with input symbols and
calls to other procedures while selecting the alternate production is
implemented using switch or if-statements.
• Thus, the syntax or structure of the resulting program closely mirrors
that of the grammar it recognizes.

Department of Computer Science and Engg

3/15/2026 49
 • For example, the procedure for the produc on A → α can be written
as shown below:
procedure A () // Function header
{
......
...... body of the function
......
}

Department of Computer Science and Engg

3/15/2026 50
 Algorithm for recursive descent parser

procedure A() // A → X1X2X3.......Xk

{
for i = 1 to k do
if (Xi is a non-terminal)
call procedure Xi();
else if (Xi is same as current input symbol a)
advance the input to the next symbol
else
error();
end for
}

Department of Computer Science and Engg

3/15/2026 51
 1>Write the recursive descent parser for the following grammar
E→ T
T→ F
F → (E) | id
// func on corresponding to the produc on E → T
procedure E()
{
T();
}
// func on corresponding to the produc on T → F
procedure T()
{
F();
}

Department of Computer Science and Engg

3/15/2026 52
 • // func on corresponding to the produc on F → (E) | id
procedure F()
{
if (input_symbol == “(” )
advance input pointer
E();
if (input_symbol == “)” )
advance input pointer
else
error()
end if
else if (input_symbol == id)
advance input pointer
else
error();
end if
Department of Computer Science and Engg
}
3/15/2026 53
 Different types of recursive descent parsers

• Recursive descent parser with backtracking

• Recursive descent parser without backtracking (predictive parser)

What is the need for backtracking in recursive descent parser?”

• During parsing, the productions are applied one by one. But, if two or
more alternative productions are there, they are applied in order
from left to right one at a time.
• When a particular production applied fails to expand the non-
terminal properly, we have to apply the alternate production. Before
trying alternate production, it is necessary undo the activities done
using the current production. This is possibly only using backtracking.

Department of Computer Science and Engg

3/15/2026 54
 • Show the steps involved in recursive descent parser with
backtracking for the input string cad for the following grammar
S → cAd A → ab | a

Department of Computer Science and Engg

3/15/2026 55
 Department of Computer Science and Engg
3/15/2026 56
 Department of Computer Science and Engg
3/15/2026 57
 “For what type of grammars recursive descent parser cannot
be constructed? What is the solution?

The recursive descent parser cannot be constructed for a grammars

having:
• Ambiguity. The solution is to eliminate ambiguity from the grammar.
• Left recursion. The solution is to eliminate left recursion from the
grammar.
• Two or more alternatives having a common prefix. The solution is to
left factor the grammar.

Department of Computer Science and Engg

3/15/2026 58
 Consider the produc on E→ E + T . Write the recursive descent
parser. (Recursive grammar for left recursion- drawback)

// func on corresponding to the produc on E → E + T

procedure E()
{
E();
if (input_symbol = “+” )
advance input pointer
else
error
end if
T();
}

Department of Computer Science and Engg

3/15/2026 59
 “What is the problem in constructing recursive descent parser
for the grammar having left recursion?”
• When a procedure is invoked, the parameter values along with
return address will be pushed on to the stack and hence stack size
decreases
• The procedure E() is called recursively infinitely without consuming
any input and hence the size of the stack grows very fast and stack
will be full soon.
• Since there is no space left on the stack to push parameter values
and return address, the system crashes.
• So. the recursive descent parser that is built using left-recursive
grammar can cause a parser to go into an infinite loop eventually
crashing the system
• Hence the left recursive grammar is not suitable for recursive
descent parser. Hence, we have to eliminate left recursion from the
grammar and then parse the string.

Department of Computer Science and Engg

3/15/2026 60
 • Write the recursive descent parser for the following grammar:
• E → TE’ , E'→ +TE'| ε , T → FT’ , T'→ *FT'| ε , F→ (E)|id
Soln:

• // func on corresponding to the produc on: E → T E’

procedure E()
{
T();
EDASH();
}

Department of Computer Science and Engg

3/15/2026 61
 • // func on corresponding to the produc on: E' → + T E’ | ε
procedure EDASH()
{
if ( inputsymbol == „+‟)
{
Advance input pointer
T();
EDASH();
}
}
• // func on corresponding to the produc on: T → F T’
procedure T()
{
F();
TDASH(); }
Department of Computer Science and Engg
3/15/2026 62
 • // func on corresponding to the produc on: T' → * F T'| ε
procedure TDASH()
{
if ( inputsymbol == „*‟)
{
advance input pointer
F();
TDASH();
}
}

Department of Computer Science and Engg

3/15/2026 63
 • // func on corresponding to the produc on: F → ( E ) | id
procedure F()
{
if ( inputsymbol == „(„)
{
advance input pointer
E();
if ( inputsymbol == „)‟)
advance input pointer
else error(); }
else
{ if (inputsymbol == id )
advance input pointer
else error(); }
}
Department of Computer Science and Engg
3/15/2026 64
 Problems with top down parser

• Ambiguity in the grammar

• Left recursion
• Non-left factored grammar
• Backtracking

Department of Computer Science and Engg

3/15/2026 65
 • First and Follow,
• LL (1) Grammars,
• Non-recursive Predictive Parsing,
• Error Recovery in Predictive Parsing.
: Refer nots

Department of Computer Science and Engg

3/15/2026 66
 Department of Computer Science and Engg
3/15/2026 67
 Department of Computer Science and Engg
3/15/2026 68
 Department of Computer Science and Engg
3/15/2026 69
 Department of Computer Science and Engg
3/15/2026 70
3/15/2026 Department of Computer Science and Engg
71