LARA

Algorithm for Computing First and Follow Sets

Building on Recursive Descent Parsing

nullable = {}
foreach nonterminal X:
  first(X)={}
  follow(X)={}
for each terminal Y:
  first(Y)={Y}

repeat
  foreach grammar rule X ::= Y(1) ... Y(k)
  if k=0 or {Y(1),...,Y(k)} subset of nullable then
    nullable = nullable union {X}
  for i = 1 to k
    for j = i+1 to k
      if i=1 or {Y(1),...,Y(i-1)} subset of nullable then
        first(X) = first(X) union first(Y(i))
      if i=k or {Y(i+1),...Y(k)} subset of nullable then
        follow(Y(i)) = follow(Y(i)) union follow(X)
      if i+1=j or {Y(i+1),...,Y(j-1)} subset of nullable then
        follow(Y(i)) = follow(Y(i)) union first(Y(j))
until none of nullable,first,follow changed in last iteration