Derivation and Recursion in CFG: Leftmost, Rightmost and Worked Examples

A grammar rule fits on one line, but a derivation question can still make you pause: which nonterminal may be rewritten, in what order, and when has the process actually finished? Recursion adds another trap, because a valid CFG can support finite strings while a careless derivation or parser keeps expanding forever. Exact strings distinguish the ideas; use GATE CS Exam Preparation as the wider subject route when placing them in your full plan.

CFG derivation: grammar, sentential form and sentence

A context-free grammar is G = (V, Σ, P, S), where V contains nonterminals, Σ contains terminals, P contains productions, and S is the start symbol. Use this grammar:

• V = {S, A, B}

• Σ = {a, b}

• Start symbol: S

• Productions: S -> AB, A -> aA | a, B -> bB | b

The symbol => means one application; =>* means zero or more. A sentential form may contain terminals and nonterminals, so aAB and aaB qualify. A sentence contains terminals only, so aabbb is a sentence.

This grammar generates exactly {a^m b^n | m >= 1, n >= 1}. Every sentence has at least one a, followed by at least one b. For the wider connection between grammars, languages and stack machines, read Context-Free Grammars and Pushdown Automata.

Leftmost derivation: derive aabbb step by step

In a leftmost derivation, always rewrite the leftmost nonterminal in the current sentential form.

1. S => AB (S -> AB)

2. AB => aAB (A -> aA)

3. aAB => aaB (A -> a)

4. aaB => aabB (B -> bB)

5. aabB => aabbB (B -> bB)

6. aabbB => aabbb (B -> b)

The result has two a symbols, three b symbols and no nonterminal. It is a sentence reached in six applications. While both A and B remain, the leftmost rule forces us to finish A before touching B.

Rightmost derivation: same string, different rewrite order

Now always rewrite the rightmost nonterminal:

1. S => AB (S -> AB)

2. AB => AbB (B -> bB)

3. AbB => AbbB (B -> bB)

4. AbbB => Abbb (B -> b)

5. Abbb => aAbbb (A -> aA)

6. aAbbb => aabbb (A -> a)

The two orders can be compared directly:

Both start at S, end at aabbb, and take six applications. The same production choices give the same parse tree. Having a leftmost and a rightmost sequence does not prove ambiguity. That requires two distinct parse trees, equivalently two distinct leftmost or two distinct rightmost derivations for one string.

Recursive grammar rules: direct, indirect, left and right recursion

The rule A -> aA | a has direct right recursion and a base. Choosing recursion twice and then the base gives A => aA => aaA => aaa. Choosing A -> aA forever produces no finite sentence because A never disappears.

The rule E -> E + T | T has direct left recursion because E immediately returns as the leftmost symbol. Recursion can also be indirect. With A -> Bc and B -> Ad | b, the sequence A => Bc => Adc returns to A in the leftmost position after two steps.

Recursion is a grammar property. Non-termination is derivation or parser behaviour. A base alternative permits finite strings. Left recursion is valid in a CFG, but naive recursive descent can call itself without consuming input.

Left-recursion removal: derive id+id+id

Start with E -> E + T | T and T -> id. Removing immediate left recursion gives:

• E -> T E'

• E' -> + T E' | ε

• T -> id

Both grammars generate one or more id tokens separated by +, although their parse-tree shapes differ. Under the transformed grammar:

1. E => T E' (E -> T E')

2. T E' => id E' (T -> id)

3. id E' => id + T E' (E' -> + T E')

4. id + T E' => id + id E' (T -> id)

5. id + id E' => id + id + T E' (E' -> + T E')

6. id + id + T E' => id + id + id E' (T -> id)

7. id + id + id E' => id + id + id (E' -> ε)

The terminal string takes seven applications, including the final epsilon production. The transformation supports top-down parsing; Parsing in Compiler Design: Top-Down and Bottom-Up Explained continues from that purpose.

Derivation and recursion traps that lose marks

Two boundary cases clarify termination. X -> xX generates no finite terminal sentence because every step leaves X. In contrast, X -> xX | ε generates {x^n | n >= 0}, including the empty string when epsilon is chosen immediately.

Left-recursion removal preserves the generated language, not the original parse-tree shape. If semantic actions or associativity depend on that old tree, they must be adjusted deliberately during the transformation.

Derivation and recursion exam patterns: what to practise

Common checks ask you to identify derivation order, fill a missing sentential form, count applications, test membership, distinguish direct from indirect recursion, or remove immediate left recursion.

Try two rapid checks with the first grammar:

• aaab is generated. After S -> AB, use A -> aA twice, A -> a once and B -> b once. Including the start production, that is five applications.

• ba is impossible. Every generated sentence places all a symbols before all b symbols.

KnowledgeGate has about 10 live practice questions on Derivation & Recursion. Once you can reproduce both six-step derivations without notes, use the GATE Test Series for mixed practice.

Derivation and recursion: the short version and next step

• Begin at S.

• Rewrite exactly one nonterminal per arrow.

• Obey the named leftmost or rightmost order.

• Stop only when terminals remain.

• For a finite sentence, confirm that every recursive path has a terminating alternative.

Keep two anchors in memory: aabbb takes six applications in either derivation order, while transformed id+id+id takes seven, including E' -> ε. For a structured route through the wider Compiler Design sequence, continue with GATE Guidance by Sanchit Sir. If you need practice rather than teaching, the test series is the focused alternative.