Program to Calculate Follow of A Grammar
'/%3E%3Ccircle cx='48' cy='39' r='19' fill='%23f2c9a5'/%3E%3Cpath d='M27 35c3-16 39-17 42 2-8-8-27-9-42-2z' fill='%23374151'/%3E%3Cpath d='M21 86c5-24 49-28 56 0z' fill='%232563eb'/%3E%3Ccircle cx='41' cy='41' r='2' fill='%23111827'/%3E%3Ccircle cx='55' cy='41' r='2' fill='%23111827'/%3E%3Cpath d='M42 52c4 3 9 3 13 0' stroke='%2392400e' stroke-width='3' fill='none' stroke-linecap='round'/%3E%3C/svg%3E)
Reviewed by Calculator Editorial Team
In formal language theory, the FOLLOW set of a non-terminal symbol in a context-free grammar is a set of terminals that can appear immediately to the right of that non-terminal in any sentential form derived from the start symbol. This guide explains how to calculate the FOLLOW set and provides a practical calculator to compute it for your grammar.
What is the FOLLOW Set?
The FOLLOW set is an essential concept in parsing algorithms like LL(1) and LR(1). It complements the FIRST set by identifying what terminals can follow a non-terminal in any valid derivation. For a non-terminal A, FOLLOW(A) is defined as:
- All terminals that can immediately follow A in any production
- The end-of-input marker ($) if A can be the rightmost symbol in a derivation
The FOLLOW set is different from the FIRST set, which contains the first terminals that can appear in any string derived from a non-terminal.
How to Calculate FOLLOW
To calculate the FOLLOW set for a grammar, follow these steps:
- Initialize FOLLOW(S) = {$} where S is the start symbol
- For each production A → αBβ:
- Add FIRST(β) to FOLLOW(B)
- If β can derive ε, add FOLLOW(A) to FOLLOW(B)
- Repeat until no more changes occur
FOLLOW(A) = {a | S ⇒* αAaβ, a ∈ Terminals ∪ {$}}
Algorithm for FOLLOW Calculation
The algorithm for calculating FOLLOW sets involves these key steps:
- Initialize all FOLLOW sets to empty
- Add $ to FOLLOW(S)
- For each production A → αBβ:
- Add FIRST(β) - {ε} to FOLLOW(B)
- If β can derive ε, add FOLLOW(A) to FOLLOW(B)
- Repeat steps 3 until no more changes occur
This process continues until the FOLLOW sets stabilize, meaning no new elements can be added to any FOLLOW set.
Worked Example
Consider the following grammar:
| Non-terminal | Production |
|---|---|
| S | aAd |
| A | bB |
| A | ε |
| B | cB |
| B | ε |
Calculating the FOLLOW sets:
- FOLLOW(S) = {$}
- From S → aAd: FOLLOW(A) = {d}
- From A → bB: FOLLOW(B) = FOLLOW(A) = {d}
- From B → cB: FOLLOW(B) remains {d}
The final FOLLOW sets are:
| Non-terminal | FOLLOW Set |
|---|---|
| S | {$} |
| A | {d} |
| B | {d} |
FAQ
- What is the difference between FIRST and FOLLOW sets?
- The FIRST set contains the first terminals that can appear in any string derived from a non-terminal, while the FOLLOW set contains terminals that can appear immediately after the non-terminal in any derivation.
- When is the FOLLOW set empty?
- The FOLLOW set is empty only if the non-terminal cannot appear in any sentential form. This typically happens with non-terminals that are not reachable from the start symbol.
- How do I handle left recursion in FOLLOW calculation?
- Left recursion doesn't directly affect FOLLOW calculation, but it can make the FIRST set calculation more complex. For FOLLOW, you should still follow the standard algorithm rules.
- Can a non-terminal have multiple terminals in its FOLLOW set?
- Yes, a non-terminal can have multiple terminals in its FOLLOW set if there are multiple different terminals that can appear immediately after it in valid derivations.
- What happens if a non-terminal can derive ε?
- If a non-terminal can derive ε, then the FOLLOW set of that non-terminal is propagated to the FOLLOW set of any non-terminal that appears before it in a production.