FIRST and FOLLOW sets in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the FIRST set of a terminal symbol.

Compiler Design

FIRST([1]) = { { [1] } }

Drag options to blanks, or click blank then click option'

Aepsilon

Bnonterminal

Cterminal

Dstart_symbol

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing terminal with nonterminal symbols.

Thinking FIRST set of terminal is empty.

The FIRST set of a terminal symbol is the symbol itself.

2fill in blank

medium

Complete the code to add epsilon to the FIRST set when a production can derive epsilon.

Compiler Design

If a production A -> [1] can derive epsilon, then epsilon is added to FIRST(A).

Drag options to blanks, or click blank then click option'

Aa start symbol

Ba terminal

Ca nonterminal

Depsilon

Attempts:

3 left

💡 Hint

Common Mistakes

Adding epsilon to FIRST sets incorrectly for terminals.

Forgetting to add epsilon when production derives empty string.

If the right side of a production can produce epsilon (empty string), then epsilon is included in the FIRST set of the left side nonterminal.

3fill in blank

hard

Fix the error in the statement about FOLLOW sets: FOLLOW(A) contains {{BLANK_1}} if A appears before terminal b in some production.

Compiler Design

FOLLOW(A) contains [1] if A appears before terminal b in some production.

Drag options to blanks, or click blank then click option'

AFIRST(b)

BFOLLOW(b)

CFIRST(A)

DFOLLOW(A)

Attempts:

3 left

💡 Hint

Common Mistakes

Adding FOLLOW(b) instead of FIRST(b).

Confusing FOLLOW and FIRST sets.

The FOLLOW set of A includes FIRST of the symbol that follows A in a production, if that symbol is a terminal or nonterminal.

4fill in blank

hard

Fill both blanks to complete the rule for FOLLOW sets: If A -> αB{{BLANK_1}}β and FIRST({{BLANK_2}}) contains epsilon, then FOLLOW(B) includes FOLLOW(A).

Compiler Design

If A -> αB[1]β and FIRST([2]) contains epsilon, then FOLLOW(B) includes FOLLOW(A).

Drag options to blanks, or click blank then click option'

Aβ

Bα

DB

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up α and β in the production.

Forgetting to check if FIRST(β) contains epsilon.

If the symbol after B is β and FIRST(β) contains epsilon, then FOLLOW(B) includes FOLLOW(A).

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension for FIRST sets: first_sets = {{{BLANK_1}}: {{BLANK_2}} for {{BLANK_3}} in grammar}

Compiler Design

first_sets = [1]: [2] for [3] in grammar}

Drag options to blanks, or click blank then click option'

Anonterminal

Bcompute_first(nonterminal)

Dterminal

Attempts:

3 left

💡 Hint

Common Mistakes

Using terminal instead of nonterminal as keys.

Not calling the function to compute FIRST sets.

This comprehension creates a dictionary mapping each nonterminal to its FIRST set computed by a function.

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