LL(1) Grammars

LL(1) Grammars

1. What LL(1) Means

LL(1): parse Left-to-right, Leftmost derivation, 1 lookahead token. Grammar is LL(1) iff for every choice A → α | β, the predictor sets are disjoint — parser can decide with one token, no backtracking.

2. FIRST and FOLLOW (must compute in exam)

Set	Meaning	Rules
FIRST(α)	tokens that can start α (+ ε if nullable)	if A → ε, add ε; if A → B C, add FIRST(B) minus ε, plus FIRST(C) if B nullable
FOLLOW(A)	tokens that can follow A	start: $ in FOLLOW(S); if B → α A β, add FIRST(β) minus ε; if β nullable, add FOLLOW(B)

3. LL(1) Condition + Table

For each A → α: predictor = FIRST(α), plus FOLLOW(A) if α ⇒* ε. If two productions of A share any token → not LL(1).

M[A,a] = A → α where a in predictor(A→α); error otherwise

Example:

E → T E' |  E' → + T E' | ε  |  T → F T' | T' → * F T' | ε | F → ( E ) | id
FIRST(E')={+,ε}, FOLLOW(E')={$,)} → table entry M[E',+]=+TE', M[E',$,)]=ε

4. Why Grammars Fail LL(1)

• Left recursion (E → E+T): FIRST loops → eliminate first.
• Common prefix (A → ab | ac): left-factor to A → a A', A' → b|c.
• Ambiguity can never be LL(1).

5. Exam Points

• Compute FIRST/FOLLOW + build LL(1) table — 7-10 marks, most frequent parser question.
• State LL(1) condition and check given grammar — 5 marks, very frequent.
• Eliminate left recursion / left factoring to make LL(1) — 5 marks, frequent.