Scribd
Upload
167 views4 pages

First and Follow Problems

First sets contain the terminal symbols that can begin strings derived from each nonterminal, while follow sets contain the terminals that can follow each nonterminal. The document provides rules for calculating first and follow sets based on a grammar's production rules, and examples of applying the rules to sample grammars. It explains that first and follow sets are needed for LL(1) parsing.

Uploaded by

Fakibazz frnds
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
167 views4 pages

First and Follow Problems

First sets contain the terminal symbols that can begin strings derived from each nonterminal, while follow sets contain the terminals that can follow each nonterminal. The document provides rules for calculating first and follow sets based on a grammar's production rules, and examples of applying the rules to sample grammars. It explains that first and follow sets are needed for LL(1) parsing.

Uploaded by

Fakibazz frnds
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

First and Follow-

First and Follow sets are needed so that the parser can properly apply the needed production rule at
the correct position.

First Function-

First(α) is a set of terminal symbols that begin in strings derived from α.


Example-
 
Consider the production rule-
A → abc / def / ghi
Then, we have-
First(A) = { a , d , g }

Rules For Calculating First Function-


 
Rule-01:
 
For a production rule X → ∈,
First(X) = { ∈ }
 
Rule-02:
 
For any terminal symbol ‘a’,
First(a) = { a }
Rule-03:
 
For a production rule X → Y1Y2Y3,
 
Calculating First(X)
 
● If ∈ ∉ First(Y1), then First(X) = First(Y1)
● If ∈ ∈ First(Y1), then First(X) = { First(Y1) – ∈ } ∪ First(Y2Y3)
 
Calculating First(Y2Y3)
 
● If ∈ ∉ First(Y2), then First(Y2Y3) = First(Y2)
● If ∈ ∈ First(Y2), then First(Y2Y3) = { First(Y2) – ∈ } ∪ First(Y3)
 
Similarly, we can make expansion for any production rule X → Y1Y2Y3…..Yn.

Follow Function-

Follow(α) is a set of terminal symbols that appear immediately to the right of α.

Rules For Calculating Follow Function-


 
Rule-01:
 
For the start symbol S, place $ in Follow(S).
 
Rule-02:
 
For any production rule A → αB,
Follow(B) = Follow(A)
 
Rule-03:
 
For any production rule A → αBβ,
 
● If ∈ ∉ First(β), then Follow(B) = First(β)
● If ∈ ∈ First(β), then Follow(B) = { First(β) – ∈ } ∪ Follow(A)
 
Important Notes-
 
Note-01:
 
● ∈ may appear in the first function of a non-terminal.
● ∈ will never appear in the follow function of a non-terminal.
 
Note-02:
 
● Before calculating the first and follow functions, eliminate Left Recursion from the
grammar, if present.
 
Note-03:
 
We calculate the follow function of a non-terminal by looking where it is present on the RHS
of a production rule.

Find out first and follow from the following grammars and construct the
LL(1) from them.

Problem-01:
 
Calculate the first and follow functions for the given grammar-
 
S → aBDh
B → cC
C → bC / ∈
D → EF
E → g / ∈
F → f / ∈
Problem-02:
 
Calculate the first and follow functions for the given grammar-
 
S → (L) / a
L → SL’
L’ → ,SL’ / ∈

Problem-03:
 
Calculate the first and follow functions for the given grammar-
 
S → AaAb / BbBa
A→∈
B→∈

You might also like