How does flex compile the DFA so quickly?
There are two big speed wins that
- It analyzes the input rules to construct equivalence classes for those
characters that always make the same transitions. It then rewrites the NFA
using equivalence classes for transitions instead of characters. This cuts
down the NFA->DFA computation time dramatically, to the point where, for
uncompressed DFA tables, the DFA generation is often I/O bound in writing out
- It maintains hash values for previously computed DFA states, so testing
whether a newly constructed DFA state is equivalent to a previously constructed
state can be done very quickly, by first comparing hash values.