Calculate Follow Set

The follow set is a fundamental concept in formal language theory, particularly in the construction of parsing tables for context-free grammars. It helps determine which terminals can appear immediately after a given non-terminal in any valid derivation.

What is the Follow Set?

The follow set of a non-terminal symbol in a context-free grammar is the set of terminals that can appear immediately to the right of that non-terminal in any sentential form derived from the start symbol.

Follow sets are crucial for:

Constructing LL(1) parsing tables
Determining the validity of grammar productions
Identifying potential conflicts in grammar rules

In contrast to the first set (which contains the first terminals of derivations), the follow set contains terminals that can appear after a non-terminal in any derivation.

How to Calculate the Follow Set

The follow set can be calculated using a systematic approach:

Initialize the follow set of the start symbol with the end-of-input marker ($)
For each production rule A → αBβ:
- Add FIRST(β) to FOLLOW(B)
- If β can derive ε, add FOLLOW(A) to FOLLOW(B)
Repeat until no more changes occur

FOLLOW(A) = { t | S ⇒* αAβ, β ⇒* tγ }

This process continues until the follow sets stabilize, meaning no new elements can be added to any follow set.

Example Calculation

Consider the following grammar:

S → aA A → bB | ε B → c

The follow sets for this grammar are:

FOLLOW(S) = {$}
FOLLOW(A) = {$, c}
FOLLOW(B) = {$, c}

This example demonstrates how the follow set propagates through the grammar rules.

Frequently Asked Questions

What is the difference between first and follow sets?

The first set contains the first terminals that can appear in derivations of a non-terminal, while the follow set contains terminals that can appear immediately after a non-terminal in any derivation.

When is the follow set empty?

The follow set is empty only if the non-terminal never appears in any sentential form that can be derived from the start symbol.

How does the follow set help in parsing?

The follow set is used in LL(1) parsing to determine which production to use when encountering a non-terminal, by looking at the next terminal in the input.