The method

FIRST sets

FIRST(X) is the set of terminals that can begin a string derived from X. If X can derive the empty string, ε is in FIRST(X) too.

1. FIRST rule 1

   a terminal is its own FIRST set.

2. FIRST rule 2

   for A → X…, add FIRST(X) minus ε.

3. FIRST rule 3

   if every symbol on the right is nullable, add ε.

Rule 2 is the one people get wrong: you take FIRST of the next symbol minus ε, and you only move on to the symbol after it if the current one is nullable.

FOLLOW sets

FOLLOW(A) is the set of terminals that can appear immediately after A in some derivation. It is about the grammar as a whole, not about A's own productions.

1. FOLLOW rule 1

   the start symbol is followed by $.

2. FOLLOW rule 2

   for A → α B β, add FIRST(β) minus ε to FOLLOW(B).

3. FOLLOW rule 3

   for A → α B, or A → α B β with β nullable, add FOLLOW(A) to FOLLOW(B).

Rule 3 catches the case people miss: if A is at the end of a production, or everything after it can vanish, then whatever follows the head also follows A.

The parse table

The table says which production to apply given a non-terminal on the stack and one terminal of lookahead.

1. Table rule 1

   put A → α under every terminal in FIRST(α).

2. Table rule 2

   if α is nullable, put A → α under every terminal in FOLLOW(A).

A cell with two productions means one token of lookahead is not enough to choose, and the grammar is not LL(1).

Why a grammar fails to be LL(1)

Left recursion

E → E + T means the parser would expand E to E forever without consuming a token. No left-recursive grammar is LL(1); rewrite it as E → T E' with E' → + T E' | ε first.

A FIRST/FIRST clash

Two alternatives begin with the same terminal, as in S → a b | a c. Left-factor them into S → a S' with S' → b | c.

A FIRST/FOLLOW clash

A nullable non-terminal can start with the same terminal that can follow it, so the parser cannot tell whether to expand it or skip past it. The dangling-else grammar is the standard example.

Try each of these in the workbench — the example picker has a left-recursive grammar and a dangling-else grammar ready to load.