Scribd
Upload
9 views2 pages

Rules

The document outlines the rules for calculating the First and Follow functions in formal grammar. It details specific rules for determining the First set for production rules and terminal symbols, as well as the Follow set based on the position of non-terminals in production rules. Important notes emphasize the handling of epsilon (∈) and the elimination of left recursion before calculations.

Uploaded by

71-Chirag Adve
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Rules

The document outlines the rules for calculating the First and Follow functions in formal grammar. It details specific rules for determining the First set for production rules and terminal symbols, as well as the Follow set based on the position of non-terminals in production rules. Important notes emphasize the handling of epsilon (∈) and the elimination of left recursion before calculations.

Uploaded by

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

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.

You might also like