The top-down parsing tutorial introduced predictive parsing as a way to avoid backtracking by deciding, in advance, which production rule to apply based on the current non-terminal and the next available input token. LL(1) parsing takes this exact idea and turns it into a fully systematic, table-driven procedure, removing the need to hand-write a separate function for every non-terminal in the grammar. Instead, the entire parsing logic is captured inside a single table, which a small, generic parsing routine can consult at every step.
The name LL(1) itself describes precisely how this technique works. The first L indicates that the input is scanned from left to right. The second L indicates that the parser constructs a leftmost derivation of the input. The number 1 indicates that the parser only ever needs to look one token ahead in the input to decide which production rule to apply next. Together, these three properties define a very specific, well-behaved category of grammars and parsers, and understanding them is the key to understanding this entire topic.
In this tutorial, you will learn how to compute FIRST and FOLLOW sets for a grammar, how those sets are used to construct a complete LL(1) parsing table, how a predictive parser uses that table alongside a parsing stack to process input, what it means for a grammar to qualify as LL(1), and what to do when a grammar does not meet that requirement.
A predictive parser needs a reliable way to decide, for a given non-terminal and a given next input token, exactly which production rule to apply. FIRST and FOLLOW sets provide precisely this information, and computing them correctly is the essential first step in building any LL(1) parser.
| Set | Meaning |
|---|---|
| FIRST(X) | The set of terminal symbols that can appear as the first symbol of any string derivable from X. If X can derive the empty string, epsilon is included in FIRST(X). |
| FOLLOW(X) | The set of terminal symbols that can appear immediately after X in some valid sentential form derived from the start symbol. |
The FIRST set of a non-terminal is computed by examining its production rules and following a small set of consistent rules, applied repeatedly until no further symbols can be added to any FIRST set in the grammar.
Grammar:
Expression -> Term ExpressionRest
ExpressionRest -> + Term ExpressionRest | epsilon
Term -> Factor TermRest
TermRest -> * Factor TermRest | epsilon
Factor -> ( Expression ) | Identifier
FIRST(Factor) = { (, Identifier }
FIRST(TermRest) = { *, epsilon }
FIRST(Term) = { (, Identifier }
FIRST(ExpressionRest) = { +, epsilon }
FIRST(Expression) = { (, Identifier }
Notice how FIRST(Term) simply inherits the FIRST set of Factor, since every production for Term begins with Factor. Similarly, since TermRest can derive the empty string, epsilon is correctly included in its FIRST set, reflecting the fact that a Term can consist of just a Factor with no multiplication following it.
FOLLOW sets are slightly more involved to compute, since they depend on how a non-terminal is actually used elsewhere in the grammar, rather than only on its own production rules.
Using the same grammar as above:
FOLLOW(Expression) = { ), $ }
FOLLOW(ExpressionRest) = { ), $ }
FOLLOW(Term) = { +, ), $ }
FOLLOW(TermRest) = { +, ), $ }
FOLLOW(Factor) = { *, +, ), $ }
Here, FOLLOW(Expression) includes a closing parenthesis, since Expression appears inside "( Expression )" in the production for Factor, and it also includes the end marker, since Expression is the start symbol. FOLLOW(Factor) picks up the multiplication and addition symbols because Factor is followed by TermRest, and TermRest can derive epsilon, meaning whatever follows TermRest, including plus and the closing parenthesis, must also be considered part of what can follow Factor.
Once FIRST and FOLLOW sets have been computed for every non-terminal, they can be used to build the LL(1) parsing table, a two-dimensional table indexed by non-terminals along one axis and terminal symbols, including the end marker, along the other. Each cell in the table either contains a specific production rule to apply, or is left blank, indicating a syntax error if that combination is ever encountered during parsing.
The table is built by applying a simple procedure for every production rule in the grammar.
Partial LL(1) Parsing Table:
( ) Identifier + * $
Expression Expr->Term ExprRest Expr->Term ExprRest
ExprRest ExprRest->eps ExprRest->+Term ExprRest ExprRest->eps
Term Term->Factor TermRest Term->Factor TermRest
TermRest TermRest->eps TermRest->eps TermRest->*Factor TermRest TermRest->eps
Factor Factor->(Expression) Factor->Identifier
To parse using this table, the parser only ever needs to look at the non-terminal currently at the top of its parsing stack and the next input token, then look up the corresponding cell to find out exactly which production rule to apply, with no guessing or backtracking required at any point.
A table-driven predictive parser operates using a parsing stack, initially containing just the grammar's start symbol along with the end-of-input marker, and processes the input tokens one at a time according to a simple, repeating procedure.
| Top of Stack | Action |
|---|---|
| A terminal symbol matching the next input token. | Pop the terminal from the stack and consume the matching input token. |
| A non-terminal symbol. | Look up the parsing table using the non-terminal and the next input token, then replace the non-terminal on the stack with the right-hand side of the corresponding production rule. |
| The end-of-input marker, with no remaining input. | Accept the input as valid, since the entire stack and input have been successfully consumed together. |
| Any other situation, such as a blank table entry or a mismatched terminal. | Report a syntax error, since no valid continuation of the parse is possible. |
Parsing the input: id + id Stack: Expression $ Input: id + id $ Table Lookup: Expression -> Term ExprRest Stack: Term ExprRest $ Input: id + id $ Table Lookup: Term -> Factor TermRest Stack: Factor TermRest ExprRest $ Input: id + id $ Table Lookup: Factor -> id Stack: id TermRest ExprRest $ Input: id + id $ Action: Match 'id', consume input Stack: TermRest ExprRest $ Input: + id $ Table Lookup: TermRest -> epsilon Stack: ExprRest $ Input: + id $ Table Lookup: ExprRest -> + Term ExprRest Stack: + Term ExprRest $ Input: + id $ Action: Match '+', consume input Stack: Term ExprRest $ Input: id $ Table Lookup: Term -> Factor TermRest Stack: Factor TermRest ExprRest $ Input: id $ Table Lookup: Factor -> id Stack: id TermRest ExprRest $ Input: id $ Action: Match 'id', consume input Stack: TermRest ExprRest $ Input: $ Table Lookup: TermRest -> epsilon Stack: ExprRest $ Input: $ Table Lookup: ExprRest -> epsilon Stack: $ Input: $ Action: Accept
This trace demonstrates the elegance of table-driven predictive parsing. At every single step, the parser's next move is determined entirely by consulting the table, using only the symbol currently on top of the stack and the next input token, without ever needing to guess between multiple possibilities.
Not every context-free grammar can be used to build a valid LL(1) parsing table. A grammar qualifies as LL(1) only if, during table construction, no single cell in the parsing table ever ends up needing to hold more than one production rule at the same time. If two different rules for the same non-terminal both need to be placed in the same table cell, the grammar is not LL(1), since the parser would have no way to decide which rule to apply using only one token of lookahead.
This requirement directly connects back to the conditions discussed in the top-down parsing tutorial. A grammar must be free of left recursion, must be left factored wherever alternatives share a common prefix, and must not have overlapping FIRST sets among a non-terminal's alternative production rules, including careful handling of any alternative that can derive epsilon, in order to reliably produce a valid, conflict-free LL(1) parsing table.
When a grammar cannot be directly converted into a valid LL(1) parsing table, compiler designers generally have a few options available, depending on the nature of the problem.
| Advantages | Limitations |
|---|---|
| Parsing is efficient, since each decision requires only a single table lookup based on one token of lookahead. | Only a specific, well-behaved subset of context-free grammars can be directly used for LL(1) parsing. |
| The parsing table can be generated automatically once FIRST and FOLLOW sets are computed, avoiding the need for hand-written recursive functions. | Grammars must often be rewritten, sometimes reducing their natural readability, in order to satisfy LL(1) requirements. |
| Error detection is generally straightforward, since a blank table entry immediately signals an invalid combination of non-terminal and input token. | Some language constructs genuinely require more than one token of lookahead, which LL(1) parsing cannot support without further extension. |
| Mistake | Correct Understanding |
|---|---|
| Forgetting to include epsilon-related FOLLOW set entries when a production rule can derive the empty string. | Whenever a production's right-hand side can derive epsilon, the corresponding production must also be added to the table for every terminal in the non-terminal's FOLLOW set, not just its FIRST set. |
| Assuming that computing FIRST and FOLLOW sets once is enough, without rechecking for conflicts while building the table. | A grammar only qualifies as LL(1) if the completed parsing table contains no cell with more than one production rule, which must be explicitly verified. |
| Believing every ambiguous grammar can be fixed simply by applying left recursion elimination and left factoring. | Some grammars require fundamentally different parsing techniques, or additional lookahead, and cannot be converted into a valid LL(1) grammar through these transformations alone. |
| Confusing the roles of FIRST and FOLLOW sets when filling in the parsing table. | FIRST sets determine which table entries a production is added to under normal circumstances, while FOLLOW sets are only used when a production can derive epsilon. |
LL(1) parsing turns predictive top-down parsing into a fully systematic, table-driven technique, using FIRST and FOLLOW sets to determine exactly which production rule to apply based on the current non-terminal and a single token of lookahead. Once these sets are computed, they are used to construct a parsing table, which a simple, generic parsing routine can consult at every step, using a parsing stack to track its progress through the derivation. A grammar only qualifies as LL(1) if this table can be built without any conflicting entries, which typically requires the grammar to be free of left recursion and properly left factored.
In this tutorial, you learned how to compute FIRST and FOLLOW sets step by step, how those sets are used to construct a complete LL(1) parsing table, how a predictive parser uses that table alongside a stack to process input token by token, what conditions a grammar must satisfy to qualify as LL(1), and what options exist when a grammar does not meet that requirement. With this foundation in place, you are ready to explore LR parsing, a more powerful bottom-up, table-driven technique capable of handling a substantially wider range of grammars.