Skip to main content

Eliminating Left 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)

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.

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 / E x E / 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 → T x F / 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.

Comments

Post a Comment

Popular posts from this blog

Code Optimization | Code Optimization Techniques

Code Optimization- Code Optimization is an approach to enhance the performance of the code. The process of code optimization involves- Eliminating the unwanted code lines Rearranging the statements of the code Advantages- The optimized code has the following advantages- Optimized code has faster execution speed. Optimized code utilizes the memory efficiently. Optimized code gives better performance. Code Optimization Techniques- Important code optimization techniques are- Compile Time Evaluation Common sub-expression elimination Dead Code Elimination Code Movement Strength Reduction 1. Compile Time Evaluation- Two techniques that falls under compile time evaluation are- A) Constant Folding- In this technique, As the name suggests, it involves folding the constants. The expressions that contain the operands having constant values at compile time are evaluated. Those express...
Post a Comment
Read more

Grammar in Automata | Types of Grammar

Grammar in Automata- Formal Definition- A Grammar is a 4-tuple such that G = (V , T , P , S) where- V = Finite non-empty set of non-terminal symbols T = Finite set of terminal symbols P = Finite non-empty set of production rules S = Start symbol Grammar Constituents- A Grammar is mainly composed of two basic elements- 1. Terminal symbols 2. Non-terminal symbols 1. Terminal Symbols- Terminal symbols are those which are the constituents of the sentence generated using a grammar. Terminal symbols are denoted by using small case letters such as a, b, c etc. 2. Non-Terminal Symbols- Non-Terminal symbols are those which take part in the generation of the sentence but are not part of it. Non-Terminal symbols are also called as auxiliary symbols or variables . Non-Terminal symbols are denoted by using capital letters such as A, B, C etc. Examples of Grammar- Example-01: Consider a grammar G = (V ...
Post a Comment
Read more

FIRST & FOLLOW Calculation

First Function- First(α) is a set of terminal symbols that begin in strings derived from α. Example- Consider the production rule- A → abc / def / ghi Then, we have- First(A) = { a , d , g } Rules For Calculating First Function- Rule-01: For a production rule X → ∈, First(X) = { ∈ } Rule-02: For any terminal symbol ‘a’, First(a) = { a } Rule-03: For a production rule X → Y1Y2Y3, Calculating First(X) If ∈ ∉ First(Y1), then First(X) = First(Y1) If ∈ ∈ First(Y1), then First(X) = { First(Y1) – ∈ } ∪ First(Y2Y3) Calculating First(Y2Y3) If ∈ ∉ First(Y2), then First(Y2Y3) = First(Y2) If ∈ ∈ First(Y2), then First(Y2Y3) = { First(Y2) – ∈ } ∪ First(Y3) Similarly, we can make expansion for any production rule X → Y1Y2Y3…..Yn. Follow Function- Follow(α) is a set of terminal symbols that appear immediately to the right of...
Post a Comment
Read more