Module 3 :

SYNTAX ANALYSIS
- (Elimination of Left
Recursion, Left
Factoring)
 Elimination of Left Recursion

➢ A grammar is left recursive if it has a

nonterminal A such that there is a derivation

For some strings α

➢ It is important to remove left recursion from

grammar because it can create an infinite
loop, leading to errors and a significant
decrease in performance
 Elimination of Left Recursion
➢ Classification of CFG based on Ambiguity
Ambiguous CFG
CFG
Unambiguous CFG
➢ Classification of CFG based on Recursion
Right Recursion
CFG
Left Recursion
➢ Classification of CFG based on Determinism
Deterministic CFG
CFG
Nondeterministic CFG
 Elimination of Left Recursion
➢ Recursion in CFG:

❑ Consider the following grammar:

E -> E*Product // This is left recursive

Product -> Term ^ Product // This is right recursive

 Elimination of Left Recursion
➢ Left Recursion:

❑ A generic left recursive grammar is of the

form
A -> Aα | β

❖ Here, A is Non-Terminal
❖ α and β are sequences of terminals and
non-terminals and do not start with A
❑ This grammar will generate the language in the
form
A= βα*
 Elimination of Left Recursion
➢ Right Recursion:

❑ A generic right recursive grammar is of the

form
A -> αA | β

❖ Here, A is Non-Terminal
❖ α and β are sequences of terminals and
non-terminals and do not start with A
❑ This grammar will generate the language in the
form
A= α* β
 Elimination of Left Recursion
➢ Problems due to Left Recursion:
❑ An Example: Recursion in programming language:
When a function calls itself, it is recursive function.
If we use the following left recursive grammar to
represent recursive functions
A -> Aα | β
Then, the recursive code will take the following form
A( )
{
This code will form infinite A( );
loops. Because, there is no α;
scope to represent the condition }
when to terminate the loop
 Elimination of Left Recursion

➢ Top-down parsing methods cannot handle left

recursive grammars, since this kind of parsing is
finding a leftmost derivation for an input string.

➢ as the entire process will go into an infinite loop, so a

transformation is needed to eliminate left recursion

A -> Aα | β
-> Aαα
-> Aααα
-> Aαααα
 Elimination of Left Recursion

➢ This is a purely a problem of left recursiveness. i.e., the

left hand side of the production keeps on repeating
until a terminal symbol halts the entire process.

➢ So we need to eliminate this left recursion, so that

grammar executes for the input we are looking for.
 Elimination of Left Recursion

❑ In this case, if right recursive grammar is used,

then, infinite loops will not be formed.
A -> αA | β

Then, the recursive code will take the following form

A( )
This code will not form infinite {
loops. Because, inside “α”, you α;
can write the condition to A( );
terminate a loop. }
 Elimination of Left Recursion
➢ Solution: Convert Left Recursion to Right
Recursion

❑ As per generic left recursive grammar

A -> Aα | β
❖ The recognised language is A= βα*
❑ In the case of equivalent right recursive grammar,
the recognised language will be same but
production rules will be different.
❑ The equivalent right recursive grammar is
A -> βA’
A’ -> αA’ | ɛ
 Elimination of Left Recursion
➢ Example 1: Elimination of Left Recursion

❑ Given Grammar :
S -> S+S | a
❖ This grammar is left recursive grammar
❖ Comparing it with generic form of Left
recursive grammar A -> Aα | β, we get
α = +S, β =a
❖ Now, we need to convert the given grammar
towards the following form
A -> βA’ S->aS’
A’ -> αA’ | ɛ i.e. S’-> +SS’ | ɛ
 Elimination of Left Recursion
➢ Example 1: Elimination of Left Recursion

❑ Given Grammar :
S -> S+S | a

❖ So, after eliminating left recursion from the

given grammar, the grammar will be

S->aS’
S’-> +SS’ | ɛ
 Elimination of Left Recursion
➢ Example 2: Elimination of Left Recursion
Given Grammar :
 Elimination of Left Recursion
➢ Example 3: Elimination of Left Recursion

❑ Given Grammar :
S -> S*T | T
T -> id
❖ Comparing it with generic form of Left
recursive grammar A -> Aα | β, we get
α = *T, β =T
❖ Now, we need to convert the given grammar
towards the following form
A -> βA’ S->TS’
A’ -> αA’ | ɛ i.e. S’-> *TS’ | ɛ
T ->id
 Elimination of Left Recursion
➢ Example 4: Elimination of Left Recursion

❑ Given Grammar :
 Elimination of Left Recursion
➢ Example 5: Elimination of Left Recursion

❑ Given Grammar :

➢ After elimination of left recursion

 Elimination of Left Recursion
➢ Example 6: Elimination of Left Recursion

❑ Given Grammar :

➢ This grammar has left recursion involving

derivations of two or more steps.
➢ In this grammar, The nonterminal S is left
recursive because S ->Aa ->Sda
➢ To address this issue, the nonterminal A will be
written as A -> A c | A a d | b d | ɛ
 Elimination of Left Recursion
➢ Example 6: Elimination of Left Recursion

