Computing the Follow Set

Question

Ok, I've understood how to compute the Follow_k(N) set (N is a nonterminal): for every production rule of the form A -> aBc you add First_k(First_k(c)Follow_k(A)) to Follow_k(B) (a, c are any group of terminals and nonterminals, or even lambda). ...and you repeat this until there's nothing left to add.

But what happends for production rules like: S -> ABCD (A, B, C, D are all nonterminals)?

Should I
add First_k(First_k(BCD)Follow_k(S)) to Follow_k(A) or
add First_k(First_k(CD)Follow_k(S)) to Follow_k(B) or
add First_k(First_k(D)Follow_k(S)) to Follow_k(C) or
add First_k(First_k(lambda)Follow_k(S)) to Follow_k(D) or
do all of the above?

UPDATE:
Let's take the following grammar for example:

S -> ABC
A -> a
B -> b
C -> c

Intuitively, Follow_1(S) = {} because nothing follows after S
Follow_1(A) = {b} because b follows after A,
Follow_1(B) = {c} because c follows after B,
Follow_1(C) = {} because nothing follows after C.
In order to get this result using the algorithm you must consider all cases for S -> ABC.

But my judgement or example may not be right so the question still remains open...

Answer 1

If you run into trouble on other grammar problems like this, give this online first, follow, & predict set finder a shot. It's automatic and you can compare answers to its output to get a feel for how to work through these.

But what happens for production rules like: S -> ABCD (A, B, C, D are all nonterminals)?

Here are the rules for finding follow sets.

1. First put $ (the end of input marker) in Follow(S) (S is the start symbol)
2. If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).
3. If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
4. If there is production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)

Let's use your example grammar:

• S -> ABC
• A -> a
• B -> b

• C -> c

  1. Rule 1 says that follow(S) contains $.
  2. Rule 2 gives us: follow(A) contains first(B); also, follow(B) contains first(C).
  3. Rule 3 says that follow(C) contains follow (S).
  4. None of your productions are nullable, so we don't care about rule #4. A symbol is nullable if it derives ε or if it derives a nullable non-terminal symbol.

Nullability's transitivity can trip people up. Consider this grammar:

• S -> A
• A -> B
• B -> ε

Since B derives ε, B's nullable. Since A derives B, which derives ε, A's nullable too. S derives A, which derives B, which derives ε, so S is nullable as well.

Granted, you didn't bring that up, but it's a common source of confusion in compiler courses, so I figured I'd lay it out.

Also, if you need some sample grammars to work through, http://faculty.stedwards.edu/laurab/cosc4342/g1answers.txt might be handy.