Cal11 calculator
Search calculator...

First and Follow Set Calculator

Reviewed by Calculator Editorial Team

This First and Follow Set Calculator helps you determine the FIRST and FOLLOW sets for non-terminals in a context-free grammar. These sets are essential for parsing algorithms like LL(1) and are used in compiler design and formal language theory.

What Are FIRST and FOLLOW Sets?

In formal language theory, FIRST and FOLLOW sets are fundamental concepts used in parsing algorithms. They help determine which terminals can appear next in a derivation sequence.

FIRST set of a non-terminal A is the set of terminals that begin the strings derived from A. It includes ε (epsilon) if A can derive an empty string.

FOLLOW set of a non-terminal A is the set of terminals that can appear immediately to the right of A in any sentential form. It includes $ (end marker) if A can appear at the end of a string.

These sets are crucial for constructing parsing tables in top-down parsers like LL(1).

How to Calculate FIRST Sets

To calculate the FIRST set for a non-terminal A:

  1. If A produces a terminal a, then add a to FIRST(A).
  2. If A produces ε, then add ε to FIRST(A).
  3. If A produces a non-terminal B, then add FIRST(B) to FIRST(A), excluding ε.
  4. If all productions of A can produce ε, then add ε to FIRST(A).

Formal Definition:

FIRST(A) = {a | A ⇒* a...} ∪ {ε | A ⇒* ε}

For example, consider the grammar:

S → aB | bA
B → b | ε

The FIRST sets would be:

  • FIRST(S) = {a, b}
  • FIRST(B) = {b, ε}

How to Calculate FOLLOW Sets

To calculate the FOLLOW set for a non-terminal A:

  1. Add $ to FOLLOW(S) where S is the start symbol.
  2. If there's a production A → αBβ, then add FIRST(β) to FOLLOW(B), excluding ε.
  3. If there's a production A → αB or A → αBβ where FIRST(β) contains ε, then add FOLLOW(A) to FOLLOW(B).

Formal Definition:

FOLLOW(A) = {a | S ⇒* αAaβ} ∪ {$ | S ⇒* αA}

Using the same example grammar:

S → aB | bA
B → b | ε

The FOLLOW sets would be:

  • FOLLOW(S) = {$}
  • FOLLOW(A) = {$, b}
  • FOLLOW(B) = {$, b}

Practical Applications

FIRST and FOLLOW sets are used in:

  • Compiler design for syntax analysis
  • Designing LL(1) parsers
  • Language processing algorithms
  • Automated theorem provers

They help determine the validity of a grammar and guide the construction of parsing tables.

Common Mistakes

When calculating FIRST and FOLLOW sets, common errors include:

  • Forgetting to include ε in FIRST sets when appropriate
  • Not properly handling the end marker $ in FOLLOW sets
  • Incorrectly propagating FIRST sets when they contain ε
  • Missing recursive cases in the calculations

Always verify your calculations by checking each production rule systematically.

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 non-terminal, while the FOLLOW set contains the terminals that can appear immediately after the non-terminal in any derivation.

When should I include ε in a FIRST set?

You should include ε in the FIRST set of a non-terminal if that non-terminal can derive an empty string (ε).

How do I know when to include $ in a FOLLOW set?

You should include $ in the FOLLOW set of the start symbol, and in any non-terminal that can appear at the end of a derivation.

What if a non-terminal's FIRST set contains ε?

If a non-terminal's FIRST set contains ε, you need to consider the next symbol in the production when calculating FOLLOW sets.