1
$\begingroup$

The book I am learning about compilers from states that $M \to \alpha N \beta$ will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable.

This is a bit confusing because there can be other productions such as $M\to \gamma K \theta $. Logically, then, the set of symbols which can follow $M$ can also be the set of set of symbols that can follow $k$ if $\theta$ is nullable and can be different from $\mathrm{FOLLOW}(N)$.

As such both $\mathrm{FOLLOW}(N)$ and $\mathrm{FOLLOW}(K)$ should be included in $\mathrm{FOLLOW}(M)$. Shouldn't it be like this? What might be the reasons behind the statement in the book?

$\endgroup$
1
$\begingroup$

If the grammar includes $M \to \alpha N \beta$ and $\beta$ is nullable then anything which could follow $M$ could also follow $N$. In other words,

$FOLLOW(M) \subset FOLLOW(N)$

So we need to add everything in $FOLLOW(M)$ to $FOLLOW(N)$. It does not oblige us to alter $M$'s follow set.

If there is also $M \to \gamma K \theta$ with $\theta$ nullable, then similarly we have

$FOLLOW(M) \subset FOLLOW(K)$

so we also have to add everything in $FOLLOW(M)$ to $FOLLOW(K)$. That implies that the FOLLOW sets for $N$ and $K$ are not disjoint, but it really says nothing interesting about $M$'s FOLLOW set.

$\endgroup$
  • $\begingroup$ What did you mean by "it does not oblige us to alter M's following set ? what I am question is why is the inclusion not the other way round , i.e, follow(n) is contained in follow(m) ? $\endgroup$ – Eddie Dorphy Dec 9 '17 at 15:10
  • $\begingroup$ Logically , whatever can follow N will be included in whatever can follow M ,isn't it so ? $\endgroup$ – Eddie Dorphy Dec 9 '17 at 15:12
  • $\begingroup$ @eddie: no, it isn't. N may appear elsewhere in the grammar, folowed by other terminals; β may have an expansion which starts with another terminal. None of this says anything at all about what might follow M. $\endgroup$ – rici Dec 9 '17 at 17:49
  • $\begingroup$ :It seems I am getting it now . M can be replaced by a set of symbols ending with N and beta , beta being nullable, but the symbols following M and after substitution N , are there because they are eligible to follow M and are from the follow set of M . Hence it does not mean that , only they will follow N . And as by subsitution and nullable beta , this strings in follow(M) can always be shown to follow N , hence the inclusion is as it is given . $\endgroup$ – Eddie Dorphy Dec 11 '17 at 17:06

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.