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α / β
(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’ / ∈
(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

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...

Elimination of Left Factoring

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-   PRACTICE PROBLEMS BASED ON LEFT FACTORING- Problem-01: 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 Problem-02: Do left factoring in the following grammar- A → aAB / aBc / aAc Solution- Step-01: A → aA’ A’ → AB / Bc / Ac Again, this is a grammar with common prefixes. Step-02: A → aA’ A’ → AD / Bc D → B / c This is a left factored grammar. Problem-03: Do left factoring in the following grammar- S → bSSaaS / bSSaSb / bSb / a Solution- ...

Testing a Program – An Example

Question: Write a set of test cases – specific set of data – to properly test a relatively Simple program. Create a set of test data for the program - data the program must handle correctly to be considered a successful program. Here’s a description of the program: “The program reads three integer values from an input dialog. The three values represent the lengths of the sides of a triangle. The program displays a message that states whether the triangle is scalene, isosceles, or equilateral”. Code: The function triangle takes three integer parameters that are interpreted as the lengths of the sides of a triangle. It returns whether the triangle is equilateral (three lengths equal), isosceles (two lengths equal), scalene (no lengths equal), or invalid (impossible lengths). Evaluate your test cases: Evaluate your set of test cases by using it to answer the following questions. Give yourself one point for each “YES” answer. Do you have a test case that represents a ...