5 ms·

Show HN: Regex Derivatives (Brzozowski Derivatives)

103 points by c0nstantine 4y ago

A Python sketch of a regex engine in less than 150 lines of code

enricozb 4y ago
I think there is a typo when defining v(e), it says both v(e) = e and v(e) = empty set.
- c0nstantine 4y ago
  Yes there's a typo. Thank you for following the README.md and your attention. It's fixed now.
mananaysiempre 4y ago
From my own experiments[1], I suspect your engine might still be prone to exponential blowup: you only get proper linear matching if you reassociate and sort the choice expressions and merge identical terms (and Brzozowski’s original paper[2] does point this out). This makes the implementation quite a bit more annoying. ETA: Yup. Try (successfully) matching a long string of As against (A*)* and watch it die. [1] http://ix.io/4qan/ http://ix.io/4qan/ (matching only), http://ix.io/4qap/ http://ix.io/4qap/ (adds parsing and printing). [2] https://doi.org/10.1145/321239.321249 https://doi.org/10.1145/321239.321249
- c0nstantine 4y ago
  I agree. There is no magic. DFA construction has a risk of exponential growth in the number of states. My point was to illustrate the technique. I found no minimalistic python implementations and decided to write one with a short and gentle intro. I wanted to add the test for 'syntactic' equivalence to reduce the number of terms. But the code became less readable and I rolled it back.
  - mananaysiempre 4y ago
    >> I suspect your engine might still be prone to exponential blowup > DFA construction has a risk of exponential growth in the number of states. Right, I may have phrased that badly. I meant that the length of the derivative can grow multiplicatively for each consumed character, without bound, so even with memoization you won’t end up with a DFA. For example, in your simple implementation each A fed into (A*)* gives you a new (longer) RE, forever, even though a DFA for it only has to have a starting state and a failure one (actual implementations may end up with more). Brzozowski proves that a RE has only a finite number of derivatives, thus making memoized differentiation equivalent to lazy DFA construction, but only if you respect associativity, commutativity and idempotence of choice ( | in modern syntax, + in his). I’m not actually sure you need all of those, in all circumstances, or if it’s enough to restrict the equivalences to e.g. the vicinity of a repetition operator, and he doesn’t discuss this, but I’ve made a couple of simpler attempts and could still make them blow up after some tinkering.
    - c0nstantine 4y ago
      I think I got your point. It is valid. To construct the DFA and have a finite number of derivatives we have to keep track of the following equivalences: r + r ~ r r + s ~ s + r (r + s) + t ~ r + (s + t) In [1] authors state this and refer to the proof in the original paper. They even extend it to a set of extended rules to reduce the number of terms (states) even more. Actually, the code for (lazy) DFA construction code is not even committed yet. The repo contains just sequential per-character application of the derivative to a regex. Which is obviously finite (though not efficient). Again, just to demonstrate the concept. [1] https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf
      - mananaysiempre 4y ago
        Yes, and even if you aren’t constructing a DFA, only being able to produce a finite number of derivatives from a given RE is still useful: As there’s only a finite number of derivatives, their length is obviously bounded by a constant for a fixed starting RE (though that constant is still exponential in the length of that RE). This implies your non-DFA-based matcher can only take a bounded time computing the next derivative, so takes a time proportional to the length of a string to process that string (even if the constant of proportionality is exponential in the RE length). (I’m not good at fitting all of my reasoning into a single comment today, am I?)
- H8crilA 4y ago
  This comment is not following HN guidelines, but: I saw this and I was immediately sure that I could make this blow up exponentially. But then I got too lazy to think about exactly how, and instead waited for kind strangers on the Internet to provide a ready solution. Thank you :) BTW, the concept is still cool.
- djoldman 4y ago
  try against this: https://gist.github.com/pervognsen/815b208b86066f6d7a00 https://gist.github.com/pervognsen/815b208b86066f6d7a00
