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.

Also Read- Ambiguous 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.

To gain better understanding about Recursive Grammar

Some of the important differences between ambiguous grammar and unambiguous
grammar are-

Ambiguous Grammar Unambiguous Grammar

A grammar is said to be ambiguous if for at A grammar is said to be unambiguous if for all

least one string generated by it, it produces the strings generated by it, it produces exactly
more than one- one-
 parse tree
 parse tree
 or derivation tree
 or derivation tree
 or syntax tree
 or syntax tree
 or leftmost derivation
 or leftmost derivation
 or rightmost derivation
 or rightmost derivation

For ambiguous grammar, leftmost derivation For unambiguous grammar, leftmost

and rightmost derivation represents different derivation and rightmost derivation represents
parse trees. the same parse tree.

Ambiguous grammar contains less number of Unambiguous grammar contains more

non-terminals. number of non-terminals.

For ambiguous grammar, length of parse tree For unambiguous grammar, length of parse
is less. tree is large.

Ambiguous grammar is faster than

unambiguous grammar in the derivation of a Unambiguous grammar is slower than
tree. ambiguous grammar in the derivation of a
(Reason is above 2 points) tree.
 Example-
Example-
E → E + E / E x E / id E→E+T/T
(Ambiguous Grammar) T→TxF/F

General Approach To Check Grammar Ambiguity-

To check whether a given grammar is ambiguous or not, we follow the following steps-

Step-01:

We try finding a string from the Language of Grammar such that for the string there exists
more than one-
 parse tree
 or derivation tree
 or syntax tree
 or leftmost derivation
 or rightmost derivation

Step-02:

If there exists at least one such string, then the grammar is ambiguous otherwise
unambiguous.

PROBLEMS BASED ON CHECKING WHETHER

GRAMMAR IS AMBIGUOUS-

Problem-01:

Check whether the given grammar is ambiguous or not-

S → SS
 S→a
S→b

Solution-

Let us consider a string w generated by the given grammar-

w = abba
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-02:

Check whether the given grammar is ambiguous or not-

 S→A/B
A → aAb / ab
B → abB / ∈

Solution-

Let us consider a string w generated by the given grammar-

w = ab
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-03:

Check whether the given grammar is ambiguous or not-

S → AB / C
A → aAb / ab
B → cBd / cd
 C → aCd / aDd
D → bDc / bc

Solution-

Let us consider a string w generated by the given grammar-

w = aabbccdd
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-04:
Check whether the given grammar is ambiguous or not-
S → AB / aaB
A → a / Aa
B→b

Solution-

Let us consider a string w generated by the given grammar-

w = aab
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-05:

Check whether the given grammar is ambiguous or not-

S → a / abSb / aAb
 A → bS / aAAb

Solution-

Let us consider a string w generated by the given grammar-

w = abababb
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-06:

Check whether the given grammar is ambiguous or not-

E→E+T/T
T→TxF/F
 F → id

Solution-

 There exists no string belonging to the language of grammar which has more than one
parse tree.
 Since a unique parse tree exists for all the strings, therefore the given grammar is
unambiguous.

Problem-07:

Check whether the given grammar is ambiguous or not-

S → aSbS / bSaS / ∈

Solution-

Let us consider a string w generated by the given grammar-

w = abab
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-08:

Check whether the given grammar is ambiguous or not-

R → R + R / R . R / R* / a / b

Solution-

Let us consider a string w generated by the given grammar-

w = ab + a
Now, let us draw parse trees for this string w.
 Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

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 / ∈

PRACTICE PROBLEMS BASED ON LEFT RECURSION

ELIMINATION-

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’ / ∈

Problem-02:

Consider the following grammar and eliminate left recursion-

E→E+E/ExE/a

Solution-

The grammar after eliminating left recursion is-

E → aA

A → +EA / xEA / ∈

Problem-03:

Consider the following grammar and eliminate left recursion-

E→E+T/T
T→TxF/F
F → id

Solution-
The grammar after eliminating left recursion is-
E → TE’

E’ → +TE’ / ∈
T → FT’

T’ → xFT’ / ∈
F → id

Problem-04:

Consider the following grammar and eliminate left recursion-

S → (L) / a
L→L,S/S

Solution-

The grammar after eliminating left recursion is-

S → (L) / a
L → SL’

L’ → ,SL’ / ∈

Problem-05:

Consider the following grammar and eliminate left recursion-

S → S0S1S / 01

Solution-

The grammar after eliminating left recursion is-

S → 01A

A → 0S1SA / ∈
Problem-06:

Consider the following grammar and eliminate left recursion-

S→A
A → Ad / Ae / aB / ac
B → bBc / f

Solution-

The grammar after eliminating left recursion is-

S→A
A → aBA’ / acA’

A’ → dA’ / eA’ / ∈
B → bBc / f

Problem-07:

Consider the following grammar and eliminate left recursion-

A → AAα / β

Solution-

The grammar after eliminating left recursion is-

A → βA’

A’ → AαA’ / ∈

Problem-08:

Consider the following grammar and eliminate left recursion-

 A → Ba / Aa / c
B → Bb / Ab / d

Solution-

This is a case of indirect left recursion.

Step-01:

First let us eliminate left recursion from A → Ba / Aa / c

Eliminating left recursion from here, we get-

A → BaA’ / cA’

A’ → aA’ / ∈

Now, given grammar becomes-

A → BaA’ / cA’

A’ → aA’ / ∈
B → Bb / Ab / d

Step-02:

Substituting the productions of A in B → Ab, we get the following grammar-

A → BaA’ / cA’

A’ → aA’ / ∈
B → Bb / BaA’b / cA’b / d

Step-03:
Now, eliminating left recursion from the productions of B, we get the following grammar-
A → BaA’ / cA’

A’ → aA’ / ∈
B → cA’bB’ / dB’

B’ → bB’ / aA’bB’ / ∈

This is the final grammar after eliminating left recursion.

Problem-09:

Consider the following grammar and eliminate left recursion-

X → XSb / Sa / b
S → Sb / Xa / a

Solution-

This is a case of indirect left recursion.

Step-01:

First let us eliminate left recursion from X → XSb / Sa / b

Eliminating left recursion from here, we get-

X → SaX’ / bX’

X’ → SbX’ / ∈

Now, given grammar becomes-

X → SaX’ / bX’

X’ → SbX’ / ∈
S → Sb / Xa / a
Step-02:

Substituting the productions of X in S → Xa, we get the following grammar-

X → SaX’ / bX’

X’ → SbX’ / ∈
S → Sb / SaX’a / bX’a / a

Step-03:

Now, eliminating left recursion from the productions of S, we get the following grammar-
X → SaX’ / bX’

X’ → SbX’ / ∈
S → bX’aS’ / aS’

S’ → bS’ / aX’aS’ / ∈

This is the final grammar after eliminating left recursion.

Problem-10:

Consider the following grammar and eliminate left recursion-

S → Aa / b

A → Ac / Sd / ∈

Solution-

This is a case of indirect left recursion.

Step-01:
 First let us eliminate left recursion from S → Aa / b
This is already free from left recursion.

Step-02:

Substituting the productions of S in A → Sd, we get the following grammar-

S → Aa / b

A → Ac / Aad / bd / ∈

Step-03:

Now, eliminating left recursion from the productions of A, we get the following grammar-
S → Aa / b
A → bdA’ / A’

A’ → cA’ / adA’ / ∈

This is the final grammar after eliminating left recursion

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-