FIRST and FOLLOW Sets

E → E + T is left recursive, and a top-down parser expanding it would immediately expand E again, forever. So it is rewritten as E → T E' with E' → + T E' | ε, which derives the same strings without recursing on the left.

The primed non-terminals and their ε-productions are the whole reason FOLLOW sets are needed. Without ε, FIRST alone would determine every move.

The other required rewrite is left factoring: A → αβ | αγ becomes A → αA' with A' → β | γ, so one lookahead token can distinguish the alternatives.

1. 1For a terminal t, FIRST(t) = { t }.
2. 2For A → aα where a is a terminal, add a to FIRST(A).
3. 3For A → Bα, add FIRST(B) minus ε to FIRST(A).
4. 4If B can derive ε, also look past it to α — and if every symbol on the right can derive ε, add ε to FIRST(A).
5. 5Repeat until nothing changes.

Step 4 is where mistakes happen. Only skip past a symbol if it can genuinely vanish.

1. 1Put $ — end of input — in FOLLOW of the start symbol.
2. 2For A → αBβ, add FIRST(β) minus ε to FOLLOW(B).
3. 3For A → αB, or A → αBβ where β can derive ε, add FOLLOW(A) to FOLLOW(B).
4. 4Repeat until nothing changes.

ε is never in a FOLLOW set. FOLLOW holds terminals that actually appear after the non-terminal, and $ counts as one of those.

Both computations are fixed-point iterations: the sets only grow, over a finite alphabet, so they must stabilise. One non-terminal's set can grow after another already looked finished, which is why a single pass is not enough.

For each production A → α: put it in table[A][t] for every terminal t in FIRST(α); and if α can derive ε, also for every t in FOLLOW(A).

That second clause is the entire purpose of FOLLOW — it tells the parser when erasing a non-terminal is the correct move rather than an error.

A grammar is LL(1) exactly when no cell ends up with two productions in it. A conflict means one lookahead token fails to determine the move. The usual causes are left recursion and a common prefix among alternatives, and both have mechanical fixes.