SomeoneOnTheWeb 4y ago
IIRC, that's what the Rust regex engine[1] currently uses [1] https://github.com/rust-lang/regex https://github.com/rust-lang/regex
- mananaysiempre 4y ago
  Nope, and its author (burntsushi) doesn’t think[1,2] you can do a practical regex matcher on top of the techinque. I’m not sure I agree with him, but, well, he’s built a production engine and I haven’t. (There’s a thing called “partial derivatives”, which is to Brzozowski derivatives as NFAs are to DFAs, but it doesn’t interact well with intersection and negation if you want to support those.) [1] https://news.ycombinator.com/item?id=31693927 https://news.ycombinator.com/item?id=31693927 [2] https://news.ycombinator.com/item?id=31693559 https://news.ycombinator.com/item?id=31693559
- burntsushi 4y ago
  As the sibling commenter said, indeed, the regex crate does not use derivatives. If you wouldn't mind, could you share what led you to that conclusion? I'd love to fix it! I am at least currently not aware of any "production" and "general purpose" regex engine that is built on derivatives. And I'm not really sure how you'd build one. The biggest hurdle you'd have to over come as far as I can tell is that derivatives are usually used to build a DFA. In this case, the OP does matching while taking the derivative simultaneously. My guess is that you'll run into problems doing that which huge character classes, which are easy to get when Unicode is enabled. Whether "production" and "general purpose" are the same as "practical" is unclear. To put away the vague words, my understanding is that with derivatives, you'll either get slow match times or slow compilation times. (To the point where "slow" becomes enough to notice and be a problem.) With that said, the world is full of experts saying you can't do something. What I'm trying to say here is that there are some challenges I've faced in the course of building a regex engine that I simply don't know how I'd address with derivatives. Another thing worth considering here is the match semantics of the regex. I haven't had time yet to try this particular matcher, but when I do, I'd check for how alternations are matched. For example, what does 'samwise|sam' match in the haystack 'samwise'? Either answer is correct, but one is typically found in POSIX engines and the other found in Perl-like engines. Can derivatives implement either? It's also worth noting that I am not an expert on regex derivatives. I've never actually build a derivative oriented matcher. If I had, I'm sure I could be a lot more specific with my criticisms. :-)
evolveyourmind 4y ago
And here the formalized proof in less than 150 lines of code (in Agda) for Brzozowski Derivatives for regex matching (and additional regular languages theorems): https://github.com/desi-ivanov/agda-regexp-automata https://github.com/desi-ivanov/agda-regexp-automata
- c0nstantine 4y ago
  Thanks for sharing. I am not familiar with Agda. Will take a look. There is somewhat similar code in COQ: https://github.com/coq-community/regexp-Brzozowski https://github.com/coq-community/regexp-Brzozowski
  - DonaldPShimoda 4y ago
    Just a small FYI, but the language's name (for now) is Coq, not COQ.
