# First Sets: If $A \to Ad\ |\ c$, what is $First(A)$?

Suppose that we have a grammar with the following rules:

$$S \to Aa\ |\ b\ |\ \varepsilon\\ A \to Ad\ |\ c$$

From looking at it I already know that $$First(S) = \{b, \varepsilon, c\}$$. My question is:

• How to determine $$First(A)$$?

For instance, by looking at the rule $$S \to Aa$$ we know that $$First(S)$$ must include $$First(A)$$. $$First(A)$$ already includes $$c$$ (that's why $$c \in First(S)$$). but how to handle the rule $$A \to Ad$$.

Just by applying the algorithm for finding the $$First$$ set blindly, I will have that $$First(A)$$ "includes" $$First(A)$$, which confuses me.

As far as I understand in $$A \to Ad\ |\ c$$ there is a left recursion. By eliminating it we get the following rules

$$A \to cA'\\ A' \to dA'$$

Does this mean that $$First(A)$$ only contains $$c$$?

Does this mean that I can ignore a rule with left recursion and just look at the other (non-recursive) rules under that variable?

Thanks!

• Why do you find it confusing that $First(A)$ includes $First(A)$? :-) It seems tautological. However, it doesn't add any information. Since you (presumably) know that $A$ is not nullable, just accept the tautology and move on. – rici Dec 6 '18 at 21:36
• (And to be clear, you can only ignore this left-recursive rule because $A$ is not nullable. If it were nullable, you would need to proceed with the rest of the RHS, as with any other nullable non-terminal.) – rici Dec 6 '18 at 21:37

## 1 Answer

The grammar you have presented is left linear grammar. The production $$A \rightarrow Ad$$ in when transformed into $$FM$$, $$A$$ becomes state & an edge with $$c$$ terminal from $$A$$ to $$A$$ (self loop). So its clear for this particular grammar $$First(A)$$ is $$c$$.

Moreover, your approach is also correct or primarily correct.