Working through this for fun: http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/
Example calculation of nullable and first uses a fixed-point calculation. (see section 3.8)
I'm doing things in Scheme and relying a lot on recursion.
If you try to implement nullable or first via recursion, it should be clear you'll recur infinitely on a production like
N -> N a b
where N is a non-terminal and a,b are terminals.
Could this be solved, recursively, by maintaining a set of non-terminals seen on the left hand side of production rules, and ignoring them after we have accounted for them once?
This seems to work for nullable. What about for first?
EDIT: This is what I have learned from playing around. Source code link at bottom.
Non terminals cannot be ignored in the calculation of first unless they are nullable.
Consider:
N -> N a
N -> X
N ->
Here we can ignore N in N a because N is nullable. We can replace N -> N a with N -> a and deduce that a is a member of first(N).
Here we cannot ignore N:
N -> N a
N -> M
M -> b
If we ignored the N in N -> N a we would deduce that a is in first(N) which is false. Instead, we see that N is not nullable, and hence when calculating first, we can omit any production where N is found as the first symbol in the RHS.
This yields:
N -> M
M -> b
which tells us b is in first(N).
Source Code: http://gist.github.com/287069
So ... does this sound OK?