noelwelsh 4y ago
The next logical step is parsing with derivatives: https://matt.might.net/papers/might2011derivatives.pdf https://matt.might.net/papers/might2011derivatives.pdf I found the paper was fairly readable. YMMV.
aarchi 4y ago
I'm currently building a couple of regexp engines: One, that's a formalization[0] in Coq with big-step semantics, which uncommonly has the intersection operator, and includes several equivalence relations and a proof of the pumping lemma, excepting one case (more on that below). As a learning exercise and for historical reasons, I've also mostly ported Rust Cox's re1 engine to Rust[1], which includes VM matchers in the style of Henry Spencer, Ken Thompson, and Rob Pike. I also plan to port Doug McIlroy's engine[2], which is interesting for having intersection and complement and special handling for sublanguages, all the way down to just concatenation matched with Knuth-Morris-Pratt. I also want to examine the Rust (thanks burntsushi!), RE2, and Plan 9 engines in more depth. Once I have time to get back to the project, I want to get back to my regular expression crossword puzzle solver. For that, I'm converting the hint regexps to DFAs, that match strings of some fixed length, and concatenating and intersecting them, until a single regexp is yielded, which should be a string literal, if the puzzle has a single solution. For backreferences, it's more tricky, but I plan on rewriting backreferences to the captured expression, where the lengths of both match, then either executing it with a stack like a pushdown automata or constructing a set of constraints on the characters by index. As an aside: In my proof of the pumping lemma[3], I got stuck on the case for intersection and I'd love insight. Regular languages are closed under intersection, so the pumping lemma should hold for my implementation. I need to prove that if s =~ re1 and s =~ re2 can be pumped, then so can s =~ And re1 re2. s is is split into different substrings for re1 and re2, s = s11 ++ s12 ++ s13 = s21 ++ s22 ++ s23, then repeated an arbitrary number of times, (forall n, s11 ++ repeat s12 n ++ s13 =~ re1) and (forall n, s21 ++ repeat s22 n ++ s23 =~ re2). My intuition is that s11 = s21, s12 = s22, and s13 = s23, because they both match for the intersection, but I'm not convinced of that and haven't been able to formulate a proof for that. 0: https://github.com/thaliaarchi/recross-coq https://github.com/thaliaarchi/recross-coq 1: https://github.com/thaliaarchi/re1-rust https://github.com/thaliaarchi/re1-rust 2: https://github.com/arnoldrobbins/mcilroy-regex https://github.com/arnoldrobbins/mcilroy-regex 3: https://github.com/thaliaarchi/recross-coq/blob/main/theories/regexp_pumping.v#L117-L124 https://github.com/thaliaarchi/recross-coq/blob/main/theorie...
DonHopkins 4y ago
This "derivatives of regular expressions" technique is what James Clark used in the design of the efficient implementation of the Relax/NG tree regular expression based XML validator, based on Janusz A. Brzozowski, "Derivatives of Regular Expressions", Journal of the ACM, Volume 11, Issue 4, 1964. https://relaxng.org/jclark/design.html https://relaxng.org/jclark/design.html >Unordered content >SGML provides an & operator: A & B matches A followed by B or B followed by A. XML removed the & operator. RELAX NG reintroduces it with a twist. In SGML, a content model of A & B* requires all the B elements to be consecutive: the required A element cannot occur in between two B elements. Usually, users use the & operator because they want to allow child elements to occur in any order, so this restriction is undesirable. In RELAX NG, the corresponding operator has interleaving semantics. It matches any interleaving of a sequence containing a single A element and a sequence containing zero or more B elements; it thus allows the A element to occur anywhere, including between two B elements. >XML removed the & operator mainly because of the & operator's reputation for implementation complexity. The most difficult part of implementing the & operator in SGML is detecting whether a content model including & is 1-unambiguous. Unlike SGML, XML and W3C XML Schema, RELAX NG does not restrict content models to be 1-unambiguous, so this implementation difficulty is removed. The classic implementation technique for SGML and XML content models is to construct a Glushkov automaton. The 1-unambiguity restriction is helpful for this technique because it ensures that the Glushkov automaton is deterministic. An interleaving operator causes difficulty with this technique. However, there is an alternative implementation technique available [17] based on derivatives of regular expressions [4]. This handles content models that are not 1-unambiguous without any additional effort and can deal with interleaving without difficulty. RELAX NG imposes restrictions on the use of interleave which are sufficient to ensure that a derivative-based implementation will not exhibit exponential behavior. [4] Janusz A. Brzozowski. Derivatives of Regular Expressions. Journal of the ACM, Volume 11, Issue 4, 1964. https://dl.acm.org/doi/10.1145/321239.321249 https://dl.acm.org/doi/10.1145/321239.321249 https://dl.acm.org/doi/pdf/10.1145/321239.321249 https://dl.acm.org/doi/pdf/10.1145/321239.321249 [17] Joe English. How to validate XML. 1999. See http://www.flightlab.com/~joe/sgml/validate.html http://www.flightlab.com/~joe/sgml/validate.html
deleted 4y ago
[deleted]
djoldman 4y ago
See also: https://matt.might.net/articles/parsing-with-derivatives/ https://matt.might.net/articles/parsing-with-derivatives/ https://gist.github.com/pervognsen/815b208b86066f6d7a00 https://gist.github.com/pervognsen/815b208b86066f6d7a00

