I'm trying to build a grammar that violate only the 3rd rule. I'm trying to figure out what kind of grammar would not respect that.

I think the grammar has to be left-recursive to not respect it.

if $\beta \Rightarrow^* \epsilon$ then $\alpha$ does not derive any string beginning with a terminal in $\mathop {FOLLOW}(A)$. Where $A \to \alpha \mid \beta$

Am I right to think that?

  • 2
    $\begingroup$ What "rules" are you talking about? Presumably it is enough to just add a production (or two) that violate the rule. $\endgroup$ – vonbrand Feb 18 '16 at 23:34
  • $\begingroup$ Added the rule. $\endgroup$ – Laura Feb 18 '16 at 23:47

Something like the following:

$\begin{align} S &\to A a \\ A &\to a \mid \epsilon \end{align}$

| cite | improve this answer | |
  • $\begingroup$ So it has to be left recursive? $\endgroup$ – Laura Feb 19 '16 at 0:09
  • $\begingroup$ @Laura this isn't recursive (no right hand side contains the non-terminal at the left), even less left-recursive $\endgroup$ – vonbrand Feb 19 '16 at 0:30
  • $\begingroup$ ok so FOLLOW(A) = {a,$} in this case. And FIRST(S) = {a} $\endgroup$ – Laura Feb 19 '16 at 0:48
  • $\begingroup$ @Laura, what is important is that $A \Rightarrow^* \epsilon$, $\mathop{FIRST}(A) = \{a\}$ and $\mathop{FOLLOW}(A) = \{a\}$, so $\mathop{FIRST}(A) \cap \mathop{FOLLOW}(A) \ne \varnothing$ $\endgroup$ – vonbrand Feb 19 '16 at 1:21

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.