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, ε}