Computing Predict Sets

Let The Predict set for a production is the set of terminals that indicate that this production should be chosen:
Predict: Production -> set of terminals
Predict(A->alpha) = First(alpha) (+ Follow(A)-empty if empty is in First(alpha))

Computing First(alpha)

First(alpha) is the set of terminals that could begin a string derived from alpha, or empty if alpha could vanish entirely. Suppose alpha=X1 X2 ... Xk. Then
  1. If X1 is a terminal a, First(alpha) = {a}
  2. If X1 is a nonterminal A, then

Computing Follow(A)

Follow(A) is the set of tokens that can follow A in some legal derivation:
  1. If A is the start symbol then $ is in Follow(A).
  2. If there is a production B->alpha A beta, then everything in First(beta) (except empty) is in Follow(A).
  3. If there is a production B->alpha A, or B->alpha A beta where First(beta) contains empty, then everything in Follow(B) is in Follow(A).