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
- If X1 is a terminal a, First(alpha) = {a}
- 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:
- If A is the start symbol then $ is in Follow(A).
- If there is a production B->alpha A beta, then everything in First(beta)
(except empty) is in Follow(A).
- 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).