❑ Given Grammar :

➢ So, now the grammar will have the following

form
S -> A a | b
A -> A c | A a d | b d | ɛ
➢ After elimination of left
recursion
 Question?
➢ Eliminate left recursion from the following
grammar

❑
 Left Factoring
➢ Classification of CFG based on Ambiguity
Ambiguous CFG
CFG
Unambiguous CFG
➢ Classification of CFG based on Recursion
Right Recursion
CFG
Left Recursion
➢ Classification of CFG based on Determinism
Deterministic CFG
CFG
Nondeterministic CFG
 Left Factoring
➢ Non-Deterministic CFGs: When two or more
production rules have common prefix

➢ A -> αβ1 | αβ2 | αβ3

➢ Problems in Non-Deterministic CFGs:

❖ Top-down parsing requires backtracking for this
kind of grammar due to confusion which
production rule should be chosen. Backtracking is
a costly process.
 Left Factoring
➢ Example of Backtracking:
A
➢ A -> αβ1 | αβ2 | αβ3
α β312
➢ Let’s assume, top down parser want to recognise the
following string αβ3
❖ In this case, the parser starts with the 1st production
rule A -> αβ1 , but this is not the correct production
rule.
❖ So, it then backtrack towards the root A and select 2nd
production rule αβ2. Again, it’s not the correct rule.
❖ So, it then backtracks towards the root again and
select 3rd production rule A -> αβ3
 Left Factoring
➢ Hence, the main reason behind backtracking is that,
production rules are chosen by top-down parsers
without be examined completely

➢ A -> αβ1 | αβ2 | αβ3

➢ By seen only prefix α, the production rules are

selected
➢ Therefore, this common long prefix need to be
removed from the production rules
➢ The mechanism related to removal of non-
determinism is called Left Factoring
 Left Factoring
➢ To remove non-determinism from the grammar,
production rules need to be represented in the
following form
❑ Before Left Factoring:
❖ A -> αβ1 | αβ2 | αβ3 ➢ The grammar that
is obtained after
❑ After Left Factoring: left factoring is
❖ A -> αA’ called Left
A’ -> β1 | β2 | β3 Factored
Grammar
➢ To achieve this grammar, the leftmost common prefix α
is factored out from each production rule. That is the
reason behind the name “Left Factoring”
 Left Factoring
➢ Algorithm for Left Factoring
➢ INPUT: Grammar G.
➢ OUTPUT: An equivalent left-factored grammar
 Left Factoring
➢ Example 1: Left Factoring

❑ Given Grammar :
A -> aAB | aBc | aAc

❖ Each production rules in this grammar has a

common prefix a

❖ Comparing it with the following grammar

form
A -> αβ1 | αβ2 | αβ3

We get, α=a, β1=AB, β2= Bc and β3= Ac

 Left Factoring
➢ Example 1: Left Factoring
❑ Given Grammar :
A -> aAB | aBc | aAc
❖ Next, we will represent the given grammar in the
following form
A -> αA’
A’ -> β1 | β2 | β3
❖ So, after 1st left factoring the given grammar will
be
A -> aA’
A’ -> AB | Ac | Bc

❖ Now, in the above grammar the 2nd production rule is

again representing non-determinism.
 Left Factoring
➢ Example 1: Left Factoring
❑ Given Grammar :
A -> aAB | aBc | aAc
➢ after 1st left factoring A -> aA ’
A’ -> AB | Ac | Bc
❖ Because, “A” is the common prefix.
❖ Need to apply Left Factoring again
❖ Here, α=A ; β1=A ; β2=c
❖ So, after applying 2nd time left factoring,

A -> aA’
A’ -> AA’’| Bc
A’’-> B | c
 Left Factoring
➢ Example 1: Left Factoring

❑ Given Grammar :
A -> aAB | aBc | aAc

❖ Now, we will represent the given grammar in the

following form
A -> αA’
A’ -> β1 | β2 | β3

❖ So, after 1st left factoring the given grammar will

be A -> aA’
A’ -> AB | Bc | Ac
 Left Factoring
➢ Example 2: Left Factoring

❑ Given Grammar: The following grammar

abstracts the “dangling-else" problem

❑ Each production rule in the given grammar has

a common prefix iEtS
 Left Factoring
➢ Example 2: Left Factoring

❑ Given Grammar: The following grammar

abstracts the “dangling-else" problem

❑ Comparing the given grammar with the

following grammar form
A -> αβ1 | αβ2 | αβ3

❑We get, S= A; α=iEtS; β1=ɛ ; β2=eS

 Left Factoring
➢ Example 2: Left Factoring

❑ Given Grammar: The following grammar

abstracts the “dangling-else" problem

❑ Therefore, according to the following grammar form

A -> αA’
A’ -> β1 | β2 | β3
The left factored grammar will be
S -> iEtSS’ | a
S’-> eS | ɛ
E -> b
 Question?

➢ Does the following grammars require left

factoring? If yes, perform the same

1. A -> bAAaaA | bAAaAb | bAc | a

2. S -> a | ab| abc |abcd

3. id_list --> id | id , id_list | id[] | id()