FIRST and FOLLOW sets in Compiler Design - Mini Project: Build & Apply

Understanding FIRST and FOLLOW Sets in Compiler Design

📖 Scenario: You are learning how compilers analyze grammar rules to understand programming languages. FIRST and FOLLOW sets help the compiler decide which rules to apply when reading code.Imagine you have a simple grammar for arithmetic expressions. You want to find the FIRST and FOLLOW sets for the grammar symbols to help build a parser.

🎯 Goal: Build the FIRST and FOLLOW sets for a given grammar step-by-step. You will create the grammar rules, define helper sets, compute the FIRST sets, and then compute the FOLLOW sets.

📋 What You'll Learn

Create a dictionary representing grammar rules with exact keys and values

Define an empty dictionary for FIRST sets

Write code to compute FIRST sets for all grammar symbols

Write code to compute FOLLOW sets for all grammar symbols

💡 Why This Matters

🌍 Real World

FIRST and FOLLOW sets are used by compilers to decide which grammar rule to apply when parsing code, enabling syntax analysis and error detection.

💼 Career

Understanding FIRST and FOLLOW sets is essential for compiler engineers, language designers, and anyone working on programming language tools.

1

Create the Grammar Rules Dictionary

Create a dictionary called grammar with these exact entries: 'E': ['T E\''], 'E\'': ['+ T E\'', 'ε'], 'T': ['F T\''], 'T\'': ['* F T\'', 'ε'], 'F': ['( E )', 'id']. Use exact string formatting including quotes and escape characters.

Compiler Design

# Create the grammar dictionary with the specified rules
# Your code here

Hint

Use a Python dictionary with keys as non-terminals and values as lists of productions.

2

Initialize the FIRST Sets Dictionary

Create an empty dictionary called first where keys will be grammar symbols and values will be sets representing their FIRST sets.

Compiler Design

grammar = {
    'E': ['T E\''],
    'E\'': ['+ T E\'', 'ε'],
    'T': ['F T\''],
    'T\'': ['* F T\'', 'ε'],
    'F': ['( E )', 'id']
}
# Create an empty dictionary called first
# Your code here

Hint

Use an empty dictionary to store FIRST sets for each symbol.

3

Compute the FIRST Sets for Grammar Symbols

Write code to compute the FIRST sets for all grammar symbols in grammar. Use a loop over grammar keys and assign a set of terminals that can appear first in their productions to first[symbol]. For this step, manually assign these exact FIRST sets: first['E'] = {'(', 'id'}, first['E\''] = {'+', 'ε'}, first['T'] = {'(', 'id'}, first['T\''] = {'*', 'ε'}, first['F'] = {'(', 'id'}.

Compiler Design

grammar = {
    'E': ['T E\''],
    'E\'': ['+ T E\'', 'ε'],
    'T': ['F T\''],
    'T\'': ['* F T\'', 'ε'],
    'F': ['( E )', 'id']
}

first = {}
# Assign the FIRST sets for each grammar symbol as specified
# Your code here

Hint

Assign sets of terminals to each symbol's FIRST set exactly as given.

4

Compute the FOLLOW Sets for Grammar Symbols

Create a dictionary called follow with keys as grammar symbols and values as sets representing their FOLLOW sets. Initialize follow['E'] with the set containing '$' (end of input marker). Then assign these exact FOLLOW sets: follow['E\''] = {')', '$'}, follow['T'] = {'+', ')', '$'}, follow['T\''] = {'+', ')', '$'}, follow['F'] = {'*', '+', ')', '$'}.

Compiler Design

grammar = {
    'E': ['T E\''],
    'E\'': ['+ T E\'', 'ε'],
    'T': ['F T\''],
    'T\'': ['* F T\'', 'ε'],
    'F': ['( E )', 'id']
}

first = {}

first['E'] = {'(', 'id'}
first['E\''] = {'+', 'ε'}
first['T'] = {'(', 'id'}
first['T\''] = {'*', 'ε'}
first['F'] = {'(', 'id'}

# Create the follow dictionary and assign the specified FOLLOW sets
# Your code here

Hint

Initialize the follow dictionary and assign the sets exactly as given.

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