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 IIIConcept: In an LL(1) grammar, one lookahead symbol must select exactly one production. Therefore the predictive sets of two alternatives for the same…

  1. A.

    I and II

  2. B.

    I and III

  3. C.

    II and III

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

Loading lesson…