Left Recursion Elimination and Left Factoring for GATE: Grammar Transformation Drills

Grammar-transformation questions become messy when two separate problems are treated as one. Left recursion can make a top-down parser recurse forever, while a common prefix can force it to choose a production too early. GATE expects you to recognise each problem and apply the correct mechanical transformation without dropping an epsilon production.

The two are independent. Left recursion is a termination problem: the parser re-enters a rule without consuming any input. A common prefix is a decision problem: the parser must commit before it has read anything that separates the alternatives.

Why top-down parsing needs these transformations

A grammar is immediately left recursive when a nonterminal can derive itself as the first symbol in one step, as in A -> A alpha. A recursive-descent procedure for A calls itself again before consuming any input. The process repeats without making progress.

Left factoring solves a different decision problem. In A -> alpha beta1 | alpha beta2, both alternatives begin with alpha. A predictive parser cannot choose between them while it is still reading that shared prefix.

The remedies are correspondingly different:

• Left-recursion elimination moves recursion away from the left edge.

• Left factoring extracts a common prefix and delays the choice.

Both transformations preserve the language when performed correctly. They improve the grammar's form for top-down parsing, but they do not by themselves prove that the result is LL(1). The contrast worth holding onto is bottom-up: a shift-reduce parser handles left recursion natively and needs neither transformation, as Parsing: Top Down and Bottom Up sets out.

Eliminating immediate left recursion

Start with the simplest form:

A -> A alpha | beta

Here, alpha is the part after the recursive A, and beta is a non-left-recursive alternative. Introduce a fresh nonterminal A':

A -> beta A'

A' -> alpha A' | epsilon

The new A' generates zero or more copies of alpha. The epsilon alternative is what permits zero copies and terminates the recursion. Removing epsilon would require at least one alpha and would change the language.

With several alternatives, separate them into recursive and non-recursive groups:

A -> A alpha1 | A alpha2 | beta1 | beta2

becomes:

A -> beta1 A' | beta2 A'

A' -> alpha1 A' | alpha2 A' | epsilon

Do not carry the leading A into A'. Only the suffix alpha moves there.

Worked elimination on an expression grammar

Consider the familiar grammar:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

For E, the recursive suffix is + T and the non-recursive alternative is T. Therefore:

E  -> T E'
E' -> + T E' | epsilon

For T, the recursive suffix is * F and the non-recursive alternative is F:

T  -> F T'
T' -> * F T' | epsilon

F has no left-recursive alternative, so it remains unchanged:

F -> ( E ) | id

The original grammar has six productions when each alternative is counted separately: two for E, two for T, and two for F. The transformed grammar has eight: one for E, two for E', one for T, two for T', and two for F. Thus 1 + 2 + 1 + 2 + 2 = 8.

The transformed grammar still generates id + id * id, but its recursive calls happen after a term or factor has consumed input. That is the operational reason the change helps a top-down parser.

Indirect left recursion

Immediate left recursion is visible in one production. Indirect left recursion passes through another nonterminal, as in A -> B x and B -> A y. You reveal it by substitution before applying the immediate rule.

Use this general algorithm. Order the nonterminals as A1, A2, ..., An. For each Ai, substitute productions of every earlier Aj wherever an Ai production begins with that Aj. After those substitutions, remove any immediate left recursion in Ai.

Now take:

S -> A a | b
A -> A c | S d | epsilon

Choose the order S, A. S has no immediate left recursion. In the productions for A, replace the leading S in S d using S -> A a | b:

A -> A c | (A a | b) d | epsilon

Distribute the trailing d:

A -> A c | A a d | b d | epsilon

The recursive suffixes are c and a d. The non-recursive alternatives are b d and epsilon. Applying the rule gives:

A  -> b d A' | A'
A' -> c A' | a d A' | epsilon

Why does the second alternative become just A'? The beta there was epsilon, and epsilon A' simplifies to A'. This small simplification is a common multiple-choice trap.

Left factoring a common prefix

Left factoring does not remove recursion. It pulls the longest common prefix out of competing alternatives:

A -> alpha beta1 | alpha beta2

becomes:

A -> alpha A'

A' -> beta1 | beta2

Apply it to the dangling-else grammar:

S -> i E t S | i E t S e S | a

The first two alternatives share the complete prefix i E t S. Factor that prefix, leaving e S in one suffix and epsilon in the other:

S  -> i E t S S' | a
S' -> e S | epsilon

The parser can now consume the shared prefix before deciding whether S' supplies an else part. The factor must be the longest useful common prefix. If the new alternatives still share a prefix, factor again until the decision has actually been delayed.

Traps and GATE question patterns

GATE asks this material in three shapes: transform the grammar and pick the matching option, count the productions after transformation, and judge whether the result is LL(1). All three are decided by the same short list of failure modes:

• Missing epsilon: the fresh recursive nonterminal must be able to stop.

• Only visible recursion removed: indirect recursion requires ordered substitution first.

• Partial factoring: one extraction may expose another shared prefix.

• False LL(1) conclusion: eliminating left recursion and common prefixes is often necessary, but FIRST and FOLLOW conflicts may remain.

• Wrong production count: count each alternative as a separate production, including epsilon.

After transformation, use the process in LL(1) Parsing Table Construction for GATE to test whether table entries conflict. For year-specific question wording and paper details, confirm against the official GATE portal of the organising IIT.

Practice drills with worked answers

Work each one on paper first, then check the count.

Drill 1. Eliminate the immediate left recursion here, then count the productions.

S -> S a | S b | c | d

The recursive suffixes are a and b; the non-recursive alternatives are c and d:

S  -> c S' | d S'
S' -> a S' | b S' | epsilon

Four alternatives become five: two for S and three for S', because epsilon counts as a production of its own.

Drill 2. Left-factor this grammar completely.

A -> a b c | a b d | a e

All three alternatives begin with a, so pull that out first:

A  -> a A'
A' -> b c | b d | e

One pass was not enough. A' still has two alternatives sharing the prefix b, so factor again:

A   -> a A'
A'  -> b A'' | e
A'' -> c | d

Three alternatives become five. Stopping after the first pass is the partial-factoring trap: the parser is left with exactly the decision it could not make.

Drill 3. Remove the indirect left recursion, taking the nonterminals in the order X, Y.

X -> Y a | b
Y -> X c | d

X is processed first and has no immediate left recursion. In Y -> X c, substitute the productions of X:

Y -> (Y a | b) c | d
Y -> Y a c | b c | d

The recursion is now immediate, with suffix a c:

X  -> Y a | b
Y  -> b c Y' | d Y'
Y' -> a c Y' | epsilon

Four alternatives become six. Taking Y first also works; what the ordering guarantees is that every substitution uses a nonterminal already processed.

Short version and next step

For A -> A alpha | beta, write A -> beta A' and A' -> alpha A' | epsilon. For a shared prefix, move the suffix choices to a fresh nonterminal. For indirect recursion, substitute earlier nonterminals first and then apply the immediate rule.

Redo the three drills from a blank page, counting every alternative, then build a parsing table for each result. The GATE Test Series gives timed grammar drills, and the GATE category connects them with the rest of Compiler Design.