Scribd
Upload
2 views3 pages

Left Recursion Practice

The document provides a practice set for eliminating left recursion in grammar, featuring five problems of increasing difficulty with detailed solutions. It outlines the standard rule for rewriting left-recursive grammar and demonstrates the application of this rule through various examples. Each problem is solved step-by-step, showcasing the identification of recursive and non-recursive parts, and the final grammars are presented clearly.

Uploaded by

Rubayet Sikder
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views3 pages

Left Recursion Practice

The document provides a practice set for eliminating left recursion in grammar, featuring five problems of increasing difficulty with detailed solutions. It outlines the standard rule for rewriting left-recursive grammar and demonstrates the application of this rule through various examples. Each problem is solved step-by-step, showcasing the identification of recursive and non-recursive parts, and the final grammars are presented clearly.

Uploaded by

Rubayet Sikder
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Eliminating Left Recursion — Practice Set

5 problems, ordered by difficulty, with full worked solutions

Reference: The Standard Rule


For a nonterminal A with rules of the form (βi never start with A):

A → A α1 | A α2 | ... | A αm | β1 | β2 | ... | βn

rewrite as:

A → β1 A' | β2 A' | ... | βn A'


A' → α1 A' | α2 A' | ... | αm A' | ε

Problem 1 — Basic direct left recursion


E → E + T | T

Solution
Identify. A = E, with α = + T and β = T (only one alternative for each).

Apply the rule.

E → T E'
E' → + T E' | ε

Problem 2 — Two recursive alternatives


E → E + T | E - T | T

Solution
Identify. A = E, recursive alternatives: α1 = + T, α2 = - T. Non-recursive: β = T.

Apply the rule.

E → T E'
E' → + T E' | - T E' | ε

Problem 3 — Classic expression/term/factor grammar


E → E + T | T
T → T * F | F
F → ( E ) | id

Solution
Identify. Only E and T are left-recursive (F is not, since neither alternative starts with F). Handle each
nonterminal independently since there's no indirect recursion here (F doesn't refer back to E or T on the
left).

Fix E.
E → T E'
E' → + T E' | ε

Fix T.

T → F T'
T' → * F T' | ε

Leave F unchanged.

F → ( E ) | id

Final grammar.

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id

Problem 4 — Multiple recursive AND multiple base alternatives


A → A a | A b | c | d

Solution
Identify. α1 = a, α2 = b (recursive parts). β1 = c, β2 = d (base cases, plugged in for EACH one).

Apply the rule. Every base case βi gets its own A' tacked on:

A → c A' | d A'
A' → a A' | b A' | ε

Common mistake to avoid. Don't write "A → c | d A'" — every base alternative needs the A' appended,
not just the last one.

Problem 5 — Indirect (mutual) left recursion


S → A a | b
A → A c | S d | ε

Solution
Note. S itself isn't left-recursive on the surface, but A → S d lets S reach A again, and A → A c is directly
left-recursive. We need the general (ordered) algorithm, not just the direct-recursion rule.

Step 1 — Order the nonterminals. Take the order S, then A (S is already listed first).

Step 2 — For i = 1 (S): nothing to substitute S has no earlier nonterminal to expand into it. S → A a | b
is left as is (not left-recursive on its own).

Step 3 — For i = 2 (A): substitute S's productions Wherever A's rule begins with S (the earlier
nonterminal), replace S with its right-hand sides:
A → A c | S d | ε
(replace "S d" using S → A a | b)
A → A c | A a d | b d | ε

Step 4 — Now A is directly left-recursive. α1 = c, α2 = a d β1 = b d, β2 = ε. Apply the standard rule:

A → b d A' | A'
A' → c A' | a d A' | ε

Final grammar.

S → A a | b
A → b d A' | A'
A' → c A' | a d A' | ε

You might also like