FIRST and FOLLOW sets in Compiler Design - Deep Dive

Overview - FIRST and FOLLOW sets

What is it?

FIRST and FOLLOW sets are tools used in compiler design to analyze grammar rules. FIRST set of a grammar symbol tells us which terminals can appear at the beginning of strings derived from that symbol. FOLLOW set tells us which terminals can appear immediately after that symbol in some valid string. These sets help in building parsers that understand the structure of programming languages.

Why it matters

Without FIRST and FOLLOW sets, a compiler would struggle to decide how to parse code correctly, leading to errors or ambiguity. They solve the problem of predicting which grammar rule to apply next, making parsing efficient and deterministic. This ensures that programming languages can be processed reliably by computers, enabling software development.

Where it fits

Learners should first understand context-free grammars and basic parsing concepts. After mastering FIRST and FOLLOW sets, they can study parser construction techniques like LL(1) and LR parsing. These sets are foundational for understanding how compilers analyze and process source code.

Mental Model

Core Idea

FIRST sets identify possible starting symbols of derivations, while FOLLOW sets identify possible symbols that can come immediately after a non-terminal in valid strings.

Think of it like...

Imagine reading a recipe book: FIRST sets tell you what ingredients you might find at the start of a recipe step, while FOLLOW sets tell you what ingredients or steps come right after a particular ingredient or step.

Grammar Symbol
   │
   ├─ FIRST set: terminals that can start strings from this symbol
   └─ FOLLOW set: terminals that can appear immediately after this symbol

Example:
  Non-terminal A
  ├─ FIRST(A) = {a, b}
  └─ FOLLOW(A) = {c, $}

Where $ means end of input

Build-Up - 7 Steps

1

Foundation

Understanding Grammar Symbols

Concept: Introduce terminals and non-terminals in grammar and their roles.

A grammar consists of terminals (actual characters or tokens) and non-terminals (symbols representing patterns). Terminals are like words in a language, and non-terminals are categories or phrases made from those words. For example, in English, 'noun' is a non-terminal, and 'cat' is a terminal.

Result

Learners can distinguish between basic building blocks (terminals) and abstract categories (non-terminals) in grammar.

Understanding the difference between terminals and non-terminals is essential because FIRST and FOLLOW sets apply differently to each.

2

Foundation

What is a Derivation in Grammar?

Concept: Explain how strings are formed from grammar symbols through production rules.

Derivation means starting from a non-terminal and repeatedly replacing it using grammar rules until only terminals remain. For example, if S → aA and A → b, then S derives 'ab'. This process shows how sentences or strings are generated.

Result

Learners grasp how grammar rules produce strings and how non-terminals expand into terminals.

Knowing derivations helps understand why FIRST sets focus on possible starting terminals of these expansions.

3

Intermediate

Defining the FIRST Set

🤔Before reading on: do you think FIRST sets include only terminals or can they include non-terminals? Commit to your answer.

Concept: FIRST set of a symbol is the set of terminals that can appear at the start of strings derived from that symbol.

For a terminal, FIRST is just the terminal itself. For a non-terminal, FIRST includes terminals that can appear first in any string derived from it. If a non-terminal can derive the empty string (ε), then ε is included in its FIRST set. For example, if A → aB | ε, then FIRST(A) = {a, ε}.

Result

Learners can compute FIRST sets for terminals and non-terminals, including handling empty strings.

Understanding FIRST sets is crucial because they predict what input symbols can appear next, guiding parser decisions.

4

Intermediate

Defining the FOLLOW Set

🤔Before reading on: do you think FOLLOW sets depend on the position of a symbol in grammar rules? Commit to your answer.

Concept: FOLLOW set of a non-terminal is the set of terminals that can appear immediately after it in some valid string derived from the grammar's start symbol.

FOLLOW sets help determine what can come next after a non-terminal. For example, if a rule is A → αBβ, then everything in FIRST(β) except ε is in FOLLOW(B). If β can derive ε, then FOLLOW(A) is also in FOLLOW(B). The start symbol's FOLLOW set always includes the end-of-input marker ($).

Result

Learners can compute FOLLOW sets by analyzing grammar rules and positions of non-terminals.

FOLLOW sets complement FIRST sets by showing what can follow a symbol, enabling parsers to know when to stop or switch rules.

5

Intermediate

Computing FIRST and FOLLOW Sets Step-by-Step

🤔Before reading on: do you think FIRST and FOLLOW sets are computed once or iteratively updated? Commit to your answer.

