Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
First()
2.1.
Rules to find First()
3.
Follow()
3.1.
Rules to find Follow()
4.
Example of First and Follow in Compiler Design
5.
Frequently Asked Questions
5.1.
In which phase of compiler do we use first and follow?
5.2.
What is the need of first and follow in compiler design?
5.3.
Why is first and follow important?
5.4.
What are the rules for generating first and follow sets?
5.5.
Can Epsilon be in first set?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

First and Follow in Compiler Design

Author Ashish Sharma
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this article, we will learn about First and follow in compiler design, rules to find the first and follow in compiler design, and some related examples to find first and follow.

first and follow in compiler design

FIRST and FOLLOW in compiler design are two grammatical functions that help you enter table entries. We will discuss the First and Follow in detail below. If the compiler knew ahead of time what the "initial character and follow up of the string produced when a production rule is applied," it might carefully choose which production rule to apply by comparing it to the current character or token in the input string it sees.

First()

FIRST () is a function that specifies the set of terminals that start a string derived from a production rule. It is the first terminal that appears on the right-hand side of the production. For example,

If the Input string is 

T->*FT’/ε

Here we find out that T has two productions like T->*FT’ and T->ε, after viewing this we found the first of T in both the production statement which is * and ε.

Then the first of the string will be {*,ε}.

Rules to find First()

To find the first() of the grammar symbol, then we have to apply the following set of rules to the given grammar:-

  • If X is a terminal, then First(X) is {X}.
  • If X is a non-terminal and X tends to aα is production, then add ‘a’ to the first of X. if X->ε, then add null to the First(X).
  • If X_>YZ then if First(Y)=ε, then First(X) = { First(Y)-ε} U First(Z).
  • If X->YZ, then if First(X)=Y, then First(Y)=teminal but null then First(X)=First(Y)=terminals.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Follow()

Follow () is a set of terminal symbols that can be displayed just to the right of the non-terminal symbol in any sentence format. It is the first non-terminal appearing after the given terminal symbol on the right-hand side of production.

For example,

If the input string is

E->TE’, F->(E)/id

Here we found that on the right-hand side of the production statement where is the E occurs, we only found E in the production F->(E)/id through which we found the follow of E.

Then the output Follow of E = { ) }, as ‘)’ is the non-terminal in the input string on the right-hand side of the production.

Rules to find Follow()

To find the follow(A) of the grammar symbol, then we have to apply the following set of rules to the given grammar:-

  • $ is a follow of ‘S’(start symbol).
  • If A->αBβ,β!=ε, then first(β) is in follow(B).
  • If A->αB or A->αBβ where First(β)=ε, then everything in Follow(A) is a Follow(B).

Example of First and Follow in Compiler Design

Let us consider grammar to show how to find the first and follow in compiler design.

E->TE’
E’->+TE’/ε
T->FT’
T’->*FT’/ε
F->(ε)/id

Here,

Terminals are id, *, +, ε, (, )

Non-terminals are E, E’, T, T’, F

Now let’s try to find the first of ‘E’. here on the right-hand side of the production E->TE’ is T which is a non-terminal but we have to find the terminals so to find terminals we move to the production T->FT’ in which the first element is again a non-terminal, so we move to the third production F->(ε)/id in which the first element is a terminal which will be the first of E.

So, First(E)={(, id}  

Now let’s try to find the follow of ‘E’, to find this we find the production in which ‘E’ is on the right-hand side and we get production which is F->(E)/id, so the follow will be the next non-terminal followed by the terminals which are ‘)’ and in the follow ‘$’ is always added. So the follow(E)={$,)} 

On repeating the above steps to find the first and follow in compiler design, we get

Non-terminals First() Follow()
E {(,id)} {$,)}
E' {+,∈} {$,)}
T {*,∈} {$,+,)}
T' {(,id)} {+,),$}
F {(,id} {+,),$,*}

Frequently Asked Questions

In which phase of compiler do we use first and follow?

It is used during the parser table construction, first and follow sets are created to find the correct position of any terminal in the derivation.

What is the need of first and follow in compiler design?

First() and Follow() are functions that help the parser to apply the needed rule at the correct position. It also provides selected information for recursive descent parsers.

Why is first and follow important?

first and follow are important because they help the parser determine which production rule to apply to the given input. First tells which terminal can start production whereas the follows tells the parser what terminal can follow a non-terminal.

What are the rules for generating first and follow sets?

First sets are generated by adding all terminals and non-terminals that can be derived from a production rule's left side. Then follows sets are generated after adding all terminals that can appear after the non-terminal in a right-hand side of a production rule. 

Can Epsilon be in first set?

Yes, epsilon can be in the first set of a grammar if a production rule allows a non-terminal to derive the empty string (epsilon). This indicates that the non-terminal can be replaced with nothing in some derivations.

Conclusion

In this article, we have extensively discussed the introduction to first and follow in compiler design. We have started with an introduction to First and Follow in compiler design, then a gave a brief description about first and follow with examples, then rules to find the first and follow and examples on it.

Recommended Reading:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Activation Tree in Compiler Design
Next article
Inherited Attribute in Compiler Design
Live masterclass