Hacker News Reader

Comment by feanaro | Hacker News Reader

Thinking about point 1 makes me wonder why no popular regex engines have an intersection (logical AND) operator. It seems like it could allow writing complex regexes in a much clearer way.

View on HN

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

This is interesting, thank you!

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...

Could 2 lookaheads starting at the same position not be used for this purpose?

Lookahead is what causes a language not to be regular. In fact, common regex libraries support broader classes of languages than the regular ones. Perhaps that's why there's no `and` operator.

Reply on news.ycombinator.com