Concept: FIRST and FOLLOW sets are computed using iterative algorithms that update sets until no changes occur.

Start by initializing FIRST sets for terminals and empty for non-terminals. Then apply rules repeatedly: add terminals to FIRST sets based on productions, include ε if applicable. For FOLLOW sets, start with $ in FOLLOW(start symbol), then add terminals based on positions in productions, propagating FOLLOW sets as needed. Repeat until stable.

Result

Learners can perform the full computation of FIRST and FOLLOW sets for any grammar.

Knowing the iterative nature prevents confusion about why sets grow over time and ensures correct computation.

6

Advanced

Using FIRST and FOLLOW in LL(1) Parsing

🤔Before reading on: do you think FIRST and FOLLOW sets alone guarantee a parser will be unambiguous? Commit to your answer.

Concept: FIRST and FOLLOW sets are used to build LL(1) parsing tables that decide which production to use based on the next input symbol.

In LL(1) parsing, for each non-terminal and terminal, the parser uses FIRST and FOLLOW sets to fill a table. If a production's FIRST set contains a terminal, that production is chosen when that terminal appears next. If the production can derive ε, then terminals in FOLLOW set guide the choice. Conflicts in this table indicate grammar is not LL(1).

Result

Learners understand how FIRST and FOLLOW sets enable predictive parsing and detect grammar ambiguities.

Understanding this application shows why these sets are not just theoretical but practical tools for building efficient parsers.

7

Expert

Handling ε-Productions and Ambiguities

🤔Before reading on: do you think ε-productions simplify or complicate FIRST and FOLLOW computations? Commit to your answer.

Concept: ε-productions (rules that produce empty strings) require careful handling in FIRST and FOLLOW computations and can cause parsing conflicts.

When a non-terminal can derive ε, its FIRST set includes ε, affecting FOLLOW set propagation. This can cause overlaps in parsing table entries, leading to ambiguity. Experts use techniques like grammar refactoring or lookahead to resolve these conflicts. Understanding subtle interactions between ε, FIRST, and FOLLOW is key to robust parser design.

Result

Learners appreciate the complexity ε-productions introduce and how to manage them in real parsers.

Knowing these subtleties prevents common parser bugs and guides grammar design for unambiguous parsing.

Under the Hood

FIRST and FOLLOW sets are computed by analyzing grammar production rules and simulating possible derivations. The process involves fixed-point iteration where sets are updated repeatedly until no new terminals can be added. Internally, this simulates all possible strings derivable from symbols, tracking which terminals appear at start or immediately after symbols. This analysis enables parsers to predict next input tokens without backtracking.

Why designed this way?

The design balances completeness and efficiency. Early compiler research needed a way to parse languages deterministically with minimal lookahead. FIRST and FOLLOW sets provide a systematic method to predict parsing actions using only one token of lookahead (LL(1) parsing). Alternatives like backtracking parsers were slower and less predictable. This method was chosen for its clarity and practical performance.

Grammar
  │
  ├─ Production Rules
  │    ├─ Non-terminals
  │    └─ Terminals
  │
  ├─ Compute FIRST sets
  │    └─ Iterative updates until stable
  │
  ├─ Compute FOLLOW sets
  │    └─ Use FIRST sets and positions in rules
  │
  └─ Build Parsing Table
       └─ Use FIRST and FOLLOW to decide productions

Myth Busters - 4 Common Misconceptions

Quick: Do FOLLOW sets include terminals that can appear anywhere after a symbol, or only immediately after? Commit to your answer.

Common Belief: FOLLOW sets include all terminals that can appear anywhere after a non-terminal in any string.

Reality: FOLLOW sets include only terminals that can appear immediately after the non-terminal in some valid derivation.

Why it matters: Misunderstanding this leads to incorrect FOLLOW sets, causing parsing tables to be wrong and parsers to fail or behave unpredictably.

Quick: Can FIRST sets of non-terminals include other non-terminals? Commit to your answer.

Common Belief: FIRST sets can contain non-terminals as well as terminals.

Reality: FIRST sets contain only terminals and possibly ε (empty string), never non-terminals.

Why it matters: Confusing this causes errors in parser construction and misunderstanding of how parsing decisions are made.

Quick: Does the presence of ε in FIRST sets always mean the grammar is ambiguous? Commit to your answer.

Common Belief: If ε is in a FIRST set, the grammar must be ambiguous or problematic.

