5 ms·

Wait, if one wants to match a complement of a regex, surely it is equivalent to seeing if matching the original regex would fail? Or do I miss something obvious

Wait, if one wants to match a complement of a regex, surely it is equivalent to seeing if matching the original regex would fail? Or do I miss something obvious?

burntsushi 4y ago
I mean, yes? But it's kind of missing the forest for the trees. Regex searching isn't limited to "did it match or not," but also to finding where the regex matched in the first place. For example, let's say you want to match all words except for 'foo'. You might write, '\b(!foo)\b', where the '(!re)' syntax means "complement of 're'." That would then match 'bar', 'baz' but not 'foo' in 'bar foo baz'. It's like how character class set notation has a 'negation' feature. e.g., '[a-z]' matches a-z, but '[^a-z]' matches anything except for 'a-z'. So you might say, "why bother with adding negation when you can just check if the original char class would fail?" The answer is that without negation embedded in the regex itself, you miss out on composition. This is another reason why features like complement and intersection aren't particularly popular. They are weird to reason about. Another reason is that many of their use cases can be achieved through other means. For example, my example above could conceivably be done by iterating over all words (using word segmentation, for example) and just checking whether each matches 'foo' or not. It could also likely be accomplished through the use of negative look-around, commonly found in backtracking regex engines and not finite automata based regex engines.
nsajko 4y ago
Your proposed implementation makes sense for the case of merely taking the complement of a simple regular expression. But the point of having the complement operator available is to be able to take complements of arbitrary sub-expressions within the RE, and even having nested complements in the RE. In that case your proposed implementation would be relatively inefficient.

Wait, if one wants to match a complement of a regex, surely it is equivalent to seeing if matching the original regex would fail? Or do I miss something obvious?

burntsushi 4y ago

I mean, yes? But it's kind of missing the forest for the trees. Regex searching isn't limited to "did it match or not," but also to finding where the regex matched in the first place. For example, let's say you want to match all words except for 'foo'. You might write, '\b(!foo)\b', where the '(!re)' syntax means "complement of 're'." That would then match 'bar', 'baz' but not 'foo' in 'bar foo baz'. It's like how character class set notation has a 'negation' feature. e.g., '[a-z]' matches a-z, but '[^a-z]' matches anything except for 'a-z'. So you might say, "why bother with adding negation when you can just check if the original char class would fail?" The answer is that without negation embedded in the regex itself, you miss out on composition. This is another reason why features like complement and intersection aren't particularly popular. They are weird to reason about. Another reason is that many of their use cases can be achieved through other means. For example, my example above could conceivably be done by iterating over all words (using word segmentation, for example) and just checking whether each matches 'foo' or not. It could also likely be accomplished through the use of negative look-around, commonly found in backtracking regex engines and not finite automata based regex engines.

nsajko 4y ago

Your proposed implementation makes sense for the case of merely taking the complement of a simple regular expression. But the point of having the complement operator available is to be able to take complements of arbitrary sub-expressions within the RE, and even having nested complements in the RE. In that case your proposed implementation would be relatively inefficient.