CoreSource checked

FIRST/FOLLOW Set Computation

Computes grammar symbol sets used to predict valid parser choices.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Parsing
Difficulty: Intermediate
Family: Grammar Analysis
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 3
Code example: Ready
Visualization: Ready

Overview

FIRST sets describe tokens that can begin a symbol, while FOLLOW sets describe tokens that may appear after a nonterminal.

Core Concepts

first setfollow setnullable symbolgrammar fixed point

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(grammar size)

Average

O(iterations * grammar size)

Worst

O(iterations * grammar size)

Space

O(grammar size)

When to Use

Use when language parsing needs first set.
Use when the input matches the assumptions behind grammar Analysis.

When Not to Use

Avoid when the grammar class does not match the parser's assumptions.
Avoid when a simpler algorithm gives the required result with less setup.

What It Does

Computes grammar symbol sets used to predict valid parser choices
Uses first set and follow set to guide the work.
Produces parse tree.

Use Cases

Language parsing
Compiler front ends
Structured text processing

Inputs

Tokens or grammar
Parser state

Outputs

Parse tree
Automaton
Grammar table or parse result

Key Formulas (1)

FIRST propagation

FIRST(A) includes FIRST(symbol) for productions A → symbol …

FIRST(A) includes FIRST(symbol) for productions A -> symbol ...

Adds possible leading tokens from productions until sets stop changing.

Pseudocode

1.Prepare tokens, grammar rules, tables, or automaton states
2.Advance through tokens or grammar items according to the parsing rule
3.Create parse nodes, state transitions, or table entries when a rule applies
4.Report an error or return the completed structure

Canonical Example

Input: tokens = ['id', '+', 'id', '*', 'id'] with a tiny grammar or precedence table
Output: Parse tree
Explanation: FIRST/FOLLOW Set Computation applies first set to produce parse tree.

Implementation Notes

Report errors with token position and expected grammar symbols.
Keep the first set step separate enough to test independently.
Keep lexical analysis separate from parsing unless the method explicitly combines them.

Common Pitfalls

Ambiguity and left recursion must be handled according to the parser type.
Test edge cases, not only clean examples.
Mixing token positions, character offsets, and grammar states can produce misleading parse errors.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show grammar items, parser states, and consumed input as parsing progresses.

Input:ABABABCABAB

Window:ABAB

Step 1 of 4: Prepare tokens, grammar rules, tables, or automaton states

parsing-mechanism

Notes

FIRST/FOLLOW Set Computation should be used with the assumptions and tradeoffs of grammar Analysis in mind.

Sources (1)

What each reference supports for this entry.

Compilers: Principles, Techniques, and Tools

Book

Compiler textbook support for FIRST/FOLLOW Set Computation's grammar analysis, parser construction, and implementation constraints.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Used byLL(1) Parse Table Construction

Parsing · Core

LL(1) parse table construction uses FIRST and FOLLOW sets to choose productions.

Compare with this

Used byLR(1) Item Set Construction