Parsing - Introduction to Compiler Construction in a Java World - page 82

First and Follow
We dene, rst(X 1 X 2 :::X n ) = fajX 1 X 2 :::X n ) a;a 2 Tg, that is, the set of all termi-
nals that can start strings derivable from X 1 X 2 :::X n . Also, if X 1 X 2 :::X n ) , then we
say that rst(X 1 X 2 :::X n ) includes .
We define two algorithms for computing first: one for a single symbol and the other for
a sequence of symbols. The two algorithms are both mutually recursive and make use of
memoization, that is, what was previously computed for each set is remembered upon each
iteration.
Algorithm 3.2 Compute first(X) for all symbols X in a Grammar G
Input: a context-free grammar G = (N;T;S;P)
Output: first(X) for all symbols X in G
for each terminal x do
rst(x) fxg
end for
for each non-terminal X do
rst(X) fg
end for
if X ::= 2 P then
add to rst(X)
end if
repeat
for each Y ::= X 1 X 2 :::X n 2 P do
add all symbols from rst(X 1 X 2 :::X n ) to rst(Y )
end for
until no new symbols are added to any set
Notice that the computation of first in Algorithm 3.2 might take account of the entirety
of every right-hand side of each rule defining the symbol we are interested in.
Algorithm 3.3 Compute rst(X 1 X 2 :::X n ) for a Grammar G
Input: a context-free grammar G = (N;T;S;P) and a sequence X 1 X 2 :::X n
Output: rst(X 1 X 2 :::X n )
Set S rst(X 1 )
i 2
while 2 S and i n do
S S
Add rst(X i ) to S
i i + 1
end while
return S
Algorithm 3.3 says that to compute first for a sequence of symbols X 1 X 2 :::X n , we start
with first(X1). 1 ). If X 1 ) , then we must also include rst(X 2 ). If X 2 ) , then we must
also include first(X3). 3 ). And so on.
Example. Consider our example grammar in (3.21). The computation of first for the
terminals, by step 1 of Algorithm 3.2 is trivial: