Converting an Arbitrary CFG to an LL(1) Grammar: Correct Option and Why
To convert an arbitrary context-free grammar (CFG) into an grammar (i.e., suitable for predictive parsing), you generally must address two distinct sources of ambiguity in an LL(1) parser:
- Left recursion prevents a top-down parser from making progress when expanding nonterminals (it can cause infinite recursion).
- Left factoring is used to remove cases where the grammar has multiple productions for a nonterminal that can begin with the same prefix, which would otherwise make the next input token insufficient to choose a unique production.
Accordingly, the standard transformation strategy is to remove left recursion and then perform left factoring—which corresponds to option (iii).
A minimal LL(1) suitability idea is: for each nonterminal , the parser should be able to decide which production to use using a single lookahead token. Left recursion and lack of factoring both break this property in typical cases.
Correct answer: (iii) remove left recursion and factor the grammar.
LL(1) Grammar: Left Recursion Removal and Left Factoring
Key terms for this question
- LL(1) grammar
- Left recursion
- Left factoring
- Predictive parsing
Why option (iii) is the right transformation
LL(1) conversion typically needs both: left recursion must be eliminated for termination, and left factoring is needed so the first token (lookahead) uniquely determines the production.
Standard LL(1) conversion workflow (conceptual)
- 1Step 1
Rewrite productions to remove immediate and (where necessary) indirect left recursion so a top-down parser always makes progress.
- 2Step 2
Rewrite productions so alternatives for the same nonterminal don’t share a common prefix; this ensures 1-token lookahead can disambiguate choices.
- 3Step 3
Compute FIRST/FOLLOW sets to check that no parsing conflict remains (e.g., intersections that violate LL(1) decision rules).
FAQ / common misconceptions
Visual reasoning for the multiple-choice prompt
| Option | What it claims | Satisfies LL(1) needs? |
|---|---|---|
| (i) factor the grammar alone | Only resolve prefix ambiguity | No—left recursion may still cause non-termination |
| (ii) remove left recursion alone | Only resolve non-termination | No—lookahead may still be insufficient to choose uniquely |
| (iii) remove left recursion and factor the grammar | Both typical LL(1) blockers | Yes—this matches the standard required transformations in typical LL(1) preparation |
| (iv) None of the above | Denies the above | Incorrect given the standard method |
Which issues are addressed by each option?
Heuristic mapping of transformations to LL(1) blockers.
Knowledge Check
To convert an arbitrary CFG to an LL(1) grammar, which transformation(s) are typically required?