## Computing Predict Sets

Let
• a,b,c=terminal
• A,B,C=nonterminal
• X,Y,Z=terminal or nonterminal
• alpha,beta,gamma=mixed string of terminals and nonterminals
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
• First(alpha) includes First(beta) for all productions of form A->beta.
• If X1...Xj are nonterminals and each of X1...Xj can derive empty, then First(alpha) includes First(Xj+1).
• If X1...Xk are nonterminals and each of X1...Xk can derive empty, then First(alpha) includes empty.

### 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).