103 points by c0nstantine 4y ago

A Python sketch of a regex engine in less than 150 lines of code

enricozb 4y ago

I think there is a typo when defining v(e), it says both v(e) = e and v(e) = empty set.

c0nstantine 4y ago
Yes there's a typo. Thank you for following the README.md and your attention. It's fixed now.

mananaysiempre 4y ago

From my own experiments[1], I suspect your engine might still be prone to exponential blowup: you only get proper linear matching if you reassociate and sort the choice expressions and merge identical terms (and Brzozowski’s original paper[2] does point this out). This makes the implementation quite a bit more annoying. ETA: Yup. Try (successfully) matching a long string of As against (A*)* and watch it die. [1] http://ix.io/4qan/ http://ix.io/4qan/ (matching only), http://ix.io/4qap/ http://ix.io/4qap/ (adds parsing and printing). [2] https://doi.org/10.1145/321239.321249 https://doi.org/10.1145/321239.321249

c0nstantine 4y ago
I agree. There is no magic. DFA construction has a risk of exponential growth in the number of states. My point was to illustrate the technique. I found no minimalistic python implementations and decided to write one with a short and gentle intro. I wanted to add the test for 'syntactic' equivalence to reduce the number of terms. But the code became less readable and I rolled it back.
- mananaysiempre 4y ago
  >> I suspect your engine might still be prone to exponential blowup > DFA construction has a risk of exponential growth in the number of states. Right, I may have phrased that badly. I meant that the length of the derivative can grow multiplicatively for each consumed character, without bound, so even with memoization you won’t end up with a DFA. For example, in your simple implementation each A fed into (A*)* gives you a new (longer) RE, forever, even though a DFA for it only has to have a starting state and a failure one (actual implementations may end up with more). Brzozowski proves that a RE has only a finite number of derivatives, thus making memoized differentiation equivalent to lazy DFA construction, but only if you respect associativity, commutativity and idempotence of choice ( | in modern syntax, + in his). I’m not actually sure you need all of those, in all circumstances, or if it’s enough to restrict the equivalences to e.g. the vicinity of a repetition operator, and he doesn’t discuss this, but I’ve made a couple of simpler attempts and could still make them blow up after some tinkering.
  - c0nstantine 4y ago
    I think I got your point. It is valid. To construct the DFA and have a finite number of derivatives we have to keep track of the following equivalences: r + r ~ r r + s ~ s + r (r + s) + t ~ r + (s + t) In [1] authors state this and refer to the proof in the original paper. They even extend it to a set of extended rules to reduce the number of terms (states) even more. Actually, the code for (lazy) DFA construction code is not even committed yet. The repo contains just sequential per-character application of the derivative to a regex. Which is obviously finite (though not efficient). Again, just to demonstrate the concept. [1] https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf
    - mananaysiempre 4y ago
      Yes, and even if you aren’t constructing a DFA, only being able to produce a finite number of derivatives from a given RE is still useful: As there’s only a finite number of derivatives, their length is obviously bounded by a constant for a fixed starting RE (though that constant is still exponential in the length of that RE). This implies your non-DFA-based matcher can only take a bounded time computing the next derivative, so takes a time proportional to the length of a string to process that string (even if the constant of proportionality is exponential in the RE length). (I’m not good at fitting all of my reasoning into a single comment today, am I?)
H8crilA 4y ago
This comment is not following HN guidelines, but: I saw this and I was immediately sure that I could make this blow up exponentially. But then I got too lazy to think about exactly how, and instead waited for kind strangers on the Internet to provide a ready solution. Thank you :) BTW, the concept is still cool.
djoldman 4y ago
try against this: https://gist.github.com/pervognsen/815b208b86066f6d7a00 https://gist.github.com/pervognsen/815b208b86066f6d7a00

SomeoneOnTheWeb 4y ago

IIRC, that's what the Rust regex engine[1] currently uses [1] https://github.com/rust-lang/regex https://github.com/rust-lang/regex

