A grammar G is LL(1) if and only if the following conditions hold for two…
2014
A grammar G is LL(1) if and only if the following conditions hold for two distinct productions A → α | β
I. FIRST(α) ∩ FIRST(β) ≠ {a} where a is some terminal symbol of the grammar.
II. FIRST(α) ∩ FIRST(β) ≠ λ
III. FIRST(α) ∩ FOLLOW(A) = ϕ if λ ∈ FIRST(β)
- A.
I and II
- B.
I and III
- C.
II and III
- D.
I, II and III
Attempted by 75 students.
Show answer & explanation
Correct answer: D
A grammar is LL(1) iff, for every pair of distinct alternatives A → α | β, three conditions all hold:
1) FIRST(α) and FIRST(β) share no terminal — otherwise the parser cannot decide between α and β on a common lookahead. This is condition I.
2) At most one of α and β can derive the empty string λ; both cannot, or the parser table entry under a single column would collide. This is condition II.
3) If one alternative is nullable (λ ∈ FIRST(β)), then FIRST(α) ∩ FOLLOW(A) must be empty, so the lookahead that follows A is not also a valid start of the non-empty alternative. This is condition III.
All three conditions are necessary and together sufficient for LL(1), so conditions I, II and III must all hold.
A video solution is available for this question — log in and enroll to watch it.