Top-Down Parsing in Compiler Design: Recursive Descent, LL(1), FIRST and FOLLOW with Worked Examples

You may understand syntax analysis in class yet freeze when a GATE question asks whether a grammar is LL(1), or asks for FOLLOW(E'). The difficulty is not one formula. It is connecting grammar preparation, FIRST, FOLLOW, the parsing table, and the stack trace. Each link in that chain is mechanical once you know its rule, and one expression grammar is enough to exercise all five.

Where top-down parsing sits in a compiler

Syntax analysis is the compiler's second phase. The lexer supplies tokens, then the parser checks that token stream against a context-free grammar and builds a parse tree. If that hand-off is unclear, revise Lexical Analysis in Compiler Design: Tokens, Patterns and Lexemes Explained first.

A top-down parser starts at the grammar's start symbol and grows the tree towards the leaves, choosing a production from the next input token. A bottom-up parser starts from the leaves and works towards the root. Parsing in Compiler Design: Top-Down and Bottom-Up Explained compares the two approaches directly.

The top-down family contains:

• recursive descent with backtracking, which tries alternatives;

• predictive recursive descent, which chooses without backtracking;

• table-driven LL(1) parsing.

LL(1) means Left-to-right input scan, Leftmost derivation, and 1 lookahead token.

Fix the grammar first: left recursion and left factoring

A top-down parser cannot directly handle left recursion. With E -> E + T, expanding E produces another E before consuming input, so the parser loops.

Start with:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

The rule A -> A alpha | beta becomes A -> beta A' and A' -> alpha A' | epsilon. For E, alpha = + T and beta = T. Applying the same method to T removes the remaining left recursion:

E  -> T E'
E' -> + T E' | epsilon
T  -> F T'
T' -> * F T' | epsilon
F  -> ( E ) | id

Left factoring solves a different choice problem. For the dangling-else shape:

S -> i E t S | i E t S e S | a

factor the common prefix:

S  -> i E t S S' | a
S' -> e S | epsilon

With one lookahead, the parser cannot choose between alternatives that both begin with i E t S. Factoring postpones the decision until the distinguishing token appears.

FIRST and FOLLOW computed step by step

FIRST tells us which terminal can begin a string derived from a symbol.

1. F -> ( E ) | id, so FIRST(F) = { (, id }.

2. T -> F T', so FIRST(T) = FIRST(F) = { (, id }.

3. E -> T E', so FIRST(E) = FIRST(T) = { (, id }.

4. E' -> + T E' | epsilon, so FIRST(E') = { +, epsilon }.

5. T' -> * F T' | epsilon, so FIRST(T') = { *, epsilon }.

FOLLOW tells us which terminal can appear immediately after a nonterminal.

1. E is the start symbol, so $ enters FOLLOW(E). In F -> ( E ), ) follows E. Therefore FOLLOW(E) = { ), $ }.

2. E' is rightmost in E -> T E', so it receives FOLLOW(E). Thus FOLLOW(E') = { ), $ }.

3. In E -> T E', + enters FOLLOW(T) from FIRST(E') without epsilon. Since E' can vanish, FOLLOW(E) also flows to T. Therefore FOLLOW(T) = { +, ), $ }.

4. T' is rightmost in T -> F T', so FOLLOW(T') = FOLLOW(T) = { +, ), $ }.

5. In T -> F T', * enters FOLLOW(F) from FIRST(T'). Since T' can vanish, FOLLOW(T) also flows to F. Hence FOLLOW(F) = { *, +, ), $ }.

Epsilon never belongs in a FOLLOW set. The $ symbol marks the end of input. Where a right-hand side can vanish, the sets need a second pass before they settle, and First and Follow in Compiler Design: Step-by-Step Computation with Solved GATE Examples works that iteration through a nullable-heavy grammar.

Building the LL(1) predictive parsing table

For every production A -> alpha, place it in M[A, a] for each a in FIRST(alpha). If alpha can derive epsilon, also place it in M[A, b] for every b in FOLLOW(A).

There are exactly 13 filled cells. No cell contains two productions, so the grammar is LL(1). A multiply defined cell is the clash you hunt for when a question asks whether a grammar is LL(1).

Predictive parsing trace for id + id * id

The stack bottom is $, E is pushed first, and the input ends with $. The top of the stack is shown at the right.

The multiplication operator appears deeper in the parse tree than +, so the grammar itself encodes precedence.

Recursive descent, backtracking, and LL(1) failure

Recursive descent uses one function per nonterminal. A predictive version uses the same FIRST and FOLLOW decisions as the table instead of trying alternatives and undoing work. Backtracking can grow exponentially, so production compiler parsers avoid it for this job. Without left factoring, a parser handed S -> i E t S | i E t S e S expands the first alternative, consumes i E t S, meets an unmatched e, then rewinds the input and retries the second.

E():       T(); Eprime()
Eprime():  if lookahead == '+': match('+'); T(); Eprime()
            else if lookahead in {')', '$'}: return
            else: error

Left-recursive grammars, ambiguous grammars, and grammars that need more lookahead are not LL(1). No ambiguous grammar can be LL(1), but a grammar that fails the LL(1) test is not automatically ambiguous.

Left factoring does not always rescue a grammar. The dangling-else shape is genuinely ambiguous, and factoring changes its form without removing that ambiguity. Return to the factored pair:

S  -> i E t S S' | a
S' -> e S | epsilon

S sits immediately before S' in the first production and FIRST(S') contains e, so FOLLOW(S) = { e, $ }, and FOLLOW(S') inherits the same two terminals. Now fill column e for S'. The production S' -> e S belongs there because FIRST(e S) = { e }, and S' -> epsilon belongs there because e is in FOLLOW(S'). Cell M[S', e] therefore holds two productions, so the dangling-else grammar is not LL(1) even after factoring. Compiler writers break that tie by hand, keeping S' -> e S, which is what binds an else to the nearest unmatched if.

How GATE and interviews test top-down parsing

The current GATE syllabus lists syntax analysis under Compiler Design. Check the official GATE office website of the organising IIT for the current syllabus wording and mark distribution.

Typical tasks are compact: compute a set such as FOLLOW(E') = { ), $ }, find a multiply defined table cell, count the filled entries (13 for this grammar), or decide whether to remove left recursion or apply left factoring. Interviews may ask you to hand-write a small recursive-descent parser or explain why left recursion breaks it. Practise the timing of these steps through GATE Test Series: Mocks & Topic-wise Tests after you can trace them on paper.

The short version and your next step

• Remove left recursion and factor shared prefixes.

• Compute FIRST, including epsilon where derivable.

• Compute FOLLOW, never adding epsilon.

• Fill the predictive table from FIRST and FOLLOW.

• Trace the stack. If one table cell receives two productions, the grammar is not LL(1).

To revise this inside the complete compiler flow, use CS Fundamentals for Placements by Sanchit Sir, where compiler design sits alongside the other core CS subjects for placements and GATE. You can also browse further GATE CS Exam Preparation material by subject.