Skip to main content

FIRST & FOLLOW Calculation

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.

PRACTICE PROBLEMS BASED ON CALCULATING FIRST AND FOLLOW-

Problem-01:

Calculate the first and follow functions for the given grammar-
S → aBDh
B → cC
C → bC / ∈
D → EF
E → g / ∈
F → f / ∈

Solution-

The first and follow functions are as follows-

First Functions-

  • First(S) = { a }
  • First(B) = { c }
  • First(C) = { b , ∈ }
  • First(D) = { First(E) – ∈ } ∪ First(F) = { g , f , ∈ }
  • First(E) = { g , ∈ }
  • First(F) = { f , ∈ }

Follow Functions-

  • Follow(S) = { $ }
  • Follow(B) = { First(D) – ∈ } ∪ First(h) = { g , f , h }
  • Follow(C) = Follow(B) = { g , f , h }
  • Follow(D) = First(h) = { h }
  • Follow(E) = { First(F) – ∈ } ∪ Follow(D) = { f , h }
  • Follow(F) = Follow(D) = { h }

Problem-02:

Calculate the first and follow functions for the given grammar-
S → A
A → aB / Ad
B → b
C → g

Solution-

We have-
  • The given grammar is left recursive.
  • So, we first remove left recursion from the given grammar.
After eliminating left recursion, we get the following grammar-
S → A
A → aBA’
A’ → dA’ / ∈
B → b
C → g
Now, the first and follow functions are as follows-

First Functions-

  • First(S) = First(A) = { a }
  • First(A) = { a }
  • First(A’) = { d , ∈ }
  • First(B) = { b }
  • First(C) = { g }

Follow Functions-

  • Follow(S) = { $ }
  • Follow(A) = Follow(S) = { $ }
  • Follow(A’) = Follow(A) = { $ }
  • Follow(B) = { First(A’) – ∈ } ∪ Follow(A) = { d , $ }
  • Follow(C) = NA

Problem-03:

Calculate the first and follow functions for the given grammar-
S → (L) / a
L → SL’
L’ → ,SL’ / ∈

Solution-

The first and follow functions are as follows-

First Functions-

  • First(S) = { ( , a }
  • First(L) = First(S) = { ( , a }
  • First(L’) = { , , ∈ }

Follow Functions-

  • Follow(S) = { $ } ∪ { First(L’) – ∈ } ∪ Follow(L) ∪ Follow(L’) = { $ , , , ) }
  • Follow(L) = { ) }
  • Follow(L’) = Follow(L) = { ) }

Problem-04:

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

Solution-

The first and follow functions are as follows-

First Functions-

  • First(S) = { First(A) – ∈ } ∪ First(a) ∪ { First(B) – ∈ } ∪ First(b) = { a , b }
  • First(A) = { ∈ }
  • First(B) = { ∈ }

Follow Functions-

  • Follow(S) = { $ }
  • Follow(A) = First(a) ∪ First(b) = { a , b }
  • Follow(B) = First(b) ∪ First(a) = { a , b }

Problem-05:

Calculate the first and follow functions for the given grammar-
E → E + T / T
T → T x F / F
F → (E) / id

Solution-

We have-
  • The given grammar is left recursive.
  • So, we first remove left recursion from the given grammar.
After eliminating left recursion, we get the following grammar-
E → TE’
E’ → + TE’ / ∈
T → FT’
T’ → x FT’ / ∈
F → (E) / id
Now, the first and follow functions are as follows-

First Functions-

  • First(E) = First(T) = First(F) = { ( , id }
  • First(E’) = { + , ∈ }
  • First(T) = First(F) = { ( , id }
  • First(T’) = { x , ∈ }
  • First(F) = { ( , id }

Follow Functions-

  • Follow(E) = { $ , ) }
  • Follow(E’) = Follow(E) = { $ , ) }
  • Follow(T) = { First(E’) – ∈ } ∪ Follow(E) ∪ Follow(E’) = { + , $ , ) }
  • Follow(T’) = Follow(T) = { + , $ , ) }
  • Follow(F) = { First(T’) – ∈ } ∪ Follow(T) ∪ Follow(T’) = { x , + , $ , ) }

