Top-Down Parsing in Compiler Design: Parser Basics and a Worked LL(1) Example

A grammar may look simple, yet a parser must choose one production from the next token and reject a string at the first impossible move. One minimal expression grammar exposes decisions from left-recursion removal through FIRST and FOLLOW, four LL(1) table entries, acceptance of id + id $, and rejection of id + + id $ at M[T,+]. The compilation pipeline starts with lexical analysis and continues through parsing, semantic analysis, intermediate-code generation, optimisation, and code generation; Compiler Design connects those stages.

Related reading: FIRST and FOLLOW and predictive parsing tables.

Parser basics: from tokens to a syntax tree

A parser is the syntax-analysis stage. It consumes the token stream from lexical analysis and checks whether a context-free grammar can generate it. In id + id $, id and + are terminals, E, E', and T are non-terminals, and $ is the end marker, not a source-language token.

The grammar states legal structure. A derivation lists production applications, a parse tree records their hierarchy, and the algorithm chooses a production or reports an error. The parser neither rescans characters nor assigns runtime values.

Top-down parsing expands from the start symbol until the leaves match the input, constructing a leftmost derivation here. Bottom-up parsing reduces the input towards the start symbol.

Recursive descent, predictive parsing and grammar conditions

A recursive-descent parser has one procedure per non-terminal and may backtrack. A predictive parser selects a production using one lookahead token, so the terms are not synonymous.

This expression grammar breaks a naive top-down procedure:

E -> E + T | T
T -> id

Choosing E -> E + T makes parseE() recurse before consuming a token. Remove the left recursion and number the result:

(1) E  -> T E'
(2) E' -> + T E'
(3) E' -> epsilon
(4) T  -> id

This grammar generates id (+ id)*, including id, id + id, and id + id + id.

Left factoring repairs another problem. Factor S -> id ( E ) | id = E as S -> id R and R -> ( E ) | = E. Left-recursion removal prevents looping; factoring delays the choice. Neither guarantees LL(1), which still needs a conflict-free table.

FIRST and FOLLOW for the worked grammar

From T -> id, FIRST(T) = {id}. Since E -> T E', FIRST(E) = {id}. The two alternatives for E' give FIRST(E') = {+, epsilon}.

Put $ in FOLLOW(E) because E is the start symbol. Since E' ends production (1), copy FOLLOW(E) to FOLLOW(E'). For T in E -> T E', add FIRST(E') - {epsilon} = {+}. Because E' can vanish, also add FOLLOW(E) = {$}.

FIRST(E)   = {id}
FIRST(E')  = {+, epsilon}
FIRST(T)   = {id}
FOLLOW(E)  = {$}
FOLLOW(E') = {$}
FOLLOW(T)  = {+, $}

The larger grammar in First and Follow in Compiler Design: Solved Examples demonstrates fixed-point propagation across nullable chains. In this grammar, epsilon belongs to FIRST, while FOLLOW(E') tells the table when to select production (3).

LL(1) table construction, cell by cell

For A -> alpha, place the production under each non-epsilon terminal in FIRST(alpha). If alpha can derive epsilon, also use every symbol in FOLLOW(A). One production per cell is deterministic; multiple productions form a conflict, so that grammar form is not LL(1). With only id, +, and $, the table exposes the entire chain from left-recursion repair to an acceptance trace and a rejection cell.

M[E,id]=1 comes from FIRST(T E')={id}. The leading + gives M[E',+]=2. Since $ is in FOLLOW(E'), epsilon gives M[E',$]=3. FIRST(id)={id} gives M[T,id]=4. No cell has two productions, so the grammar is LL(1).

Every LL(1) grammar is unambiguous. A non-LL(1) grammar is not automatically ambiguous or impossible to parse another way.

Parse id + id $ from the stack to acceptance

Write the stack top at the right and start with $ E. Pop a selected non-terminal and push its right-hand side in reverse. A terminal match pops and advances; epsilon pushes and consumes nothing.

The leftmost derivation is E => T E' => id E' => id + T E' => id + id E' => id + id. The tree leaves are id, +, id, epsilon. Epsilon is not an input token; $ remains the end marker.

Top-down parsing rejection and common traps

For id + + id $, the steps through the first id and + are unchanged. Stack $ E' T then faces input + id $. Its top is T, but M[T,+]=error, so reject at the second +. Never delete it or choose T -> id against the table.

Verify grammar repairs with id, id + id, and id + id + id. Failure here only means another grammar or parsing method may be needed.

How practice questions test top-down parsing

Typical practice tasks ask you to identify a top-down parser or leftmost derivation, repair a grammar, compute sets, fill a cell, locate a conflict, trace a string, or find the first error cell. Each task tests a distinct decision: grammar suitability, set propagation, table determinism, stack order, or rejection.

Rapid top-down parsing checks test FIRST/FOLLOW calculations, table entries, stack order, and rejection.

1. FIRST(E')={+,epsilon} because its alternatives start with + or vanish.

2. FOLLOW(T)={+,$} because E' may begin with + or vanish at the end of E.

3. M[E',$]=3 because production (3) is epsilon and $ follows E'.

4. Production (2) is selected on + because its right-hand side begins with +.

5. After expanding E -> T E', stack $ E' T has T on top.

6. id + + id $ fails in M[T,+] because T can begin only with id.

Normalise the grammar, complete FIRST, stabilise FOLLOW, fill the table, check for multiple productions in any cell, and only then trace the input.

Top-down parsing: the short version and next step

Recall the chain: tokens -> grammar repair -> FIRST/FOLLOW -> LL(1) table -> stack trace -> accept or error. Here its decisive entries are M[E,id]=1, M[T,id]=4, M[E',+]=2, and M[E',$]=3.

As a retrieval exercise, trace id $. The sequence is p1, p4, match id, p3, accept; after matching id, lookahead $ selects E' -> epsilon. In contrast, + id $ fails immediately because M[E,+]=error.

Choose Zero to Hero for broad core-CS learning, GATE Guidance by Sanchit Sir for structured GATE preparation, or browse related topics in the CS Fundamentals category. Rebuild this table without looking and trace one valid and one invalid string.