mananaysiempre 4y ago
Nope, and its author (burntsushi) doesn’t think[1,2] you can do a practical regex matcher on top of the techinque. I’m not sure I agree with him, but, well, he’s built a production engine and I haven’t. (There’s a thing called “partial derivatives”, which is to Brzozowski derivatives as NFAs are to DFAs, but it doesn’t interact well with intersection and negation if you want to support those.) [1] https://news.ycombinator.com/item?id=31693927 https://news.ycombinator.com/item?id=31693927 [2] https://news.ycombinator.com/item?id=31693559 https://news.ycombinator.com/item?id=31693559
burntsushi 4y ago
As the sibling commenter said, indeed, the regex crate does not use derivatives. If you wouldn't mind, could you share what led you to that conclusion? I'd love to fix it! I am at least currently not aware of any "production" and "general purpose" regex engine that is built on derivatives. And I'm not really sure how you'd build one. The biggest hurdle you'd have to over come as far as I can tell is that derivatives are usually used to build a DFA. In this case, the OP does matching while taking the derivative simultaneously. My guess is that you'll run into problems doing that which huge character classes, which are easy to get when Unicode is enabled. Whether "production" and "general purpose" are the same as "practical" is unclear. To put away the vague words, my understanding is that with derivatives, you'll either get slow match times or slow compilation times. (To the point where "slow" becomes enough to notice and be a problem.) With that said, the world is full of experts saying you can't do something. What I'm trying to say here is that there are some challenges I've faced in the course of building a regex engine that I simply don't know how I'd address with derivatives. Another thing worth considering here is the match semantics of the regex. I haven't had time yet to try this particular matcher, but when I do, I'd check for how alternations are matched. For example, what does 'samwise|sam' match in the haystack 'samwise'? Either answer is correct, but one is typically found in POSIX engines and the other found in Perl-like engines. Can derivatives implement either? It's also worth noting that I am not an expert on regex derivatives. I've never actually build a derivative oriented matcher. If I had, I'm sure I could be a lot more specific with my criticisms. :-)

evolveyourmind 4y ago

And here the formalized proof in less than 150 lines of code (in Agda) for Brzozowski Derivatives for regex matching (and additional regular languages theorems): https://github.com/desi-ivanov/agda-regexp-automata https://github.com/desi-ivanov/agda-regexp-automata

c0nstantine 4y ago
Thanks for sharing. I am not familiar with Agda. Will take a look. There is somewhat similar code in COQ: https://github.com/coq-community/regexp-Brzozowski https://github.com/coq-community/regexp-Brzozowski
- DonaldPShimoda 4y ago
  Just a small FYI, but the language's name (for now) is Coq, not COQ.

noelwelsh 4y ago

The next logical step is parsing with derivatives: https://matt.might.net/papers/might2011derivatives.pdf https://matt.might.net/papers/might2011derivatives.pdf I found the paper was fairly readable. YMMV.

aarchi 4y ago

