First Follow Set Calculator

First and Follow sets are fundamental concepts in compiler design and formal language theory. They help determine the validity of input strings in context-free grammars. This calculator helps you compute these sets for your grammar rules.

What Are First and Follow Sets?

In formal language theory, First and Follow sets are used to determine the validity of input strings in context-free grammars. These sets help in parsing algorithms like LL(1) parsing.

First Set: The First set of a string or symbol is the set of terminals that begin the strings derived from that symbol.

Follow Set: The Follow set of a non-terminal symbol is the set of terminals that can appear immediately to the right of that symbol in any sentential form derived from the start symbol.

These sets are essential for:

Determining the validity of input strings
Building parsing tables for LL(1) parsers
Understanding the structure of context-free grammars

How to Calculate First Sets

To calculate the First set for a symbol or string, follow these steps:

For a terminal symbol, the First set is the symbol itself.
For a non-terminal symbol, the First set is the union of the First sets of all symbols that can directly derive from it.
For a string of symbols, the First set is the First set of the first symbol in the string, unless that symbol can derive the empty string (ε), in which case you also include the First set of the remaining symbols.

First(X) where X is a symbol or string:

If X is a terminal: First(X) = {X}
If X is a non-terminal: First(X) = ∪ First(α) for all X → α in grammar
If X is a string: First(X) = First(first symbol) ∪ (if first symbol can derive ε, then First(rest of string))

How to Calculate Follow Sets

To calculate the Follow set for a non-terminal symbol, follow these steps:

For the start symbol, add the end-of-input marker ($) to its Follow set.
For productions of the form A → αBβ:
- Add First(β) to Follow(B), excluding ε
- If First(β) contains ε, add Follow(A) to Follow(B)

Follow(A) where A is a non-terminal:

If A is the start symbol: Follow(A) = {$}
For production A → αBβ: Follow(B) = Follow(B) ∪ (First(β) - {ε})
If ε ∈ First(β): Follow(B) = Follow(B) ∪ Follow(A)

Example Calculation

Consider the following grammar:

S → aB | bA
B → cB | d
A → eA | f

Let's calculate First and Follow sets for this grammar.

First Sets

First(S) = {a, b}
First(B) = {c, d}
First(A) = {e, f}

Follow Sets

Follow(S) = {$}
Follow(B) = {$, a, b}
Follow(A) = {$, a, b}

These sets help determine the validity of input strings and build parsing tables for LL(1) parsers.

FAQ

What is the difference between First and Follow sets?

The First set contains the terminals that can appear at the beginning of strings derived from a symbol, while the Follow set contains the terminals that can appear immediately after a symbol in any sentential form.

When are First and Follow sets used?

First and Follow sets are primarily used in compiler design for building parsing tables for LL(1) parsers and determining the validity of input strings in context-free grammars.

How do I handle ε (epsilon) in First sets?

If a symbol can derive ε, you include the First set of the remaining symbols in the string. If the entire string can derive ε, you include ε in the First set.