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

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 nobetaibegins withA, 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 | gammabecomes
A -> alphaA' | gammaandA' -> 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:
Put
$inFOLLOW(S)for start symbolS.For
A -> alphaBbeta, addFIRST(beta) - {epsilon}toFOLLOW(B).If
betais empty or nullable, addFOLLOW(A)toFOLLOW(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) S -> a A(2) S -> b(3) A -> c A(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) = {$}.
|
|
|
|
|
|---|---|---|---|---|
| (1) | (2) |
|
|
|
|
| (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.
|
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.
Keep learning
Top-Down Parsing in Compiler Design: Recursive Descent, LL(1), FIRST and FOLLOW with Worked Examples
Learn top-down parsing from grammar preparation to predictive parsing, with one expression grammar carried through every calculation and trace.
Top-Down Parsing Mistakes in Compiler Design: 7 Errors That Cost GATE Marks
Repair seven common top-down parsing errors by cleaning the grammar, computing sets correctly, building the LL(1) table, and tracing id + id without changing conventions.
Top-Down Parsing in Compiler Design: Parser Basics and a Worked LL(1) Example
Follow one expression grammar from left-recursion removal to a complete LL(1) table. Then trace a valid token stream to acceptance and stop an invalid stream at its first error cell.
Bottom-Up Syntax Analysis Formula Sheet: LR Rules and Worked Trace
Revise bottom-up parsing through compact rules for handles, viable prefixes, LR items and SLR table construction, then follow one consistent grammar from augmentation to acceptance.





