FIRST and FOLLOW sets in Compiler Design - Full Explanation

Introduction

When building a compiler, one big challenge is figuring out how to understand the structure of sentences in a programming language. FIRST and FOLLOW sets help solve this by guiding how to predict what parts of the language come next, making parsing easier and more accurate.

Explanation

FIRST Set

The FIRST set of a grammar symbol tells us which terminals (basic symbols) can appear first in strings derived from that symbol. For example, if a symbol can start with 'a' or 'b', its FIRST set includes those terminals. This helps the parser decide what to expect next when reading input.

FIRST sets identify possible starting terminals for a grammar symbol's expansions.

FOLLOW Set

The FOLLOW set of a non-terminal symbol contains terminals that can appear immediately after that symbol in some valid sentence. This means it shows what can come next after the symbol, helping the parser know when a symbol's part is finished and what to expect next.

FOLLOW sets show which terminals can come right after a non-terminal in the language.

How FIRST and FOLLOW Work Together

FIRST and FOLLOW sets work as a team to guide the parser. FIRST sets help decide which rule to use based on the next input symbol, while FOLLOW sets help know when to stop expanding a rule and move on. Together, they prevent confusion and errors during parsing.

FIRST and FOLLOW sets together help the parser make correct decisions about grammar rules.

Handling Empty Strings (Epsilon)

Sometimes a grammar symbol can produce an empty string, called epsilon. When this happens, the FIRST set includes epsilon, and the FOLLOW set becomes important to know what can come after the empty part. This ensures the parser handles optional parts correctly.

Epsilon in FIRST sets means the symbol can be empty, so FOLLOW sets guide what follows next.

Real World Analogy

Imagine reading a recipe where each step can start with certain ingredients (FIRST set) and you also know what ingredients usually come after a step (FOLLOW set). This helps you prepare the right ingredients at the right time without confusion.

FIRST Set → Ingredients that can start a cooking step in a recipe

FOLLOW Set → Ingredients that usually come right after a cooking step

How FIRST and FOLLOW Work Together → Using the start and next ingredients to smoothly follow the recipe steps

Handling Empty Strings (Epsilon) → Steps that can be skipped, so you check what comes next to continue cooking

Diagram

Diagram

┌─────────────┐       ┌─────────────┐
│   FIRST Set │──────▶│  Parser uses │
└─────────────┘       │ to pick rule│
                      └─────────────┘
         ▲                      │
         │                      ▼
┌─────────────┐       ┌─────────────┐
│ FOLLOW Set  │──────▶│ Parser knows│
└─────────────┘       │ when to stop│
                      └─────────────┘

Diagram showing FIRST sets guide rule selection and FOLLOW sets guide when to stop parsing.

Key Facts

FIRST set → The set of terminals that can appear at the start of strings derived from a grammar symbol.

FOLLOW set → The set of terminals that can appear immediately after a non-terminal symbol in some valid sentence.

Epsilon (ε) → A symbol representing an empty string in grammar productions.

Parser → A program component that analyzes the structure of input based on grammar rules.

Common Confusions

Believing FIRST sets include all terminals that appear anywhere in the symbol's expansions.

Believing FIRST sets include all terminals that appear anywhere in the symbol's expansions. FIRST sets only include terminals that can appear at the very start of strings derived from the symbol, not all terminals inside.

Thinking FOLLOW sets apply to terminals as well as non-terminals.

Thinking FOLLOW sets apply to terminals as well as non-terminals. FOLLOW sets are defined only for non-terminal symbols, showing what can come after them.

Assuming epsilon in FIRST means the symbol always produces empty string.

Assuming epsilon in FIRST means the symbol always produces empty string. Epsilon in FIRST means the symbol can produce an empty string, but it may also produce other strings.

Summary

FIRST sets tell which terminals can start strings from a grammar symbol, helping predict input.

FOLLOW sets tell which terminals can come after a non-terminal, guiding when to stop parsing that symbol.

Together, FIRST and FOLLOW sets help parsers make correct decisions and handle optional parts in grammar.

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