We now have all the ingredients for our first real parser. From Syntax Analysis & Context-Free Grammars we know what a parse tree is; from Ambiguity, Left Recursion & Left Factoring we know how to prepare a grammar; and from FIRST & FOLLOW Sets we know which tokens can start or follow each part of the grammar.
This chapter covers top-down parsing, the approach most people would invent on their own: start with the start symbol and try to grow the parse tree downwards until its leaves match the input. We look at two styles:
Recursive descent with backtracking: try the alternatives one by one, and undo when a choice turns out wrong. Simple, general, but slow and fragile.
Predictive recursive descent: look at the next token and pick the right alternative immediately, with no backtracking. This is what real hand-written parsers, including the ones in GCC and Clang, do.
We will finish with a complete recursive descent parser and calculator in C. It was compiled with gcc and all outputs shown are from real runs.
The Idea of Top-Down Parsing
A top-down parser constructs the parse tree for the input starting from the root (the start symbol) and creating nodes in preorder, so that it traces a leftmost derivation of the input.
At every step, the parser has a partly built tree. Its leaves, read left to right, are:
terminals that have already been matched against the input, followed by
the leftmost non-terminal that still needs to be expanded, and whatever comes after it.
The one key decision is: which production should be used to expand the leftmost non-terminal? Once that is chosen, the terminals at the start of the right side must match the next input tokens. Everything about top-down parsing comes down to how this decision is made.
A Small Picture
With the expression grammar (left recursion removed)
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | ida top-down parse of id + id grows the tree like this. Each row is one leftmost derivation step:
Step | Sentential form (matched part | rest) | Next token | Decision |
|---|---|---|---|
1 | | E | id | E → T E' (only choice) |
2 | | T E' | id | T → F T' (only choice) |
3 | | F T' E' | id | F → id (because the token is id, not |
4 | id | T' E' | + | T' → ε (+ is not *, and + ∈ FOLLOW(T')) |
5 | id | E' | + | E' → + T E' |
6 | id + | T E' | id | T → F T' |
7 | id + | F T' E' | id | F → id |
8 | id + id | T' E' | $ | T' → ε ($ ∈ FOLLOW(T')) |
9 | id + id | E' | $ | E' → ε ($ ∈ FOLLOW(E')) |
10 | id + id | | $ | Accept |
Every decision here was made by looking at a single token, using exactly the FIRST and FOLLOW sets from the previous chapter. That is the goal. But first, let's see what happens when the grammar does not allow such easy decisions.
Recursive Descent Parsing
A recursive descent parser consists of one procedure for each non-terminal. The procedure for A chooses a production A → X1X2...Xk and then processes its symbols in order: for a non-terminal Xi it calls the procedure for Xi, and for a terminal Xi it checks that the next input token equals Xi and advances.
The call stack of the program plays the role of the parse tree: when the procedure for T is running inside the procedure for E, we are building a T node below an E node. Parsing starts by calling the procedure for the start symbol, and succeeds if it returns having consumed the whole input.
In general form:
procedure A():
choose an A-production A → X1 X2 ... Xk
for i = 1 to k:
if Xi is a non-terminal: call Xi()
else if Xi == current input token: advance to the next token
else: an error has occurred (or: backtrack and try another choice)The word "choose" hides the whole problem. There are two ways to make that choice.
Recursive Descent with Backtracking
The simplest strategy is to try the alternatives in order. If one fails, reset the input pointer to where it was when the procedure started and try the next one. If all fail, report failure to the caller, which may then try its next alternative.
Worked Example: Trying, Failing, and Trying Again
S → x A y
A → p q | pInput: x p y. Here is the full trace of a backtracking parser (positions count tokens from 0):
try S → x A y at 0
match x at 0
try A → p q at 1
match p at 1
q expected at 2, found y → fail
backtrack out of A → p q (input pointer goes back to 1)
try A → p at 1
match p at 1
match y at 2
accept After the first try of A After backtracking
S S
/ | \ / | \
x A y x A y
/ \ |
p q ✗ (input has y) p ✓The parser built part of a tree, discovered a mismatch, threw that subtree away, and rebuilt it differently.
Why Backtracking Is a Bad Idea in Practice
It can take exponential time. Every failure may re-parse the same input with other combinations of choices, and the combinations multiply with nesting.
It is hard to undo side effects. If a procedure already inserted a name into the symbol table or generated code before failing, all of that must be rolled back.
Error messages are poor. When every alternative fails, the parser does not know which failure was the "real" error, so it can only say "syntax error" somewhere.
It still loops forever on left recursion, exactly as described in the previous chapter.
The Trap of Partial Backtracking
Many hand-written backtracking parsers take a shortcut: inside a procedure, they try alternatives until one succeeds, and then return and never reconsider that choice. That is cheaper, but it is not equivalent to full backtracking. Consider:
S → A c
A → a | a bInput a b c. The procedure for A tries A → a, which succeeds after matching a, and returns. S then expects c but finds b. A full backtracking parser would go back into A and try A → a b, then match c and accept. The "commit to the first success" parser cannot re-enter A, so it wrongly rejects a valid string. We ran both strategies: full backtracking accepts, commit-first rejects.
Putting the longer alternative first (A → a b | a) fixes this particular input, but not in general. With S → A b, A → a b | a and input a b, A now greedily takes a b, S finds no b left, and the commit-first parser rejects again, while full backtracking accepts by going back to A → a.
The real fix is not to guess at all. Left-factoring A → a | a b into A → a A', A' → b | ε and then deciding A' by the next token gives a parser that never needs to undo anything.
Predictive Parsing: Recursive Descent without Backtracking
A predictive parser is a recursive descent parser that chooses the production for a non-terminal by looking at the next input token (the lookahead) only, and never backtracks.
For this to work, at most one alternative must be possible for each lookahead token. Using the previous chapter's sets, the procedure for A, with productions A → α1 | α2 | ... , chooses:
αi if the lookahead is in FIRST(αi);
the nullable alternative (for example A → ε) if the lookahead is in FOLLOW(A);
otherwise, it reports a syntax error right away.
So the grammar must satisfy, for every pair of alternatives of every non-terminal: their FIRST sets are disjoint; at most one of them is nullable; and if one is nullable, the FIRST sets of the others are disjoint from FOLLOW(A). These are exactly the conditions for a grammar to be LL(1). The table-driven version of this parser and the formal test are covered in the next chapter, LL(1) Parsing.
A grammar that is ambiguous or left-recursive can never satisfy these conditions, which is why we removed ambiguity and left recursion and applied left factoring before getting here.
Turning the Grammar into Procedures
For the expression grammar, the decision for each non-terminal is:
Procedure | Lookahead | Action |
|---|---|---|
E | ( or id | T(); E'() |
E' | + | match(+); T(); E'() |
E' | ) or $ (FOLLOW(E')) | do nothing (E' → ε) |
T | ( or id | F(); T'() |
T' | * | match(*); F(); T'() |
T' | +, ) or $ (FOLLOW(T')) | do nothing (T' → ε) |
F | ( | match((); E(); match()) |
F | id | match(id) |
any | anything else | syntax error |
Many real parsers simplify the ε case to "if the lookahead is not +, choose ε" and let the caller detect any error a moment later. That is still correct (errors are still caught before any wrong token is consumed), just slightly less precise in its error messages.
A Complete Recursive Descent Parser in C
Let's write the parser for real, for integers with + - * / and parentheses. Each procedure also computes the value of what it parsed, so the program is a small calculator. The grammar:
E → T E' E' → + T E' | - T E' | ε
T → F T' T' → * F T' | / F T' | ε
F → ( E ) | numOne subtlety: E' and T' must know the value computed so far, so that 8 - 3 - 2 is computed as (8 − 3) − 2. We pass it in as a parameter left. (This is the "inherited attribute" trick mentioned in the previous chapter; the syntax-directed translation chapters formalize it.)
/* rd.c : recursive descent parser and evaluator for
* E -> T E' E' -> + T E' | - T E' | eps
* T -> F T' T' -> * F T' | / F T' | eps
* F -> ( E ) | num
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
static const char *src; /* input text */
static int pos; /* current position in src */
static int tokstart; /* where the lookahead begins */
static int tok; /* lookahead: '+', '(', 'n' (number), '$' (end) ... */
static long tokval; /* value when tok == 'n' */
static int depth; /* for the trace */
static int tracing;
static void next(void) { /* a tiny lexer */
while (src[pos] == ' ') pos++;
tokstart = pos;
if (src[pos] == '\0') { tok = '$'; return; }
if (isdigit((unsigned char)src[pos])) {
tokval = 0;
while (isdigit((unsigned char)src[pos])) tokval = tokval * 10 + (src[pos++] - '0');
tok = 'n';
return;
}
tok = src[pos++];
}
static void error(const char *expected) {
printf("syntax error at column %d: expected %s, found ", tokstart + 1, expected);
if (tok == '$') printf("end of input\n");
else if (tok == 'n') printf("number %ld\n", tokval);
else printf("'%c'\n", tok);
exit(1);
}
static void enter(const char *name) {
if (!tracing) return;
printf("%*s%s (lookahead ", 2 * depth, "", name);
if (tok == 'n') printf("num %ld)\n", tokval); else printf("'%c')\n", tok);
depth++;
}
static void leave(void) { if (tracing) depth--; }
static void match(int t) {
if (tok == t) next();
else { char e[4] = { '\'', (char)t, '\'', 0 }; error(e); }
}
static long E(void);
static long F(void) { /* F -> ( E ) | num */
long v;
enter("F");
if (tok == '(') { match('('); v = E(); match(')'); }
else if (tok == 'n') { v = tokval; match('n'); }
else error("number or '('");
leave();
return v;
}
static long Tprime(long left) { /* T' -> * F T' | / F T' | eps */
long v;
enter("T'");
if (tok == '*') { match('*'); v = Tprime(left * F()); }
else if (tok == '/') { match('/'); v = Tprime(left / F()); }
else v = left; /* T' -> eps */
leave();
return v;
}
static long T(void) { long v; enter("T"); v = Tprime(F()); leave(); return v; }
static long Eprime(long left) { /* E' -> + T E' | - T E' | eps */
long v;
enter("E'");
if (tok == '+') { match('+'); v = Eprime(left + T()); }
else if (tok == '-') { match('-'); v = Eprime(left - T()); }
else v = left; /* E' -> eps */
leave();
return v;
}
static long E(void) { long v; enter("E"); v = Eprime(T()); leave(); return v; }
int main(int argc, char **argv) {
if (argc < 2) { fprintf(stderr, "usage: %s [-t] \"expression\"\n", argv[0]); return 2; }
if (argc == 3) { tracing = 1; src = argv[2]; } else src = argv[1];
next();
long v = E();
if (tok != '$') error("operator or end of input");
printf("%s = %ld\n", src, v);
return 0;
}Compare each procedure with its row in the decision table above: the code is a direct transcription of the grammar. The enter/leave calls only print a trace.
Running It
With -t the parser prints each procedure call, indented by depth, with the lookahead at the moment of the call:
$ gcc -std=c17 -Wall -Wextra rd.c -o rd
$ ./rd -t '2 + 3 * 4'
E (lookahead num 2)
T (lookahead num 2)
F (lookahead num 2)
T' (lookahead '+')
E' (lookahead '+')
T (lookahead num 3)
F (lookahead num 3)
T' (lookahead '*')
F (lookahead num 4)
T' (lookahead '$')
E' (lookahead '$')
2 + 3 * 4 = 14Read the trace as the parse tree turned on its side. A few details worth checking:
The first
T'sees+. That is not*or/, so it takes T' → ε and returns at once. ThenE'sees the same+and takes E' → + T E'.The
*is handled inside the secondT, deeper in the tree than the+. That is why 3 * 4 is computed first: 2 + 12 = 14.The last
T'andE'see$(end of input), which is in their FOLLOW sets, so both choose ε.No procedure ever had to undo anything: one token of lookahead was always enough.
Associativity is correct as well:
$ ./rd '8 - 3 - 2'
8 - 3 - 2 = 3
$ ./rd '(1 + 2) * (10 - 4) / 3'
(1 + 2) * (10 - 4) / 3 = 6
$ ./rd '100 / 10 / 5'
100 / 10 / 5 = 2If E' had instead been written to return "T minus the value of the rest", the result for 8 - 3 - 2 would have been 8 − (3 − 2) = 7, the right-associative answer. The grammar with E' is right-recursive, so we have to carry the left operand along to get left associativity back.
Error Detection
A predictive parser detects an error at the first token that cannot continue a valid program, and it knows what it expected there:
$ ./rd '2 * (3 + )'
syntax error at column 10: expected number or '(', found ')'
$ ./rd '4 4'
syntax error at column 3: expected operator or end of input, found number 4
$ ./rd '(1 + 2'
syntax error at column 7: expected ')', found end of inputIn the first case, after +, the parser is inside T and then F, which needs a number or (. In the second, E returned after the first 4 (E' took ε because a number is not + or −), and main found extra input. In the third, F matched ( E and then needed ). This parser simply stops at the first error; a production compiler would use panic-mode recovery, skipping to a synchronizing token, to report more errors.
A Shorter Version with Loops
Tail-recursive procedures like E' and T' can be replaced by loops. In EBNF notation, where { ... } means "zero or more times", the grammar is E → T { (+|-) T } and T → F { (*|/) F }, and the code becomes:
static long T(void) { /* T -> F { (*|/) F } */
long v = F();
while (tok == '*' || tok == '/') {
int op = tok;
next();
long r = F();
v = (op == '*') ? v * r : v / r;
}
return v;
}
static long E(void) { /* E -> T { (+|-) T } */
long v = T();
while (tok == '+' || tok == '-') {
int op = tok;
next();
long r = T();
v = (op == '+') ? v + r : v - r;
}
return v;
}This version (with the same F and lexer) gives identical results on all the inputs above. The loop accumulates from left to right, so left associativity comes for free. Most hand-written parsers in real compilers look like this.
Top-Down Parsing Methods Compared
Aspect | Backtracking recursive descent | Predictive recursive descent | Table-driven LL(1) |
|---|---|---|---|
How the production is chosen | Try alternatives in order, undo on failure | Code tests the lookahead | Table lookup M[A, a] |
Backtracking | Yes | No | No |
Time | Exponential in the worst case | Linear | Linear |
Grammar requirements | No left recursion | LL(1) (no left recursion, left-factored, FIRST/FOLLOW conditions) | LL(1) |
Stack | Implicit (call stack) | Implicit (call stack) | Explicit stack of grammar symbols |
Ease of adding actions and error messages | Poor | Excellent | Good |
Typical use | Teaching, tiny ad-hoc parsers | Hand-written production compilers (GCC, Clang, many others) | Textbook LL(1) parser generators; ANTLR uses the more powerful LL(*)/ALL(*) variants of the same idea |
Top-Down vs Bottom-Up
Aspect | Top-down | Bottom-up |
|---|---|---|
Tree built | From the root to the leaves | From the leaves to the root |
Derivation traced | Leftmost | Rightmost, in reverse |
Main operation | Expand (predict) a non-terminal | Shift tokens and reduce handles |
Left recursion | Not allowed | Fine |
Grammar class (deterministic versions) | LL(1), smaller | LR(1), larger: every LL(1) grammar is LR(1) |
Easy to write by hand? | Yes | No, usually generated (Yacc/Bison) |
Common Mistakes
Writing a recursive descent procedure for a left-recursive production.
E → E + TbecomesE() { E(); ... }, infinite recursion. Remove left recursion first.Assuming "try alternatives until one works" is full backtracking. Committing to the first successful alternative can reject valid strings.
Choosing ε by default without thinking about FOLLOW. It works for correct inputs, but an error is then detected later than necessary, sometimes with a confusing message.
Forgetting to check for end of input after the start procedure returns. Without the final check,
4 4would be accepted as4.Getting associativity wrong after removing left recursion. Carry the left operand into E' (or use a loop).
Advancing the input on a mismatch.
matchmust only advance when the token is the expected one.
GATE and Interview Questions
Which derivation does a top-down parser produce?
A leftmost derivation. It always expands the leftmost non-terminal of the current sentential form.
Why can't a recursive descent parser handle left-recursive grammars?
For A → Aα, the procedure for A calls itself as its first action without consuming any input, so it recurses forever (until stack overflow). The lookahead does not change between calls, so no test can stop it.
What is the difference between recursive descent and predictive parsing?
Recursive descent is the general technique of one procedure per non-terminal; it may use backtracking. A predictive parser is a recursive descent (or table-driven) parser that chooses each production using only the lookahead and never backtracks. It requires an LL(1)-style grammar.
Given S → c A d, A → a b | a, trace a backtracking parser on input c a d.
S → c A d: match c. A → a b: match a, then expect b but find d: fail, reset input to a. A → a: match a, return. Match d. Input consumed: accept.
Why is backtracking avoided in compilers?
It can take exponential time, it makes undoing semantic actions (symbol table entries, generated code) hard, and it gives poor error messages because the parser cannot tell which failed alternative was the real error.
For which grammars can we build a predictive parser with one token of lookahead?
LL(1) grammars: for every non-terminal, the alternatives have pairwise disjoint FIRST sets, at most one alternative derives ε, and if one does, the FIRST sets of the others are disjoint from FOLLOW of that non-terminal. Such grammars are never ambiguous or left-recursive.
In a recursive descent parser for E → T E', E' → + T E' | ε, what should E'() do when the lookahead is ')'?
Choose E' → ε and return without consuming anything, because ) is in FOLLOW(E'). The caller (inside F → ( E )) then matches the ).
Do real compilers use recursive descent?
Yes. GCC (for C and C++) and Clang use hand-written recursive descent parsers, because they are fast, easy to extend with language quirks, and allow excellent error messages.
Summary
Top-down parsing builds the parse tree from the root, in preorder, tracing a leftmost derivation. The key decision is which production to use for the leftmost non-terminal.
Recursive descent: one procedure per non-terminal; non-terminals become calls, terminals become
matchcalls.Backtracking tries alternatives in order and undoes failures: general but potentially exponential, awkward with side effects, and unable to handle left recursion. Committing to the first success is not full backtracking.
Predictive parsing chooses using the lookahead, with FIRST for normal alternatives and FOLLOW for ε-alternatives. It needs an LL(1) grammar, runs in linear time and gives precise error messages.
Removing left recursion makes the grammar right-recursive; pass the left operand down (or use loops) to keep operators left-associative.
The same parser can be driven by a table instead of code: that is LL(1) parsing, the next chapter.
A good top-down parser never guesses. It looks at one token, knows exactly which rule applies, and moves on.