Calculate Follow in Context Free Grammar C++

What is the FOLLOW set in context-free grammar?

The FOLLOW set of a non-terminal symbol A in a context-free grammar is the set of terminals that can appear immediately to the right of A in any sentential form derived from the start symbol. The FOLLOW set is crucial for constructing parsing tables in top-down parsers like LL(1) parsers.

Key properties of the FOLLOW set:

• The FOLLOW set of the start symbol always contains the end-of-input marker ($)
• For any production A → αBβ, the FIRST set of β is added to the FOLLOW set of B
• If β can derive the empty string (ε), then the FOLLOW set of A is added to the FOLLOW set of B

How to calculate the FOLLOW set

Calculating the FOLLOW set involves these steps:

1. Initialize the FOLLOW set of the start symbol with the end-of-input marker ($)
2. For each production in the grammar, apply the following rules:
   • If there's a production A → αBβ, add FIRST(β) to FOLLOW(B)
   • If β can derive ε, add FOLLOW(A) to FOLLOW(B)
3. Repeat the process until no more changes occur to any FOLLOW set

This process is typically implemented using an algorithm that iteratively applies these rules until a fixed point is reached.

Worked example

Consider the following context-free grammar:

Calculating the FOLLOW sets:

1. Initialize FOLLOW(S) = {$}
2. From S → aAd, add FIRST(d) = {d} to FOLLOW(A)
3. From S → bBc, add FIRST(c) = {c} to FOLLOW(B)
4. From A → ε, add FOLLOW(S) = {$} to FOLLOW(A)
5. From B → ε, add FOLLOW(S) = {$} to FOLLOW(B)

The final FOLLOW sets are:

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