Reality: ε in FIRST sets is normal and allowed; ambiguity arises only if parsing table conflicts occur due to overlapping FIRST and FOLLOW sets.

Why it matters: This misconception can lead to unnecessary grammar rewriting or rejection of valid grammars.

Quick: Are FIRST and FOLLOW sets only useful for LL(1) parsers? Commit to your answer.

Common Belief: FIRST and FOLLOW sets are only relevant for LL(1) parsing and not useful elsewhere.

Reality: While primarily used in LL(1) parsing, FIRST and FOLLOW concepts also help in other parsing techniques and grammar analysis.

Why it matters: Limiting their use reduces understanding of grammar properties and parser design options.

Expert Zone

1

FOLLOW sets depend not only on immediate grammar rules but also on indirect dependencies, requiring careful iterative propagation to capture all possibilities.

2

Handling left recursion in grammars affects FIRST and FOLLOW computations and often requires grammar transformation before these sets can be correctly computed.

3

In ambiguous grammars, FIRST and FOLLOW sets can overlap, but advanced parser generators use extended lookahead or context to resolve conflicts beyond simple FIRST/FOLLOW analysis.

When NOT to use

FIRST and FOLLOW sets are less effective for parsing techniques that require more than one token lookahead or use bottom-up parsing like LR parsers. In such cases, more powerful methods like LR(1) item sets or GLR parsing are preferred.

Production Patterns

In production compilers, FIRST and FOLLOW sets are used to build LL(1) parsing tables for simple languages or subsets. They also assist in error recovery by predicting expected tokens. Advanced parser generators integrate these sets with lookahead sets and conflict resolution strategies to handle complex grammars.

Connections

Context-Free Grammars

FIRST and FOLLOW sets are defined based on the structure of context-free grammars.

Understanding CFGs deeply helps grasp why FIRST and FOLLOW sets work and how they relate to language syntax.

Predictive Parsing

FIRST and FOLLOW sets enable predictive parsing by guiding parser decisions with one token lookahead.

Knowing these sets clarifies how parsers avoid backtracking and parse efficiently.

Natural Language Processing (NLP)

Similar concepts of predicting next words or phrases in sentences relate to FIRST and FOLLOW sets in grammar analysis.

Recognizing this connection shows how language prediction principles apply across computer languages and human languages.

Common Pitfalls

#1 Ignoring ε-productions when computing FIRST sets.

Wrong approach:

FIRST(A) = {a} when A → a | ε (missing ε)

Correct approach:

FIRST(A) = {a, ε} correctly including empty string

Root cause:

Misunderstanding that ε-productions contribute to FIRST sets and affect FOLLOW computations.

#2 Adding FOLLOW sets incorrectly by not considering positions of non-terminals in productions.

Wrong approach:

FOLLOW(B) = {} when B appears before terminal c in A → αB c β

Correct approach:

FOLLOW(B) includes c because c can follow B in the derivation

Root cause:

Not analyzing the grammar rule structure carefully to propagate FOLLOW sets.

#3 Confusing terminals and non-terminals in FIRST and FOLLOW sets.

Wrong approach:

Including non-terminals like A or B inside FIRST or FOLLOW sets

Correct approach:

FIRST and FOLLOW sets contain only terminals and possibly ε (for FIRST sets)

Root cause:

Lack of clarity on the definition and purpose of these sets.

Key Takeaways

FIRST sets tell which terminals can appear at the start of strings derived from a grammar symbol, including the empty string if applicable.

FOLLOW sets tell which terminals can appear immediately after a non-terminal in some valid string, guiding parser decisions.

Computing FIRST and FOLLOW sets requires iterative analysis of grammar rules until no new terminals can be added.

These sets are essential for building efficient, deterministic parsers like LL(1) and detecting grammar ambiguities.

Handling empty string productions and understanding the interaction between FIRST and FOLLOW sets is key to robust parser design.

Practice

1. What does the FIRST set of a non-terminal in a grammar represent?

easy

A. The set of all non-terminals reachable from that non-terminal

B. The set of terminals that can appear immediately after that non-terminal

C. The set of all terminals in the grammar

D. The set of terminals that can appear at the start of strings derived from that non-terminal

Solution

1. Step 1: Understand the definition of FIRST set

   The FIRST set of a non-terminal includes all terminals that can appear at the beginning of any string derived from that non-terminal.

2. Step 2: Differentiate from FOLLOW set

   FOLLOW sets represent terminals that can appear immediately after the non-terminal, not at the start.

