In the previous tutorial, you learned that a parser can build a parse tree either from the root downward or from the leaves upward. Top-down parsing is the family of techniques that follows the first approach, starting with the grammar's start symbol and repeatedly expanding it, one production rule at a time, until the sequence of terminal symbols it generates matches the actual input tokens. It is often the first parsing strategy students learn in detail, partly because its logic maps closely onto something programmers already understand well: recursive functions.
What makes top-down parsing especially approachable is that, in its simplest form, it can be implemented almost directly as ordinary code, without requiring complex tables or automatically generated parsing logic. At the same time, this simplicity comes with real limitations, and understanding exactly where top-down parsing struggles is just as important as understanding how it works when everything goes smoothly.
In this tutorial, you will learn how top-down parsing works conceptually, how recursive descent parsing is implemented, why backtracking causes problems for certain grammars, how predictive parsing avoids the need for backtracking, what left recursion and left factoring are and why they must be eliminated, how FIRST and FOLLOW sets support predictive parsing, and the key limitations of top-down parsing as a whole.
Top-down parsing begins with the grammar's start symbol and tries to derive the exact sequence of input tokens by repeatedly choosing and applying production rules. At each step, the parser is essentially asking a question: given the current non-terminal I need to expand, and the tokens I have left to match, which production rule should I apply next?
This process continues until every non-terminal in the derivation has been fully expanded into terminal symbols that exactly match the remaining input tokens, at which point the input is confirmed to be valid according to the grammar. If, at any point, no production rule can lead to a match with the remaining input, the parser must either try a different rule or report a syntax error.
Grammar:
Statement -> if ( Condition ) Statement
| Identifier = Expression ;
Input Tokens:
if ( Condition ) IDENTIFIER = Expression ;
Faced with this input, a top-down parser looks at the first token, "if", and recognizes that only the first production rule for Statement could possibly begin with that token. It selects that rule and continues expanding the remaining non-terminals, using the next tokens in the input to guide each subsequent choice.
Recursive descent parsing is the most direct and intuitive implementation of top-down parsing. In this approach, each non-terminal in the grammar is implemented as a separate function in the parser's source code. Whenever that non-terminal needs to be expanded, the corresponding function is called, and that function is responsible for matching the input against one of the non-terminal's production rules, calling other functions along the way whenever the rule refers to another non-terminal.
Grammar:
Expression -> Term + Expression | Term
Term -> Identifier | Number
Simplified Recursive Descent Functions:
function parseExpression():
parseTerm()
if next_token == '+':
consume('+')
parseExpression()
function parseTerm():
if next_token == IDENTIFIER:
consume(IDENTIFIER)
else if next_token == NUMBER:
consume(NUMBER)
else:
report syntax error
Notice how closely this code mirrors the grammar itself. Each production rule becomes a corresponding block of logic inside a function, and whenever a non-terminal appears on the right-hand side of a rule, the parser simply calls that non-terminal's function. This close correspondence between grammar rules and code is exactly what makes recursive descent parsing so approachable for beginners, and it is often the very first parsing technique introduced in a Compiler Design course.
Not every grammar allows a parser to know immediately which production rule to apply just by looking at the next available token. When multiple production rules for the same non-terminal begin with a similar or overlapping pattern, a naive recursive descent parser may need to try one rule, and if that rule eventually leads to a mismatch further along, undo its choices and try a different rule instead. This strategy is known as backtracking.
Grammar:
Statement -> Identifier = Expression ;
| Identifier ( ArgumentList ) ;
Both production rules for Statement begin with an identifier, so a parser cannot immediately tell which rule applies just by looking at the very first token. A backtracking parser might tentatively try the first rule, and only after failing to find an assignment operator where expected, backtrack and attempt the second rule instead, treating the identifier as the beginning of a function call.
Backtracking works, but it comes with serious drawbacks. It can be highly inefficient, since the parser may repeatedly reprocess the same tokens multiple times while trying different rules. It also complicates error reporting, since a failed attempt partway through one rule is not necessarily an actual syntax error, only a signal to try a different possibility. Because of these drawbacks, most practical parsers try to avoid backtracking entirely whenever possible.
Predictive parsing is a refined form of top-down parsing that eliminates the need for backtracking by deciding, in advance, exactly which production rule to apply based only on the current non-terminal and the next available input token, without ever needing to guess and later undo a choice. This is possible only for a specific, well-behaved category of grammars.
To make these decisions correctly, predictive parsers rely on two important sets associated with the grammar, known as FIRST and FOLLOW sets, which describe exactly which tokens can legally appear in certain positions relative to each non-terminal.
| Set | Meaning |
|---|---|
| FIRST(X) | The set of terminal symbols that can appear as the very first token of any string derived from the non-terminal X. |
| FOLLOW(X) | The set of terminal symbols that can legally appear immediately after the non-terminal X in some valid derivation. |
Grammar:
Term -> Identifier
| Number
FIRST(Term) = { IDENTIFIER, NUMBER }
Using FIRST sets like this one, a predictive parser looking at the next input token can immediately determine which production rule to use for Term, without needing to guess and backtrack, since IDENTIFIER and NUMBER unambiguously point to different rules.
A grammar is said to contain left recursion when a non-terminal, directly or indirectly, appears as the very first symbol on the right-hand side of one of its own production rules. Left recursion is fatal for top-down parsing, since a recursive descent function for such a non-terminal would call itself immediately, before consuming any input tokens at all, leading to infinite recursion rather than a working parser.
Left-Recursive Grammar:
Expression -> Expression + Term
| Term
Problem:
Parsing Expression immediately requires parsing Expression again, before any token has been consumed, resulting in infinite recursive calls.
Fortunately, any left-recursive grammar can be systematically rewritten into an equivalent grammar that produces the same language without left recursion, typically by introducing a new non-terminal that captures the repeated part of the original rule using right recursion instead.
Left Recursion Removed:
Expression -> Term ExpressionRest
ExpressionRest -> + Term ExpressionRest
| epsilon
This rewritten grammar generates exactly the same set of valid expressions as the original, but it is now perfectly suitable for top-down parsing, since ExpressionRest always consumes at least a "+" token before referring to itself again, guaranteeing that the recursion eventually terminates.
Left factoring is a separate but related grammar transformation used to handle situations where two or more production rules for the same non-terminal begin with the same sequence of symbols, making it impossible for a predictive parser to decide which rule to use just by looking at the next token, without introducing backtracking.
Grammar with a Shared Prefix:
Statement -> Identifier = Expression ;
| Identifier ( ArgumentList ) ;
Left-Factored Grammar:
Statement -> Identifier StatementRest
StatementRest -> = Expression ;
| ( ArgumentList ) ;
By factoring out the shared "Identifier" prefix into its own rule, the grammar now allows the parser to consume the identifier first, unconditionally, and only decide between the remaining alternatives once it reaches the next token, which will clearly be either an assignment operator or an opening parenthesis. This small transformation removes the ambiguity that would otherwise force the parser to guess or backtrack.
Not every grammar can be used directly with predictive top-down parsing, even after removing left recursion and applying left factoring. A grammar suitable for predictive parsing generally needs to satisfy a few important conditions.
Grammars that satisfy these conditions are often referred to as LL(1) grammars, a term that will be explored in much greater depth in the dedicated tutorial on LL(1) parsing later in this series, where FIRST and FOLLOW sets are used to systematically build a complete predictive parsing table.
| Advantages | Limitations |
|---|---|
| Conceptually simple and closely mirrors the structure of the grammar itself. | Cannot handle left-recursive grammars without first rewriting them. |
| Easy to implement by hand using recursive descent, without specialized tools. | Grammars with overlapping alternatives require left factoring before predictive parsing can be used. |
| Predictive parsing avoids backtracking entirely for suitable grammars, making parsing efficient. | Not every valid context-free grammar can be directly converted into a form suitable for predictive top-down parsing. |
| Error messages can often be produced clearly, since the parser generally knows exactly what it was expecting at each step. | Handling deeply ambiguous or complex language constructs sometimes requires grammar restructuring that reduces readability. |
| Mistake | Correct Understanding |
|---|---|
| Assuming recursive descent parsing and predictive parsing are two completely unrelated techniques. | Predictive parsing is essentially a refined, backtracking-free style of recursive descent parsing, guided by FIRST and FOLLOW sets. |
| Trying to write a recursive descent parser directly from a left-recursive grammar. | Left-recursive grammars must first be rewritten into an equivalent right-recursive form before top-down parsing can be applied. |
| Believing left factoring changes the language a grammar generates. | Left factoring only restructures how a grammar is written to remove overlapping prefixes; it does not change the set of valid strings the grammar can produce. |
| Thinking every grammar can be used for predictive parsing without any modification. | A grammar must satisfy specific conditions, including the absence of left recursion and non-overlapping FIRST sets, before predictive parsing can be applied directly. |
Top-down parsing builds a parse tree starting from the grammar's start symbol and working downward, most commonly implemented through recursive descent parsing, where each non-terminal corresponds to its own function. While backtracking can allow a top-down parser to handle a wider range of grammars, it comes at the cost of efficiency and clean error reporting, which is why predictive parsing, guided by FIRST and FOLLOW sets, is generally preferred. Achieving predictive parsing requires grammars free of left recursion and free of overlapping prefixes, both of which can be resolved through systematic grammar rewriting techniques.
In this tutorial, you learned how top-down parsing works conceptually, how recursive descent parsing is implemented directly from a grammar, why backtracking is problematic, how predictive parsing avoids it using FIRST and FOLLOW sets, why left recursion must be eliminated and how to eliminate it, what left factoring accomplishes, and the overall advantages and limitations of this parsing approach. With this foundation in place, you are ready to explore bottom-up parsing, a different strategy that builds the parse tree starting from the input tokens themselves.