Three Dollar Quill

All right, it's late because I watched a movie that was strange, but probably should have been stranger somehow?

Anyway, let's take a look at the nullability code. Here is the premise: some nonterminal symbols are known to be nullable, and the rest are not known to be nullable. I have a set representing the symbols known to be nullable, and for the symbols not known to be nullable: a map of maps of sets of sets. It maps from a symbol that is on the right-hand-side of rules, to the symbol that is on the left-hand-side of such rules, and the set that it maps to is of sets of right-hand-side symbols not known to be nullable.

Working from the outside of the update_nullable code path...

It starts by converting the list of the right-hand-side to a NSet.t option containing all of the nonterminal symbols if there were no terminal symbols. If this is None, then there's no work to do and it passes back the set and map unchanged. Otherwise, it takes the set and passes it to the next function in. I think I just noticed a bug. I'm taking a set difference in the wrong place. Just move it sooner, and... Okay, that should work.

Okay, so it filters out all elements of the right-hand-side set that are already known to be nullable. If there's still something in the set, then that needs to be added to the map: Every element in the set needs to be added or updated in the map, by adding or updating the left-hand-side key, to make sure that it points to a set containing the new set. And if there's nothing in the right-hand-side set, then the course of action is to mark the left-hand-side as nullable.

Marking a symbol is nullable is accomplished with a recursive function that pulls and accumulates work from and into a set. If the set is empty, it has no more work to do and passes back the other argument unchanged. Otherwise, it pulls one element from the set, and, hm. It's getting late and I need to be better rested to grasp this code. I think I'm missing a call to NMap.remove, and I think I just put it in the right place. But the quick and basic idea is to remove the newly nullable symbol from the sets in the sets in the maps in the map, as well as from the maps in the map. At that point, if any sets of sets contain the empty set, then the corresponding left-hand-side needs to be added to the work set.

I mean, this all seems to make sense, but I'm really tired, so I don't know that I'm trustworthy about this. I should get to bed.

Good night.