Compute FIRST sets for the following grammar. S -> aAB | CD A -> CD | SE | epsil

Question

Compute FIRST sets for the following grammar.

S -> aAB | CD

A -> CD | SE | epsilon

B -> aSB | AS

C -> cC | epsilon

D -> CDd | epsilon

E -> eFg

F -> Fg | epsilon

This is what I have so far.. stuck on some parts.

First(S) = {a} => First(C) = {a, c} => First(D) = {a, c, epsilon}.

First(A) => First(C) = {c} => First(D) = {c, epsilon} => First(S) = {a} = {c, epsilon, a}. ---- This is the part I'm stuck.

First(B) = {a} => First(A) => First(C) = {a, c, epsilon}.

First(C) = {c, epsilon}.

First(D) => First(C) = {c} => First(D) => First(D) = {c, d, epsilon}.

First(E) = {e}. (e is not epsilon)

First(F) => First(F) = {g, epsilon}.

Explanation / Answer

FIRST of a grammar symbol A is a set of terminal symbols such that the string derived from A is starts with these terminal symbols.

FIRST can be calculated using the following rules:

If B1 is e(epsilon), then add FIRST(B2) to FIRST(A)… so on.

The given grammar is :

S -> aAB | CD                       

A -> CD | SE | epsilon

B -> aSB | AS            

C -> cC | epsilon        

D -> CDd | epsilon     

E -> eFg                     

F -> Fg | epsilon

           

Consider the grammar rule, S -> aAB | CD   

Consider the grammar rule , C -> cC | epsilon

Consider the grammar rule , D -> CDd | epsilon

Consider the grammar rule , A -> CD | SE | epsilon

Consider the grammar rule, E -> eFg

Consider the grammar rule , B -> aSB | AS   

Consider the grammar rule, F -> Fg | epsilon

FIRST(S)

{a,c,d,e,epsilon}

FIRST(A)

{a,c,d,e,epsilon}

FIRST(B)

{a,c,d,e,epsilon}

FIRST(C)

{c, epsilon}

FIRST(D)

{c,d,epsilon}

FIRST(E)

{e}

FIRST(F)

{g,epsilon}

FIRST(S)

{a,c,d,e,epsilon}

FIRST(A)

{a,c,d,e,epsilon}

FIRST(B)

{a,c,d,e,epsilon}

FIRST(C)

{c, epsilon}

FIRST(D)

{c,d,epsilon}

FIRST(E)

{e}

FIRST(F)

{g,epsilon}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.