Left recursion elimination in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why is left recursion problematic in top-down parsers?

Consider a top-down parser trying to parse a grammar with left recursion. Why does left recursion cause issues?

A It makes the parser run slower but does not affect correctness.

B It makes the parser skip some input tokens, leading to incorrect parsing.

C It causes the parser to reject all inputs, even valid ones.

D It causes the parser to enter an infinite loop because it keeps expanding the same rule without consuming input.

💡 Hint

Think about what happens when a parser tries to apply a rule that calls itself first.

Left recursion means a rule calls itself as the first step. A top-down parser tries to expand this rule repeatedly without moving forward in the input, causing an infinite loop.

📋 Factual

intermediate

Identify the left-recursive grammar rule

Which of the following grammar rules is left-recursive?

A A → A α | β

B A → β A | α

C A → α β | γ

D A → β | γ α

💡 Hint

Left recursion occurs when the rule's first symbol on the right side is the same as the left side.

Rule A → A α | β is left-recursive because the first symbol on the right side is the same as the left side non-terminal A.

🚀 Application

advanced

Eliminate left recursion from the grammar

Given the grammar rule: A → A α | β, which of the following is the correct equivalent grammar after eliminating left recursion?

A A → β | α A

B A → β A'<br>A' → α A' | ε

C A → β α | A'

D A → α A' | β

💡 Hint

Use the standard left recursion elimination formula: A → β A', A' → α A' | ε

To remove left recursion, we create a new non-terminal A' and rewrite the grammar as A → β A' and A' → α A' | ε, where ε means empty string.

🔍 Analysis

advanced

Determine the number of productions after elimination

Starting with the grammar rule S → S a | S b | c, how many productions will the grammar have after eliminating left recursion?

A 4

B 3

C 2

D 5

💡 Hint

First identify the left recursion, then apply elimination creating a new non-terminal.

The original rule has three productions. After elimination, it becomes S → c S' and S' → a S' | b S' | ε, totaling 4 productions.

❓ Reasoning

expert

Predict parser behavior with indirect left recursion

Consider the grammar:
A → B a | b
B → A c | d
Does this grammar contain left recursion? If yes, what kind?

A Yes, it contains direct left recursion because A calls B and B calls A directly.

B No, it does not contain left recursion because no rule starts with itself directly.

C Yes, it contains indirect left recursion because A calls B and B calls A starting with A again.

D No, it contains right recursion only.

💡 Hint

Check if a non-terminal can eventually call itself as the first symbol on the right side through other rules.

Indirect left recursion occurs when a non-terminal calls another non-terminal which eventually calls the first non-terminal again as the first symbol. Here, A → B a and B → A c form indirect left recursion.