Left recursion elimination in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is left recursion in grammar rules?

Left recursion occurs when a grammar rule refers to itself as the first symbol on the right side, causing potential infinite loops in parsers.

beginner

Why must left recursion be eliminated in top-down parsers?

Because top-down parsers like recursive descent can get stuck in infinite loops when processing left-recursive rules.

intermediate

What is the general approach to eliminate immediate left recursion?

Rewrite the rule A → Aα | β as A → βA' and A' → αA' | ε, where A' is a new rule and ε means empty string.

beginner

What does ε represent in grammar rules after left recursion elimination?

ε represents the empty string, meaning the rule can end without producing any symbol.

intermediate

How is indirect left recursion different from immediate left recursion?

Indirect left recursion happens when a rule refers to another rule that eventually refers back to the first rule on the left side, unlike immediate left recursion which is direct self-reference.

What problem does left recursion cause in top-down parsers?

A Syntax errors

B Infinite recursion or loops

C Memory overflow

D Faster parsing

Left recursion causes the parser to call itself repeatedly without progress, leading to infinite loops.

Which of the following is a correct way to eliminate immediate left recursion from A → Aα | β?

A A → βA' and A' → αA' | ε

B A → Aβ and β → α

C A → αA and A → β

D A → α | β

The standard method introduces a new rule A' to remove left recursion by factoring out the recursive part.

In left recursion elimination, what does the new rule A' typically represent?

A A helper rule to handle repeated patterns

B The original rule unchanged

C A terminal symbol

D An error state

A' is a new rule that helps rewrite the grammar to avoid left recursion by handling repetitions.

What does ε stand for in grammar rules?

A Start symbol

B Error

C End of input

D Empty string

ε means the rule can produce nothing, allowing the parser to stop recursion.

Indirect left recursion involves:

A No recursion at all

B A rule referring to itself directly

C Multiple rules referring back to the original rule

D Only terminal symbols

Indirect left recursion happens when recursion occurs through a chain of rules, not directly.

Explain why left recursion must be eliminated for top-down parsers and describe the general method to remove immediate left recursion.

Think about how recursive calls behave in top-down parsing.

Describe the difference between immediate and indirect left recursion and why indirect left recursion is more complex to eliminate.

Consider how rules refer to each other in a grammar.