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.

KnowledgeGate Team

Exam prep & CS education

Updated 4 Nov 20265 min read
Top-Down Parsing Mistakes in Compiler Design: 7 Errors That Cost GATE Marks

Students often know the definitions of left recursion, FIRST, FOLLOW and LL(1), yet lose marks by doing the right steps in the wrong order or changing conventions during a trace. These seven repairable errors use exact grammars, sets, table cells and one complete parse of num - num. The accompanying figure keeps the classic id + id epsilon trace visible as a separate visual. Keep the governing sequence fixed: clean the grammar, compute sets to a fixed point, build the table, check conflicts, then trace.

1. Mistake: Building a Predictive Parser Before Removing Left Recursion

Why it happens: A grammar that generates the correct language is assumed to work directly with every parser. What goes wrong: With R -> R - Q | Q, a recursive-descent procedure for R calls itself again before consuming a token. Input such as num - num therefore never advances.

Remove the direct left recursion as R -> Q R', R' -> - Q R' | epsilon, with Q -> num. Now:

R => Q R' => num R' => num - Q R' => num - num R' => num - num

What to do instead: Check every nonterminal for direct and indirect left recursion before computing FIRST or filling a table. Preserve the language while transforming the grammar. Simply deleting the recursive alternative changes the language.

2. Mistake: Treating a Shared Prefix as Two Usable One-Lookahead Choices

Why it happens: The alternatives look different as complete strings, so their identical opening token is missed. What goes wrong: In S -> num := R | num ( L ), both alternatives demand M[S, num]. An LL(1) parser cannot postpone its choice until the second token.

Left-factor the grammar as S -> num X and X -> := R | ( L ). Then M[S, num] = S -> num X. On lookahead :=, choose X -> := R; on lookahead (, choose X -> ( L ).

What to do instead: Compare FIRST sets of complete right-hand sides, extract the longest common prefix, and repeat until one lookahead selects at most one alternative.

3. Mistake: Treating epsilon as an Input Symbol or a Parsing-Table Column

Why it happens: Since epsilon appears in FIRST(R') = {-, epsilon}, it is treated like the terminal -. What goes wrong: Students create an epsilon column, try to match it, or advance the input pointer when applying R' -> epsilon. But epsilon is an empty right-hand side, not a token produced by the lexer.

After both num tokens are matched, the stack is $R' and the input is $. Applying R' -> epsilon changes the stack to $, while the input remains $. Acceptance follows.

What to do instead: Keep epsilon in FIRST sets, never in the input or terminal columns. Applying an epsilon-production pops the nonterminal and consumes no input.

4. Mistake: Stopping FIRST and FOLLOW Before Nullable Information Has Propagated

Why it happens: Sets are guessed in one visual pass, especially when a nullable symbol follows another nonterminal. What goes wrong: In R -> Q R', adding only the immediate follower gives - to FOLLOW(Q) but misses $, although R' can disappear. This omission later removes a valid end-of-input table action.

Compute the sets to a fixed point:

  • FIRST(Q) = {num}

  • FIRST(R') = {-, epsilon}

  • FIRST(R) = {num}

  • Begin with FOLLOW(R) = {$}.

  • From R -> Q R', add - to FOLLOW(Q). Since R' is nullable, also add FOLLOW(R), giving FOLLOW(Q) = {-, $}.

  • Since R' ends the production, FOLLOW(R') = {$}.

Repeat the rules until nothing changes. The Top-down parsing in Compiler Design guide covers the full pipeline and a longer expression trace; this post isolates seven failure patterns and a compact audit.

5. Mistake: Filling the LL(1) Table from the Wrong Set

Why it happens: "Use FIRST" is memorised without noting that FIRST belongs to each right-hand side, while nullable right-hand sides require FOLLOW of the left-hand side. What goes wrong: R' -> epsilon gets omitted, placed under a fictitious epsilon column, or copied under every terminal.

Nonterminal

num

-

$

R

R -> Q R'

error

error

R'

error

R' -> - Q R'

R' -> epsilon

Q

Q -> num

error

error

The remaining five cells are errors. The $ cell receives R' -> epsilon because $ is in FOLLOW(R'), not because it is in FIRST(epsilon). Process each production using FIRST(rhs) - {epsilon}; if epsilon is present, also use FOLLOW(lhs). Then practise with the LL(1) parser and parsing-table solved questions.

6. Mistake: Hiding a Table Conflict by Choosing the First Production

Why it happens: A conflict is mistaken for a list of valid choices. What goes wrong: For S -> a A | a B, A -> c, B -> d, both alternatives enter M[S, a]. Choosing the first hides that the grammar is not LL(1).

Left-factor it to S -> a X, X -> A | B, retaining A -> c and B -> d. The repaired entries are M[S, a] = S -> a X, M[X, c] = X -> A, and M[X, d] = X -> B.

What to do instead: Count entries per cell. Zero means error, one means a choice, and more than one means conflict. Repair or classify the grammar.

7. Mistake: Reversing the Stack or Consuming Input During Expansion

Why it happens: Textbooks use different stack-top conventions, and expansion is confused with terminal matching. What goes wrong: Under a top-at-right convention, pushing symbols in grammar order puts the wrong symbol on top. Advancing input while expanding a nonterminal also skips a token.

For this trace, the stack bottom is left and top is right. Input is num-num$:

Stack

Input

Action

$R

num-num$

R -> Q R'

$R'Q

num-num$

Q -> num

$R'num

num-num$

match num

$R'

-num$

R' -> - Q R'

$R'Q-

-num$

match -

$R'Q

num$

Q -> num

$R'num

num$

match num

$R'

$

R' -> epsilon

$

$

accept

Push a right-hand side so its leftmost symbol is processed next. Expansion changes the stack but never the input. Consume input only when the top terminal matches the lookahead.

Two-panel LL(1) figure showing a predictive table for E, E-prime and T beside a stack, input and action trace for id+id$.

8. The 60-Second Top-Down Parsing Error Audit

Check in this order: remove direct and indirect left recursion; left-factor shared prefixes; compute FIRST with epsilon; propagate FOLLOW to a fixed point; fill cells from FIRST(rhs), using FOLLOW(lhs) for nullable cases; stop at duplicate cells; state stack direction and consume input only on a terminal match. Confirm FOLLOW(Q) = {-, $}, M[R', $] = R' -> epsilon, and final state ($, $).

The short version: grammar first, sets second, table third, trace last. Study systematically with Compiler Design, then use the GATE Test Series for timed practice. Browse Compiler Design learn module for related subjects.