The nullable list

Bison also creates a list of non-terminals that can expand into the empty string. A vector Nullable is created in nullable.c

Nullable[i] != 0 (zero) if i th non-terminal can expand into the empty string.

The algorithm itself is very simple. If X-> /* empty */ then clearly X is added to Nullable set

if X-> beta where beta contains only non-terminal symbols, X is also added to nullable set if all of the nonterminals can expand to the null string; if beta contains atleast one terminal symbol, then X cannot be included in the nullable set.

The implementation of the above algorithm is not as simple. It takes a good amount of linked list tweaking before we arrive at the final array. Look at nullable_compute () in nullable.c