Top-Down Syntax Analysis Formula Sheet: FIRST, FOLLOW, LL(1) and Predictive Parsing Revision Notes

Revise top-down parsing as one connected workflow, from grammar rewriting and FIRST/FOLLOW sets to an LL(1) table and a complete stack trace.

KnowledgeGate Team

Exam prep & CS education

Updated 2 Nov 20265 min read
Top-Down Syntax Analysis Formula Sheet: FIRST, FOLLOW, LL(1) and Predictive Parsing Revision Notes

Separate rules for left recursion, FIRST, FOLLOW and parsing tables are easy to mix up under exam pressure. Top-down Parsing in Compiler Design develops the broader grammar and table concepts. LL(1) Parser Table Explained works a balanced-parentheses table; the two-level grammar below keeps each lookahead decision small enough to verify before the table is built.

Parsing decisions that determine the table

A top-down parser constructs a parse tree from the start symbol towards the input leaves, producing a leftmost derivation. LL(1) means scan the input Left to right, construct a Leftmost derivation, and use 1 lookahead token.

Recursive descent may backtrack after a failed choice. Predictive parsing chooses one production from the current nonterminal and lookahead without backtracking.

The readiness order is:

remove left recursion -> left-factor when needed -> compute FIRST and FOLLOW -> compute SELECT -> check disjoint SELECT sets -> build the table

Grammar rewriting alone does not prove that the result is LL(1).

For a predictive-parser trace, keep the stack top on the left and append $ to the input. A terminal match pops the terminal and advances the input. For nonterminal A with lookahead a, use M[A, a]. $ against $ accepts.

Grammar-rewrite formula sheet

Immediate left recursion

For A -> Aalpha1 | Aalpha2 | ... | beta1 | beta2 | ..., where no betai begins with A, rewrite:

A -> beta1A' | beta2A' | ...

A' -> alpha1A' | alpha2A' | ... | epsilon

For example, A -> Aa | b becomes A -> bA' and A' -> aA' | epsilon. The original rule can call A again before consuming input, so a recursive-descent procedure may never progress.

For indirect left recursion, order nonterminals A1, A2, ..., An. For each Ai, replace Ai -> Ajgamma, where j < i, by Ai -> delta1gamma | ... | deltakgamma when Aj -> delta1 | ... | deltak. Then remove immediate left recursion from Ai. Substitution order matters.

Left factoring

A -> alphabeta1 | alphabeta2 | gamma

becomes A -> alphaA' | gamma and A' -> beta1 | beta2.

Thus, A -> ab | ac | d becomes A -> aA' | d and A' -> b | c. Left recursion prevents progress. A common prefix prevents a unique choice with one lookahead token.

FIRST, FOLLOW and SELECT rules

Nullable(X) is true when X can derive epsilon. A terminal is not nullable, epsilon is nullable, and a nonterminal is nullable if one right-hand side can derive epsilon.

For X1X2...Xk, add FIRST(X1) - {epsilon}. Continue to each later symbol only while all preceding symbols are nullable. Add epsilon only if every Xi is nullable.

Repeat the FOLLOW rules until no set changes:

  1. Put $ in FOLLOW(S) for start symbol S.

  2. For A -> alphaBbeta, add FIRST(beta) - {epsilon} to FOLLOW(B).

  3. If beta is empty or nullable, add FOLLOW(A) to FOLLOW(B).

For each production:

SELECT(A -> alpha) = FIRST(alpha) - {epsilon}

If epsilon in FIRST(alpha), union FOLLOW(A). The clean LL(1) test for every pair of alternatives is:

SELECT(A -> alphai) intersection SELECT(A -> alphaj) = empty set

It covers both FIRST/FIRST and FIRST/FOLLOW conflicts.

Worked example: a two-level grammar to an LL(1) table

Start with:

S -> a A | b

A -> c A | epsilon

The grammar has no left recursion and no common prefix. Number the productions:

  1. (1) S -> a A

  2. (2) S -> b

  3. (3) A -> c A

  4. (4) A -> epsilon

The FIRST sets are:

  • FIRST(S) = { a, b }

  • FIRST(A) = { c, epsilon }

The FOLLOW sets are:

  • FOLLOW(S) = { $ }

  • FOLLOW(A) = { $ }

For the two S alternatives, SELECT sets are {a} and {b}. For A, the c A alternative uses {c}, while epsilon uses FOLLOW(A) = {$}.

Nonterminal

a

b

c

$

S

(1)

(2)

error

error

A

error

error

(3)

(4)

No cell contains two productions, so the grammar passes the LL(1) table test. Every other cell is an error, not an epsilon entry.

Read the table by lookahead, then trace the same choices on the stack. This keeps grammar repair, set propagation and parser execution as separate checks, so an incorrect entry is easier to locate before an exam attempt.

Predictive-parser trace for a c c $

Use the token stream a c c $. Stack top remains on the left.

Stack

Remaining input

Action

S $

a c c $

use (1)

a A $

a c c $

match a

A $

c c $

use (3)

c A $

c c $

match c

A $

c $

use (3)

c A $

c $

match c

A $

$

use (4)

$

$

accept

Production (3) handles each c, while (4) handles the end marker. The epsilon production pops A without consuming input; only a terminal match advances the input.

Recursive-descent notes from the same grammar

Map one procedure to each nonterminal. S() chooses S -> a A on lookahead a and S -> b on lookahead b. A() chooses A -> c A on c, returns through A -> epsilon on $, and reports an error otherwise.

These guards are the table rows written as control flow. A blank cell means syntax error, not epsilon. A recovery policy may add sync entries, but they are not grammar productions.

GATE-style traps and question forms

Tie each wrong move to its correction:

  • Using only FIRST of the first right-hand-side symbol can miss later nullable symbols. Compute FIRST of the whole string.

  • Placing epsilon in a table column is invalid. Use FOLLOW lookaheads for a nullable production.

  • Adding FOLLOW(A) for a non-nullable right-hand side creates false entries.

  • Leaving left recursion in recursive descent can cause a call without progress.

  • Assuming left factoring guarantees LL(1) skips the SELECT test.

  • Consuming input for an epsilon production shifts the parser incorrectly.

  • Rejecting a grammar because one FIRST set contains epsilon is premature. Check pairwise SELECT intersections.

Question forms can ask you to transform a grammar, find a missing FIRST or FOLLOW member, choose a table entry, locate a conflict, test whether a grammar is LL(1), or determine an action from stack top and lookahead. Here, stack top A with lookahead c selects (3), while stack top A with lookahead b reaches an error cell.

Revision checklist and next step

The order to retain is:

rewrite grammar -> compute Nullable/FIRST -> compute FOLLOW -> compute SELECT -> check pairwise disjointness -> fill M[A,a] -> trace with $

Keep three hooks: left recursion means no progress, left factoring means no unique one-token choice, and a blank table cell means error.

Rebuild the table and trace once without looking. Then change the input to a c $ and predict every production before checking. The Compiler Design learn module is the structured next step, and the Compiler Design course provides the full course route.