Course contentsShow
← Computer Science
Lesson 1956 of 2,87244. Lexical Analysis and ParsingFree lesson

Predictive Parsing and FIRST Sets

Computing FIRST sets to determine which production to use based on the next input token.

Predictive Parsing and FIRST Sets

What you'll learn: How a parser uses FIRST sets to decide which grammar production to apply by examining the next input token.

The Core Problem

When a top-down parser encounters a non-terminal with multiple production choices, it faces a decision: which rule should it use? Predictive parsing solves this by looking ahead at the next input token and consulting a precomputed table.

What Are FIRST Sets?

The FIRST set of a grammar symbol (terminal, non-terminal, or production right-hand side) contains all the terminals that can appear as the first symbol when that grammar element is expanded.

For example, given these productions:

E → T + E
E → T
T → int
T → ( E )
  • FIRST(T) = {int, (} — because T can start with either token
  • FIRST(E) = {int, (} — because E always expands to T first
  • FIRST(T + E) = {int, (} — we look at T, ignoring what comes after

How Predictive Parsing Uses FIRST

When the parser sees a non-terminal and needs to choose between productions, it:

  1. Examines the next input token
  2. Checks which production's FIRST set contains that token
  3. Selects that production

If the next token is int and we're parsing E, we know both productions could work because int is in both FIRST(T + E) and FIRST(T). This would require left factoring to fix, as you learned previously.

Why This Matters

FIRST sets enable deterministic parsing decisions without backtracking. The parser makes exactly one choice per non-terminal based purely on the lookahead token—making parsing efficient and predictable.

Key Takeaway: FIRST sets map each production to the tokens that can legally begin it, allowing predictive parsers to choose the correct production rule by examining just the next input token.