Short trick method to find Follow of any grammar- Compiler Design

Ali Seron Jason

3 days ago

https://www.gyanodhan.com/video/7B2.%20GATE%20CSEIT/Compiler%20Design/275.%20Short%20trick%20method%20to%20find%20Follow%20of%20any%20grammar-%20Compiler%20Design.mp4

Contents

1 Shortcut Method to Find FOLLOW Set in Compiler Design

Short Trick to Find FOLLOW of Any Grammar in Compiler Design

In Compiler Design, the FOLLOW set of a non-terminal helps in parsing and syntax analysis. It determines the set of terminals that can appear immediately after a given non-terminal in the derivation.

Finding the FOLLOW set can be tricky, but here’s a simple and easy trick to compute it quickly!

Steps to Find FOLLOW Set Using a Short Trick

Step 1: Start with the Start Symbol

Always add $ (EOF symbol) to the FOLLOW of the start symbol.
Example: If S is the start symbol, then FOLLOW(S) = {$}.

Step 2: Look at the Right-Hand Side of Productions

If a non-terminal (A) appears in a production before a terminal or non-terminal, then FOLLOW(A) will contain FIRST of the next symbol.
Example:

css

S → A B

Here, FOLLOW(A) ⊇ FIRST(B).

Step 3: If a Non-Terminal is at the End of a Production

If A is at the end of a production, then FOLLOW(A) ⊇ FOLLOW of LHS.
Example:

css

S → A B

Since B is at the end, FOLLOW(B) ⊇ FOLLOW(S).

Step 4: If a Nullable Symbol is Present

If a nullable symbol (ε-production) is after A, then check the next symbol’s FOLLOW or LHS’s FOLLOW.
Example:

css

S → A B (where FIRST(B) contains ε)

Then, FOLLOW(A) ⊇ FOLLOW(S).

Shortcut Formula for FOLLOW

Case	Rule to Follow
`A → αBβ`	`FOLLOW(B) ⊇ FIRST(β) (excluding ε)`
`A → αB` (B is at the end)	`FOLLOW(B) ⊇ FOLLOW(A)`
`A → αBβ`, and `FIRST(β)` contains `ε`	`FOLLOW(B) ⊇ FOLLOW(A)`

Example for Quick Understanding

Grammar:

Step-by-Step Trick to Find FOLLOW

FOLLOW(S) = {$} (Start symbol rule)
FOLLOW(A) ⊇ FIRST(B) = {b, c}
FOLLOW(B) ⊇ FOLLOW(S) = {$}
FOLLOW(C) ⊇ FOLLOW(B) = {$} (Since C → ε)

Final FOLLOW Sets:

Conclusion:

With this short trick, you can quickly find FOLLOW sets without confusion!
Start with $ for the start symbol.
Use FIRST of next symbol for FOLLOW.
If at the end, take FOLLOW of LHS.
Handle ε-productions carefully.

Would you like me to explain with more examples?

Shortcut Method to Find FOLLOW Set in Compiler Design

What is the FOLLOW set?

The FOLLOW(A) of a non-terminal A is the set of terminals that can appear immediately after A in some “sentential form” (derivation).

Short Trick to Find FOLLOW(A):

Step-by-Step Shortcut (Simple Rules):

Rule 1: Start Symbol Rule

If A is the start symbol, then add $ (end marker) to FOLLOW(A).

If S is start → FOLLOW(S) = { $ }

Rule 2: A → αBβ Rule (Non-terminal followed by symbols)

If there is a production like:
A → α B β

Then, everything in FIRST(β) (except ε) is added to FOLLOW(B).

FOLLOW(B) += FIRST(β) – { ε }

Rule 3: A → αB or A → αBβ where β ⇒ ε (Nullable)

If B is at the end, or β ⇒ ε, then
FOLLOW(B) += FOLLOW(A)

This is called “FOLLOW through FOLLOW”
(when nothing follows B, or what follows is nullable)

Rule 4: Keep Applying Until Stable

Apply all above rules iteratively until no new symbols are added.

Example Using Shortcut:

Let’s take a simple grammar:

S → A B  
A → a | ε  
B → b

Step-by-Step:

➤ FIRST Sets:

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

FOLLOW(S):

S is start symbol → FOLLOW(S) = { $ }

FOLLOW(A):

S → A B
→ A is followed by B → so:

FOLLOW(A) += FIRST(B) = { b }

FOLLOW(B):

S → A B → B is at end → FOLLOW(B) += FOLLOW(S) = { $ }

Final FOLLOW Sets:

Non-terminal	FOLLOW
S	{ `$` }
A	{ b }
B	{ `$` }

Short trick method to find Follow of any grammar- Compiler Design