Compiler Design-FIRST Rule/ Function

FIRST Rule/ Function

1. If X is a terminal then FIRST (X) = {X}
2. If X is a non-terminal. i,e,  X → α B β 
3. FIRST(X) = FIRST (∝)
4. If X ⟶ Є => FIRST (X) = {Є}
5. If X ⟶ Y1, Y2, Y3, …. Yn              Y1 ⟶ a/Є , Y2 ⟶ b/Є

FIRST(X) = FIRST (Y1)

      = {FIRST(a) , FIRST(Є)}

      = { a, Є }   — Should be replaced by next non terminal

      = { a, FIRST (Y2) }

      = { a, FIRST (b), FIRST (Є) }

      = { a, b, Є }

      = { a, b, FIRST(Y3) }

      = { a,b, FIRST(c) FIRST(Є) }

      = { a, b, c, Є } — Continues until we get a terminal 

If it is 

X ⟶ Y1, Y2, Y3, d

Then,

= { a, b, c, FIRST(d) }

= { a, b, c, d }

Reference Link

FIRST Rule/ Function