Hacker News Reader

Comment by burntsushi | Hacker News Reader

Most popular regex engines use backtracking and support non-regular features. They aren't based on automata, so implementing AND is perhaps not as theoretically straight-forward in that context.

There are some popular finite automata based engines though. RE2 comes to mind. In theory, things like AND and complement could be implemented, but in practice, they blow up the size of the state machine.[1, 2] The current maintainer of RE2 did build a tool that permits intersection and complement though.[3]

[1] - https://dl.acm.org/doi/10.1145/2071368.2071372

[2] - https://github.com/google/re2/issues/156#issuecomment-354068...

[3] - https://github.com/google/redgrep

View on HN

Regarding state space blow-up, the only thing I'd add is that after DFA/NFA minimization you always get a canonical state machine (up to state relabeling) so the size will be the same regardless of how it was constructed. This doesn't mean that state space blow-up won't happen but that there isn't any inherent overhead (after minimization) compared to writing an equivalent regular expression by hand without using the product/complement constructions. But minimization interacts poorly with some practical features like capture groups, so you could probably only use the minimized automaton for matching and you'd have to compute the captures after a match some other way.

DFAs can't do capturing anyway. They aren't expressive enough. You can do it with "tagged" DFAs, which I believe are equivalent to transducers. In that case, I would imagine minimization would work just fine, it would just probably be ineffective. The paper that came out of the re2c project is good here.[1]

But sure, I think it's just a matter of adding features where most uses of them will result in pretty poor performance. In RE2's case, state blowup manifests by thrashing its hybrid NFA/DFA cache, which slows it down considerably and eventually will push RE2 to fall back to the NFA simulation.

And I'm actually not sure off the top of my head how complement/intersection impact the Thompson NFA construction. That has to be reasonably fast and space efficient on its own.

[1] - https://re2c.org/2017_trofimovich_tagged_deterministic_finit...

This is interesting, thank you!

Reply on news.ycombinator.com