First Set Algorithm

1
2
3
4
5
6
7
8
9
for each nonterminal X do First(X) :={}
while there are changes to any First(X) do
    for each production rule X ->X1X2...Xn do
        k:=1;
        while k<=n do
            First(X) = First(X) U (First(Xk)-{ε})
            if ε is not in First(Xk) then break;
            k := k+1;
        if (k>n) then First(X) = First(X) U {ε}

follow sets

1
2
3
4
stmt -> if-stmt|other
if-stmt -> if(exp)stmt else-part
else-part -> else stmt | ε
exp -> 0 | 1