2 ms·
The complement operation doesn't provide a way of deciding whether two regexes are equivalent, nor is any such thing required to implement it. Using derivatives
by kazinator 5y ago
The complement operation doesn't provide a way of deciding whether two regexes are equivalent, nor is any such thing required to implement it. Using derivatives to interpret a regular expression that contains a complement operator does not require a function for calculating equivalence of two regular expressions.
Equivalence is required for compiling. The reason is that regular expressions have features like the Kleene closure which express iteration, and these give rise to endless derivatives: regular expressions whose derivative you can keep taking ad nauseum. This is fine for interpreting, because the algorithm terminates when you have consumed the input or hit an impasse. The compiler, however, has to close the loops and turn them into cycles in the state machine graph. To do that it has to check each derivative: "have I derived an expression which has occurred before?" If so, then just hook to the previous state.
If you make the check literal, just comparing the regex syntax for identical structure, the graph will sometimes be larger than necessary, because it will contain redundant nodes that should be equivalent states. The smarter you make the equivalence function, the more compact the graphs will be.