Question

Compute FIRST sets for the following grammar.

a) S -> aAB | CD
b) A -> CD | SE | epsilon​
c) B -> aSB | AS
d) C -> cC | epsilon
e) D -> CDd | epsilon
f) E -> eFg
g) F -> Fg | epsilon

Answer 1

To compute the FIRST sets for a grammar, initialize the FIRST sets, apply rules to determine the FIRST sets of non-terminal symbols, and repeat until no more changes occur. The computed FIRST sets for the given grammar are: FIRST(S) = {a, c}, FIRST(A) = {c, e, epsilon}, FIRST(B) = {a, c}, FIRST(C) = {c, epsilon}, FIRST(D) = {c, d, epsilon}, FIRST(E) = {e, epsilon}, and FIRST(F) = {epsilon, g}.

Step-by-step explanation:

When computing FIRST sets for a grammar, we need to determine the set of terminals that can appear as the first symbol of a string derived from a non-terminal symbol. Here are the steps to compute the FIRST sets for the given grammar:

1. Initialize the FIRST sets for all non-terminal symbols to empty sets.
2. For each non-terminal symbol, follow these rules:
3. Return the computed FIRST sets for each non-terminal symbol.

Using these steps, you can compute the FIRST sets for the given grammar:

FIRST(S) = {a, c}

FIRST(A) = {c, e, epsilon}

FIRST(B) = {a, c}

FIRST(C) = {c, epsilon}

FIRST(D) = {c, d, epsilon}

FIRST(E) = {e, epsilon}

FIRST(F) = {epsilon, g}