Cal11 calculator
Search calculator...

Calculate First and Follow Sets

Reviewed by Calculator Editorial Team

First and Follow sets are fundamental concepts in formal language theory, particularly in the construction of parsing tables for top-down parsers. These sets help determine the validity of productions in a context-free grammar and are essential for syntax analysis.

What are First and Follow Sets?

In formal language theory, particularly in the study of context-free grammars, First and Follow sets are used to determine the validity of productions during syntax analysis. These sets help in constructing parsing tables for top-down parsers like LL(1) parsers.

Key Points:

  • First sets contain the set of terminals that can appear as the first symbol in any string derived from a given non-terminal.
  • Follow sets contain the set of terminals that can appear immediately after a given non-terminal in any sentential form.
  • These sets are crucial for determining the validity of productions in a grammar.

The First set of a non-terminal A, denoted as FIRST(A), is the set of terminals that can appear as the first symbol in any string derived from A. If A can derive the empty string ε, then ε is also included in FIRST(A).

The Follow set of a non-terminal A, denoted as FOLLOW(A), is the set of terminals that can appear immediately to the right of A in any sentential form. The Follow set is always a set of terminals, and ε is never included in the Follow set.

How to Calculate First Sets

Calculating the First sets for a context-free grammar involves the following steps:

  1. Initialize FIRST(X) = ∅ for all non-terminals X.
  2. For each production X → α:
    • If α is a terminal a, add a to FIRST(X).
    • If α is ε, add ε to FIRST(X).
    • If α is a non-terminal Y, add FIRST(Y) to FIRST(X).
    • If α is a sequence of symbols Y₁Y₂...Yₙ, add FIRST(Y₁) to FIRST(X). If Y₁ can derive ε, add FIRST(Y₂), and so on.
  3. Repeat step 2 until no more changes occur to any FIRST set.

Formal Definition:

For a production X → Y₁Y₂...Yₙ, FIRST(X) = FIRST(Y₁) ∪ FIRST(Y₂) ∪ ... ∪ FIRST(Yₙ) if all Yᵢ can derive ε.

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

How to Calculate Follow Sets

Calculating the Follow sets for a context-free grammar involves the following steps:

  1. Initialize FOLLOW(S) = {$} for the start symbol S, where $ is the end-of-input marker.
  2. Initialize FOLLOW(X) = ∅ for all other non-terminals X.
  3. For each production A → αBβ:
    • Add FIRST(β) to FOLLOW(B), excluding ε.
    • If FIRST(β) contains ε, add FOLLOW(A) to FOLLOW(B).
  4. Repeat step 3 until no more changes occur to any FOLLOW set.

Formal Definition:

For a production A → αBβ, FOLLOW(B) = (FIRST(β) - {ε}) ∪ (if ε ∈ FIRST(β) then FOLLOW(A)).

This process continues until the Follow sets stabilize, meaning no more terminals can be added to any Follow set.

Example Calculation

Consider the following context-free grammar:

S → aB | bA

A → a | aS | bA

B → b | bS | ε

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

First Sets

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

Follow Sets

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

These sets can be used to construct a parsing table for an LL(1) parser.

FAQ

What is the difference between First and Follow sets?

The First set of a non-terminal contains the set of terminals that can appear as the first symbol in any string derived from that non-terminal. The Follow set contains the set of terminals that can appear immediately after the non-terminal in any sentential form.

Why are First and Follow sets important in parsing?

First and Follow sets are crucial for constructing parsing tables for top-down parsers like LL(1) parsers. They help determine the validity of productions and guide the parsing process.

How do you handle ε in First sets?

If a non-terminal can derive the empty string ε, then ε is included in its First set. This indicates that the non-terminal can be skipped during parsing.

What is the end-of-input marker $ in Follow sets?

The end-of-input marker $ is used in Follow sets to indicate that a non-terminal can appear at the end of a string. It is added to the Follow set of the start symbol.

How do you calculate First and Follow sets for a grammar with left recursion?

For grammars with left recursion, you need to handle the recursion carefully. Typically, you would rewrite the grammar to eliminate left recursion before calculating First and Follow sets.