3 ms·

What about derivative-based regex? I got worried at some point that some of the purported advantages of derivative-based regexes might be drawbacks. One such a

What about derivative-based regex? I got worried at some point that some of the purported advantages of derivative-based regexes might be drawbacks. One such advantage/drawback is that it adds the complement operation into the language of Regex. But that gives you a way of deciding whether two regexes are equivalent, which is supposed to be PSPACE-COMPLETE, which ought to severely hamper finding an efficient implementation.

hayley-patton 5y ago
Author here - I don't think this is an issue. If you don't use submatching, you can just compute the minimal DFAs and compare them to test for equivalence, and you don't even need negation. Thus, introducing negation can't do any harm there. But as I generate Mealy machines for submatching, which can't be minimised, we need another approach. Knowing that A - B = A ∧ ¬B, one can produce a DFA for (A - B) ∨ (B - A), and if it has no accepting states, then A and B must be equivalent, as nothing can match one but not both. But DFA construction is O(2ⁿ), even if one takes the RE → NFA → DFA route, so this is nothing new complexity-wise. Such a decision procedure is never used in a derivative-based regex implementation, anyway. The equivalence of regular expressions only needs to be approximated, and the approximation consists of some structural rules (see Definition 4.1 of [1]). Relatively few rules are needed to guarantee that a _finite_ machine can be generated, and only a dozen rules are required to get very close to a minimal DFA (table 1, page 14 of [1]). So having the possibility of writing a precise regex equivalence function is completely irrelevant to producing an efficient regex engine. A decision procedure is handy, but you can write one for submatch-less regexes without negation, the complexity of such a procedure is typical for DFA construction, and the problem of deciding if two regular expressions are equivalent is irrelevant. [1] Regular-expression derivatives reexamined https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf
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.

hayley-patton 5y ago

Author here - I don't think this is an issue. If you don't use submatching, you can just compute the minimal DFAs and compare them to test for equivalence, and you don't even need negation. Thus, introducing negation can't do any harm there. But as I generate Mealy machines for submatching, which can't be minimised, we need another approach. Knowing that A - B = A ∧ ¬B, one can produce a DFA for (A - B) ∨ (B - A), and if it has no accepting states, then A and B must be equivalent, as nothing can match one but not both. But DFA construction is O(2ⁿ), even if one takes the RE → NFA → DFA route, so this is nothing new complexity-wise. Such a decision procedure is never used in a derivative-based regex implementation, anyway. The equivalence of regular expressions only needs to be approximated, and the approximation consists of some structural rules (see Definition 4.1 of [1]). Relatively few rules are needed to guarantee that a _finite_ machine can be generated, and only a dozen rules are required to get very close to a minimal DFA (table 1, page 14 of [1]). So having the possibility of writing a precise regex equivalence function is completely irrelevant to producing an efficient regex engine. A decision procedure is handy, but you can write one for submatch-less regexes without negation, the complexity of such a procedure is typical for DFA construction, and the problem of deciding if two regular expressions are equivalent is irrelevant. [1] Regular-expression derivatives reexamined https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf

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.