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?

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.

• 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) ? – Eddie Dorphy Dec 9 '17 at 15:10
• Logically , whatever can follow N will be included in whatever can follow M ,isn't it so ? – Eddie Dorphy Dec 9 '17 at 15:12
• @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. – rici Dec 9 '17 at 17:49
• :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 . – Eddie Dorphy Dec 11 '17 at 17:06