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?


  • $\begingroup$ 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. $\endgroup$
    – rici
    Dec 6 '18 at 21:36
  • $\begingroup$ (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.) $\endgroup$
    – rici
    Dec 6 '18 at 21:37

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.