(flex.info)How does flex compile the DFA so quickly?

---

Next: How can I use more than 8192 rules? Prev: Does there exist a "faster" NDFA->DFA algorithm? Up: FAQ

---

Enter node , (file) or (file)node

How does flex compile the DFA so quickly?
=========================================

There are two big speed wins that 'flex' uses:

  1. 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 the tables.
  2. 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.