For two distinct productions A → α | β of a grammar G, the grammar is LL(1) if…
2014
For two distinct productions A → α | β of a grammar G, the grammar is LL(1) if and only if the following conditions hold:
I. FIRST(α) ∩ FIRST(β) contains no terminal symbol.
II. ε ∉ FIRST(α) ∩ FIRST(β).
III. FIRST(α) ∩ FOLLOW(A) = ∅ if ε ∈ FIRST(β); symmetrically, FIRST(β) ∩ FOLLOW(A) = ∅ if ε ∈ FIRST(α).
Answer: D. I, II and III — Concept: In an LL(1) grammar, one lookahead symbol must select exactly one production. Therefore the predictive sets of two alternatives for the same…
- A.
I and II
- B.
I and III
- C.
II and III
- D.
I, II and III
Attempted by 228 students.
Show answer & explanation
Correct answer: D
Concept: In an LL(1) grammar, one lookahead symbol must select exactly one production. Therefore the predictive sets of two alternatives for the same nonterminal must be disjoint.
For A → α | β, shared terminal symbols cause a parsing-table conflict. Both alternatives also cannot derive ε; if either alternative derives ε, the other alternative’s FIRST set must be disjoint from FOLLOW(A).
Application:
The terminal-disjointness condition prevents FIRST(α) and FIRST(β) from sharing a terminal symbol.
The ε-exclusion condition prevents α and β from both deriving ε.
The nullable-alternative condition requires FIRST(α) ∩ FOLLOW(A) = ∅ when ε ∈ FIRST(β), and symmetrically FIRST(β) ∩ FOLLOW(A) = ∅ when ε ∈ FIRST(α).
Cross-check: If a terminal appeared in both FIRST sets, or if a nullable alternative overlapped FOLLOW(A), the LL(1) table would place two productions in one cell. The three conditions prevent those conflicts.
Result: Terminal disjointness, exclusion of shared ε, and the nullable-alternative FOLLOW condition are all required.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2