Cal11 calculator
Search calculator...

First and Follow Sets Calculator

Reviewed by Calculator Editorial Team

This First and Follow Sets Calculator helps you determine the First and Follow sets for non-terminal symbols in a context-free grammar. Understanding these sets is essential for constructing parsing tables in compiler design and formal language theory.

What are First and Follow Sets?

In formal language theory, particularly in the study of context-free grammars, First and Follow sets are fundamental concepts used in parser construction. These sets help determine the validity of productions during parsing.

First Set

The First set of a string of grammar symbols is the set of terminals that can appear as the first symbol of any string derived from that string. For a non-terminal symbol, it's the set of terminals that can appear first in any string derived from that non-terminal.

Follow Set

The Follow set of a non-terminal symbol 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 of the grammar.

Both First and Follow sets are crucial for constructing LL(1) parsing tables, where the parser must decide which production to use based on the current input symbol and the stack top symbol.

How to Calculate First Sets

Calculating First sets involves the following steps:

  1. Initialize the First set of each terminal symbol to be the symbol itself.
  2. Initialize the First set of each non-terminal symbol to be empty.
  3. Repeat until no more changes occur:
    • For each production A → αβ:
      • Add First(β) to First(A) if β can derive ε (the empty string).
      • Add First(β) to First(A) if β cannot derive ε.
First(A → αβ) = First(α) ∪ (if ε ∈ First(α) then First(β) else ∅)

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

How to Calculate Follow Sets

Calculating Follow sets involves the following steps:

  1. Initialize the Follow set of the start symbol to include the end-of-input marker ($).
  2. Initialize the Follow set of all other non-terminals to be empty.
  3. Repeat until no more changes occur:
    • For each production A → αBβ:
      • Add First(β) to Follow(B), excluding ε.
      • If β can derive ε, add Follow(A) to Follow(B).
Follow(B) = Follow(B) ∪ (First(β) - {ε}) ∪ (if ε ∈ First(β) then Follow(A) else ∅)

This iterative process continues until the Follow sets stabilize.

Example Calculation

Consider the following simple grammar:

S → aA A → bB | ε B → c

First Sets

  • First(S) = {a}
  • First(A) = {b, ε}
  • First(B) = {c}

Follow Sets

  • Follow(S) = {$}
  • Follow(A) = {c, $}
  • Follow(B) = {$}

These sets can be used to construct a parsing table for the grammar.

FAQ

What is the difference between First and Follow sets?
The First set contains the terminals that can appear first in any string derived from a given symbol, while the Follow set contains the terminals that can appear immediately after the given symbol in any sentential form.
When is the empty string (ε) included in a First set?
The empty string is included in a First set when the symbol can derive the empty string, either directly or through a series of productions that eventually derive ε.
How are First and Follow sets used in parsing?
First and Follow sets are used to construct parsing tables for top-down parsers like LL(1) parsers. They help determine which production to use based on the current input symbol and the stack top symbol.
What happens if a grammar has left recursion?
Left recursion can cause infinite loops in the calculation of First and Follow sets. Such grammars typically need to be transformed into right-recursive forms before parsing.
Can Follow sets contain the empty string (ε)?
No, Follow sets never contain ε because they represent terminals that can appear after a non-terminal in valid sentential forms, and ε is not a terminal symbol.