First Symbols in Compiler

In this class, we discuss First Symbols in Compiler.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of syntax analysis basics. Click Here.

How to identify first symbols in a context-free grammar? We discuss this in this class.

What is the use of the first symbol? We will discuss this in later classes.

First Symbol: The set of terminal symbols that begin in the string for a given non-terminal.

The definition does not help the reader to understand. We take an example and understand.

Example:

We consider the below context-free grammar.

S – aABC | bA

A – b

B – c

C – d

First(S) is the first terminal symbol encountered in the productions of S.

First(S) = First(a) U First(b)

Take First symbol in each production of S.

The FIRST of the terminal symbol is the symbol itself.

First(S) = a U b

First(S) = {a,b}

Similarly, First(A) = {b}

First(B) = {c}

First(C) = {d}

Example 2:

S – Bb | Cd

B – aB | ε

C – cC | ε

First(S) = First(B) U First(C)

First(S) = {a,ε} U {c,ε}

Place ε in B and C.

If we place epsilon in place of B in production ‘A’. we get the First(S) = {b}

If we place epsilon in place of C in production ‘A’. We get First(S) = {d}

So First(S) = {a,b,c,d}

First(B) = {a, ε}

First(C) = {c, ε}