I'm currently building a couple of regexp engines: One, that's a formalization[0] in Coq with big-step semantics, which uncommonly has the intersection operator, and includes several equivalence relations and a proof of the pumping lemma, excepting one case (more on that below). As a learning exercise and for historical reasons, I've also mostly ported Rust Cox's re1 engine to Rust[1], which includes VM matchers in the style of Henry Spencer, Ken Thompson, and Rob Pike. I also plan to port Doug McIlroy's engine[2], which is interesting for having intersection and complement and special handling for sublanguages, all the way down to just concatenation matched with Knuth-Morris-Pratt. I also want to examine the Rust (thanks burntsushi!), RE2, and Plan 9 engines in more depth. Once I have time to get back to the project, I want to get back to my regular expression crossword puzzle solver. For that, I'm converting the hint regexps to DFAs, that match strings of some fixed length, and concatenating and intersecting them, until a single regexp is yielded, which should be a string literal, if the puzzle has a single solution. For backreferences, it's more tricky, but I plan on rewriting backreferences to the captured expression, where the lengths of both match, then either executing it with a stack like a pushdown automata or constructing a set of constraints on the characters by index. As an aside: In my proof of the pumping lemma[3], I got stuck on the case for intersection and I'd love insight. Regular languages are closed under intersection, so the pumping lemma should hold for my implementation. I need to prove that if s =~ re1 and s =~ re2 can be pumped, then so can s =~ And re1 re2. s is is split into different substrings for re1 and re2, s = s11 ++ s12 ++ s13 = s21 ++ s22 ++ s23, then repeated an arbitrary number of times, (forall n, s11 ++ repeat s12 n ++ s13 =~ re1) and (forall n, s21 ++ repeat s22 n ++ s23 =~ re2). My intuition is that s11 = s21, s12 = s22, and s13 = s23, because they both match for the intersection, but I'm not convinced of that and haven't been able to formulate a proof for that. 0: https://github.com/thaliaarchi/recross-coq https://github.com/thaliaarchi/recross-coq 1: https://github.com/thaliaarchi/re1-rust https://github.com/thaliaarchi/re1-rust 2: https://github.com/arnoldrobbins/mcilroy-regex https://github.com/arnoldrobbins/mcilroy-regex 3: https://github.com/thaliaarchi/recross-coq/blob/main/theories/regexp_pumping.v#L117-L124 https://github.com/thaliaarchi/recross-coq/blob/main/theorie...

DonHopkins 4y ago

This "derivatives of regular expressions" technique is what James Clark used in the design of the efficient implementation of the Relax/NG tree regular expression based XML validator, based on Janusz A. Brzozowski, "Derivatives of Regular Expressions", Journal of the ACM, Volume 11, Issue 4, 1964. https://relaxng.org/jclark/design.html https://relaxng.org/jclark/design.html >Unordered content >SGML provides an & operator: A & B matches A followed by B or B followed by A. XML removed the & operator. RELAX NG reintroduces it with a twist. In SGML, a content model of A & B* requires all the B elements to be consecutive: the required A element cannot occur in between two B elements. Usually, users use the & operator because they want to allow child elements to occur in any order, so this restriction is undesirable. In RELAX NG, the corresponding operator has interleaving semantics. It matches any interleaving of a sequence containing a single A element and a sequence containing zero or more B elements; it thus allows the A element to occur anywhere, including between two B elements. >XML removed the & operator mainly because of the & operator's reputation for implementation complexity. The most difficult part of implementing the & operator in SGML is detecting whether a content model including & is 1-unambiguous. Unlike SGML, XML and W3C XML Schema, RELAX NG does not restrict content models to be 1-unambiguous, so this implementation difficulty is removed. The classic implementation technique for SGML and XML content models is to construct a Glushkov automaton. The 1-unambiguity restriction is helpful for this technique because it ensures that the Glushkov automaton is deterministic. An interleaving operator causes difficulty with this technique. However, there is an alternative implementation technique available [17] based on derivatives of regular expressions [4]. This handles content models that are not 1-unambiguous without any additional effort and can deal with interleaving without difficulty. RELAX NG imposes restrictions on the use of interleave which are sufficient to ensure that a derivative-based implementation will not exhibit exponential behavior. [4] Janusz A. Brzozowski. Derivatives of Regular Expressions. Journal of the ACM, Volume 11, Issue 4, 1964. https://dl.acm.org/doi/10.1145/321239.321249 https://dl.acm.org/doi/10.1145/321239.321249 https://dl.acm.org/doi/pdf/10.1145/321239.321249 https://dl.acm.org/doi/pdf/10.1145/321239.321249 [17] Joe English. How to validate XML. 1999. See http://www.flightlab.com/~joe/sgml/validate.html http://www.flightlab.com/~joe/sgml/validate.html

deleted 4y ago

[deleted]

djoldman 4y ago

See also: https://matt.might.net/articles/parsing-with-derivatives/ https://matt.might.net/articles/parsing-with-derivatives/ https://gist.github.com/pervognsen/815b208b86066f6d7a00 https://gist.github.com/pervognsen/815b208b86066f6d7a00