# Compiler Design | FIRST Set in Syntax Analysis

FIRST(X) for a grammar symbol X is the set of terminals that begin the strings derivable from X.

Rules to compute FIRST set:

1. If x is a terminal, then FIRST(x) = { ‘x’ }
2. If x-> Є, is a production rule, then add Є to FIRST(x).
3. If X->Y1 Y2 Y3….Yn is a production,
1. FIRST(X) = FIRST(Y1)
2. If FIRST(Y1) contains Є then FIRST(X) = { FIRST(Y1) – Є } U { FIRST(Y2) }
3. If FIRST (Yi) contains Є for all i = 1 to n, then add Є to FIRST(X).

Example 1:

```Production Rules of Grammar
E  -> TE’
E’ -> +T E’|Є
T  -> F T’
T’ -> *F T’ | Є
F  -> (E) | id

FIRST sets
FIRST(E) = FIRST(T) = { ( , id }
FIRST(E’) = { +, Є }
FIRST(T) = FIRST(F) = { ( , id }
FIRST(T’) = { *, Є }
FIRST(F) = { ( , id }```

Example 2:

```Production Rules of Grammar
S -> ACB | Cbb | Ba
A -> da | BC
B -> g | Є
C -> h | Є

FIRST sets
FIRST(S) = FIRST(A) U FIRST(B) U FIRST(C)
= { d, g, h, Є, b, a}
FIRST(A) = { d } U FIRST(B) = { d, g , h, Є }
FIRST(B) = { g , Є }
FIRST(C) = { h , Є }```

Notes:

1. The grammar used above is Context-Free Grammar (CFG). Syntax of most of the programming language can be specified using CFG.
2. CFG is of the form A -> B , where A is a single Non-Terminal, and B can be a set of grammar symbols ( i.e. Terminals as well as Non-Terminals)

In the next article “FOLLOW sets in Compiler Design” we will see how to compute Follow sets.