First Examples in Compiler

In this class, We discuss the First Examples in Compiler.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of How to find the first symbols. Click Here.

Example 1:

S – aBDh

B – cC

C – bC | ε

D – EF

E – g | ε

F – f | ε

Solution:

First(S) = {a}

First(B) = {c}

First(C) = {b, ε}

First(D) = First(E)

First(E) = {g, ε}

Epsilon is present in the first symbols of E. So place epsilon in place of E in the production D – EF

If we place epsilon in place of E in the production D – EF., we need to find the First(F) for First(D).

First(F) = {f, ε}

Finally, First(D) = First(E) U First(F)

We get First(D) = {g, ε} U {f, ε} = {g, f, ε}

Example 2:

S – A

A – aB | Ad

B – b

C – g

The given grammar is having left recursion.

We need to eliminate left recursion and continue finding the first symbols.

How to eliminate left recursion? Click Here.

S – A

A – aBA’

A’ – dA’ | ε

B – b

C – g

Solution:

First(S) = First(A) = a

First(A’) = {d, ε}

First(B) = {b}

First(C) = {g}

Example 3:

E – TE’

E’ – +TE’ | ε

T – FT’

T’ – *FT’ | ε

F – id | (E)

Solution:

First(E) = First(T) = First(F) = {id, (}

First(E’) = {+, ε}

First(T’) = {*, ε}