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(β)

  1. A.

    I and II

  2. B.

    I and III

  3. C.

    II and III

  4. 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.

Explore the full course: Mppsc Assistant Professor