3. Final Answer:

   The set of terminals that can appear at the start of strings derived from that non-terminal -> Option D

4. Quick Check:

   FIRST set = starting terminals [OK]

Hint: FIRST = start terminals of derivations [OK]

Common Mistakes:

• Confusing FIRST with FOLLOW sets
• Thinking FIRST includes all terminals in grammar
• Mixing terminals and non-terminals in FIRST

2. Which of the following is the correct way to compute the FOLLOW set of a non-terminal A in a grammar?

easy

A. Include all terminals that can start strings derived from A

B. Include all non-terminals reachable from A

C. Include terminals that can appear immediately after A in any production, plus FOLLOW of the start symbol if A can be at the end

D. Include only the terminals that appear before A in productions

Solution

1. Step 1: Understand FOLLOW set definition

   FOLLOW(A) contains terminals that can appear immediately after A in some sentential form.

2. Step 2: Consider special case for end of productions

   If A appears at the end of a production, FOLLOW of the production's left side non-terminal is included in FOLLOW(A).

3. Final Answer:

   Include terminals that can appear immediately after A in any production, plus FOLLOW of the start symbol if A can be at the end -> Option C

4. Quick Check:

   FOLLOW set = terminals after A [OK]

Hint: FOLLOW = terminals after non-terminal in productions [OK]

Common Mistakes:

• Confusing FOLLOW with FIRST sets
• Ignoring FOLLOW of start symbol when non-terminal is at production end
• Including terminals before the non-terminal

3. Given the grammar:

S -> A B
A -> a | ε
B -> b

What is the FIRST set of B?

medium

A. {b}

B. {a, b}

C. {ε}

D. {a}

Solution

1. Step 1: Analyze productions of B

   B produces only terminal 'b', so FIRST(B) includes 'b'.

2. Step 2: Check for epsilon in B

   There is no epsilon (empty string) production for B, so ε is not included.

3. Final Answer:

   {b} -> Option A

4. Quick Check:

   FIRST(B) = {b} [OK]

Hint: FIRST of terminal-only production is that terminal [OK]

Common Mistakes:

• Including ε when no epsilon production exists
• Mixing FIRST sets of A and B
• Adding terminals from other productions incorrectly

4. Consider the grammar:

E -> T E'
E' -> + T E' | ε
T -> int

Which mistake is present if FOLLOW(E') is computed as {+} only?

medium

A. Ignoring that E' can be at the end of production, so FOLLOW(E) should be included

B. Including terminals from FIRST sets instead of FOLLOW sets

C. Adding terminals that never appear after E'

D. Confusing E' with T in FOLLOW computation

Solution

1. Step 1: Identify where E' appears

   E' appears at the end of production E -> T E'.

2. Step 2: Apply FOLLOW rule for end non-terminal

   Since E' is at the end, FOLLOW(E) must be included in FOLLOW(E'). Ignoring this causes incomplete FOLLOW set.

3. Final Answer:

   Ignoring that E' can be at the end of production, so FOLLOW(E) should be included -> Option A

4. Quick Check:

   FOLLOW of end non-terminal includes FOLLOW of left side [OK]

Hint: Add FOLLOW of left side if non-terminal is at production end [OK]

Common Mistakes:

• Forgetting to add FOLLOW of left side non-terminal
• Mixing FIRST and FOLLOW sets
• Assuming FOLLOW only includes terminals directly after

5. Given the grammar:

S -> A B C
A -> a | ε
B -> b | ε
C -> c

What is the FIRST set of S?

hard

A. {a, b, c, ε}

B. {a, b, c}

C. {a, b, ε}

D. {a, b}

Solution

1. Step 1: Compute FIRST sets of A, B, and C

   FIRST(A) = {a, ε}, FIRST(B) = {b, ε}, FIRST(C) = {c}.

2. Step 2: Calculate FIRST(S) considering ε in A and B

   Since A and B can be ε, FIRST(S) includes FIRST(A) without ε, FIRST(B) without ε, and FIRST(C). So FIRST(S) = {a, b, c}.

3. Final Answer:

   {a, b, c} -> Option B

4. Quick Check:

   FIRST(S) = {a, b, c} considering ε in A and B [OK]

Hint: Include FIRST of next symbol if previous can be ε [OK]

Common Mistakes:

• Including ε in FIRST(S) incorrectly
• Ignoring ε in A or B when computing FIRST(S)
• Only taking FIRST(A) and ignoring B and C