4 ms·
As a side note, when converting the NFA to a DFA, you get an exponential number of states, since each DFA state corresponds to a set of NFA states.
by klodolph 4y ago
As a side note, when converting the NFA to a DFA, you get an exponential number of states, since each DFA state corresponds to a set of NFA states.
- burntsushi 4y agoTrue, and that's why libraries like RE2 don't build full DFAs. They use lazy DFAs. DFA states are compiled as needed. At most one state is built per byte of input, so this sidesteps the exponential time bound. In all implementations I know of, memory use is bounded. When memory fills up, the cache of DFA states is cleared. If this happens too many times, RE2 quits the lazy DFA and falls back to a Pike VM. (Effectively the Thompson NFA matcher, but with capture group support.)