FIRST and FOLLOW sets in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the FIRST set in compiler design?

The FIRST set of a grammar symbol is the set of terminals that begin the strings derivable from that symbol. It helps predict which production to use based on the next input symbol.

beginner

What does the FOLLOW set represent in a grammar?

The FOLLOW set of a non-terminal is the set of terminals that can appear immediately to the right of that non-terminal in some sentential form. It helps in parsing decisions when the parser expects what can come after a non-terminal.

intermediate

How is the FIRST set of a string of grammar symbols computed?

To find the FIRST set of a string, start from the left symbol and add its FIRST set. If it contains epsilon (empty string), continue to the next symbol and add its FIRST set, and so on, until a symbol without epsilon is found or the string ends.

intermediate

Why are FIRST and FOLLOW sets important in parsing?

They help the parser decide which production rule to apply by predicting the next input symbol. This is essential for constructing parsing tables in LL and LR parsers, enabling efficient syntax analysis.

intermediate

What is the role of epsilon (ε) in FIRST and FOLLOW sets?

Epsilon represents the empty string. If a symbol's FIRST set contains epsilon, it means the symbol can derive an empty string. This affects how FOLLOW sets are computed and how parsing decisions are made.

What does the FIRST set of a non-terminal include?

A All non-terminals reachable from the non-terminal

B Terminals that can appear at the start of strings derived from the non-terminal

C Terminals that can appear immediately after the non-terminal

D Only the epsilon symbol

The FIRST set contains terminals that can begin strings derived from the non-terminal.

Which set helps determine what can follow a non-terminal in a grammar?

A FIRST set

B TERMINAL set

C PRODUCTION set

D FOLLOW set

The FOLLOW set contains terminals that can appear immediately after a non-terminal.

If the FIRST set of a symbol contains epsilon, what does it mean?

A The symbol is a terminal

B The symbol cannot derive any string

C The symbol can derive the empty string

D The symbol is not used in the grammar

Epsilon in the FIRST set means the symbol can produce an empty string.

How is the FOLLOW set used in parsing?

A To decide which production to apply when the next input symbol is in FOLLOW

B To replace non-terminals with terminals

C To list all terminals in the grammar

D To find the first terminal of a string

FOLLOW sets help decide parsing actions when the next input symbol follows a non-terminal.

Which of the following is true about computing FIRST sets for a string of symbols?

A Add FIRST sets of symbols from left to right until a symbol without epsilon is found

B Only the FIRST set of the last symbol matters

C Ignore epsilon in all symbols

D Add FOLLOW sets of all symbols

When computing FIRST for a string, include FIRST sets from left to right until a symbol without epsilon is found.

Explain the difference between FIRST and FOLLOW sets and their roles in syntax analysis.

Think about what each set tells you about the grammar symbols.

Describe the process to compute the FIRST set of a string of grammar symbols.

Consider how epsilon affects the inclusion of subsequent symbols.

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