•
1. Recursive Grammar
2. Non-Recursive Grammar
1. Recursive Grammar-
• A grammar is said to be recursive if it contains at least one production that has the same
variable at both its LHS and RHS.
OR
• A grammar is said to be recursive if and only if it generates infinite number of strings.
A recursive grammar may be either-
1. Left recursive grammar
2. Right recursive grammar
A) Left Recursive Grammar-
• A recursive grammar is said to be left recursive if the leftmost variable of RHS is same as
variable of LHS.
OR
• A recursive grammar is said to be left recursive if it has Left Recursion.
Example-
S → Sa / b
(Left Recursive Grammar)
B) Right Recursive Grammar-
• A recursive grammar is said to be right recursive if the rightmost variable of RHS is same
as variable of LHS.
OR
• A recursive grammar is said to be right recursive if it has right recursion.
Example-
S → aS / b
(Right Recursive Grammar)
2. Non-Recursive Grammar-
• A grammar is said to be non-recursive if it contains no production that has the same
variable at both its LHS and RHS.
OR
• A grammar is said to be non-recursive if and only if it generates finite number of strings.
NOTE
A non-recursive grammar has neither left recursion nor right recursion.
Example-
S → aA / bB
A→a/b
B→c/d
(Non-Recursive Grammar)
The language generated from this grammar is L = { aa , ab , bc , bd }
Since the grammar generates finite number of strings, therefore it is a non-recursive
grammar.
Important Notes-
Note-01:
The grammar which is either left recursive or right recursive is always unambiguous.
Examples-
• S → aS / b (Unambiguous Grammar)
• S → Sa / b (Unambiguous Grammar)
Note-02:
The grammar which is both left recursive and right recursive is always ambiguous.
Example-
E → E + E / E – E / E x E / id
(Ambiguous Grammar)
Note-03:
• Left recursive grammar is not suitable for Top down parsers.
• This is because it makes the parser enter into an infinite loop.
• To avoid this situation, it is converted into its equivalent right recursive grammar.
• This is done by eliminating left recursion from the left recursive grammar.
Note-04:
• The conversion of left recursive grammar into right recursive grammar and vice-versa is
decidable.
Recursion-
Recursion can be classified into following three types-
1. Left Recursion
2. Right Recursion
3. General Recursion
1. Left Recursion-
• A production of grammar is said to have left recursion if the leftmost variable of its RHS
is same as variable of its LHS.
• A grammar containing a production having left recursion is called as Left Recursive
Grammar.
Example-
S → Sa / ∈
(Left Recursive Grammar)
• Left recursion is considered to be a problematic situation for Top down parsers.
• Therefore, left recursion has to be eliminated from the grammar.
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’ / ∈
(Right Recursive Grammar)
This right recursive grammar functions same as left recursive grammar.
2. Right Recursion-
• A production of grammar is said to have right recursion if the rightmost variable of its
RHS is same as variable of its LHS.
• A grammar containing a production having right recursion is called as Right Recursive
Grammar.
Example-
S → aS / ∈
(Right Recursive Grammar)
• Right recursion does not create any problem for the Top down parsers.
• Therefore, there is no need of eliminating right recursion from the grammar.
Also Read- Types of Recursive Grammar
3. General Recursion-
• The recursion which is neither left recursion nor right recursion is called as general
recursion.
Example-
S → aSb / ∈
Problem-01:
Consider the following grammar and eliminate left recursion-
A → ABd / Aa / a
B → Be / b
Solution-
The grammar after eliminating left recursion is-
A → aA’
A’ → BdA’ / aA’ / ∈
B → bB’
B’ → eB’ / ∈
Left Factoring | Left Factoring Examples
Grammar With Common Prefixes-
If RHS of more than one production starts with the same symbol,
then such a grammar is called as
Grammar With Common Prefixes.
Example-
A → αβ1 / αβ2 / αβ3
(Grammar with common prefixes)
• This kind of grammar creates a problematic situation for Top down parsers.
• Top down parsers cannot decide which production must be chosen to parse the string in
hand.
To remove this confusion, we use left factoring.
Left Factoring-
Left factoring is a process by which the grammar with common prefixes is transformed
to make it useful for Top down parsers.
How?
In left factoring,
• We make one production for each common prefixes.
• The common prefix may be a terminal or a non-terminal or a combination of both.
• Rest of the derivation is added by new productions.
The grammar obtained after the process of left factoring is called as Left Factored
Grammar.
Example-
Do left factoring in the following grammar-
S → iEtS / iEtSeS / a
E→b
Solution-
The left factored grammar is-
S → iEtSS’ / a
S’ → eS / ∈
E→b
Relationship Between Left Recursion, Left Factoring &
Ambiguity-
There is no relationship between Left Recursion, Left Factoring and Ambiguity of Grammar.
• All the three concepts are independent and has nothing to do with each other.
• The presence or absence of left recursion does not impact left factoring and ambiguity
anyhow.
• The presence or absence of left factoring does not impact left recursion and ambiguity
anyhow.
• The presence or absence of ambiguity does not impact left recursion and left factoring
anyhow.