Problem-06:

Calculate the first and follow functions for the given grammar-
S → ACB / CbB / Ba
A → da / BC
B → g / ∈
C → h / ∈

Solution-


The first and follow functions are as follows-

First Functions-

  • First(S) = { First(A) – ∈ }  ∪ { First(C) – ∈ } ∪ First(B) ∪ First(b) ∪ { First(B) – ∈ } ∪ First(a) = { d , g , h , ∈ , b , a }
  • First(A) = First(d) ∪ { First(B) – ∈ } ∪ First(C) = { d , g , h , ∈ }
  • First(B) = { g , ∈ }
  • First(C) = { h , ∈ }

Follow Functions-

  • Follow(S) = { $ }
  • Follow(A) = { First(C) – ∈ } ∪ { First(B) – ∈ } ∪ Follow(S) = { h , g , $ }
  • Follow(B) = Follow(S) ∪ First(a) ∪ { First(C) – ∈ } ∪ Follow(A) = { $ , a , h , g }
  • Follow(C) = { First(B) – ∈ } ∪ Follow(S) ∪ First(b) ∪ Follow(A) = { g , $ , b , h }
To gain better understanding about calculating first and follow functions,

Comments

Post a Comment

Popular posts from this blog

Code Optimization | Code Optimization Techniques

Code Optimization- Code Optimization is an approach to enhance the performance of the code. The process of code optimization involves- Eliminating the unwanted code lines Rearranging the statements of the code Advantages- The optimized code has the following advantages- Optimized code has faster execution speed. Optimized code utilizes the memory efficiently. Optimized code gives better performance. Code Optimization Techniques- Important code optimization techniques are- Compile Time Evaluation Common sub-expression elimination Dead Code Elimination Code Movement Strength Reduction 1. Compile Time Evaluation- Two techniques that falls under compile time evaluation are- A) Constant Folding- In this technique, As the name suggests, it involves folding the constants. The expressions that contain the operands having constant values at compile time are evaluated. Those express...
Post a Comment
Read more

Elimination of Left Factoring

In left factoring, We make one production for each common prefixes. The common prefix may be a terminal or a non-terminal or a combination of both. Rest of the derivation is added by new productions. The grammar obtained after the process of left factoring is called as Left Factored Grammar . Example-   PRACTICE PROBLEMS BASED ON LEFT FACTORING- Problem-01: Do left factoring in the following grammar- S → iEtS / iEtSeS / a E → b Solution- The left factored grammar is- S → iEtSS’ / a S’ → eS / ∈ E → b Problem-02: Do left factoring in the following grammar- A → aAB / aBc / aAc Solution- Step-01: A → aA’ A’ → AB / Bc / Ac Again, this is a grammar with common prefixes. Step-02: A → aA’ A’ → AD / Bc D → B / c This is a left factored grammar. Problem-03: Do left factoring in the following grammar- S → bSSaaS / bSSaSb / bSb / a Solution- ...
Post a Comment
Read more

Testing a Program – An Example

Question: Write a set of test cases – specific set of data – to properly test a relatively Simple program. Create a set of test data for the program - data the program must handle correctly to be considered a successful program. Here’s a description of the program: “The program reads three integer values from an input dialog. The three values represent the lengths of the sides of a triangle. The program displays a message that states whether the triangle is scalene, isosceles, or equilateral”. Code: The function triangle takes three integer parameters that are interpreted as the lengths of the sides of a triangle. It returns whether the triangle is equilateral (three lengths equal), isosceles (two lengths equal), scalene (no lengths equal), or invalid (impossible lengths). Evaluate your test cases: Evaluate your set of test cases by using it to answer the following questions. Give yourself one point for each “YES” answer. Do you have a test case that represents a ...
Post a Comment
Read more