6 ms·

Regular expression matching can be simple and fast (2007)

141 points by momonga 2y ago

Aerbil313 2y ago
I've recently discovered Lua Parsing Expression Grammars (LPEG)[1]. They are built on a different approach to parsing and are much more capable than conventional regexes, able to handle recursive sequences, able to include code, have debugging utilities, are often much more performant than regexes and they are an absolute delight to work with. It also has a module called re [2] which uses a similar syntax to regexes. 1: https://www.inf.puc-rio.br/~roberto/lpeg/ https://www.inf.puc-rio.br/~roberto/lpeg/ 2: https://www.inf.puc-rio.br/~roberto/lpeg/re.html https://www.inf.puc-rio.br/~roberto/lpeg/re.html
jjice 2y ago
This and the associated series of regex posts from Russ Cox are probably the best content on practical regular expression engine internals you can get. If you have a cursory understanding of NFAs and DFAs, it's some of the best technical writing I've ever had the pleasure to read. These posts are responsible for my love of regular expressions :)
- joe_guy 2y ago
  You may also find this very detailed post interesting https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/ https://devblogs.microsoft.com/dotnet/regular-expression-imp... It's an indepth look at where regex in dotnet was prior to and after version 7.
- kqr 2y ago
  And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding. These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.
  - banish-m4 2y ago
    NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence. The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions. PS: All your DAGs are belong to us.
    - gliptic 2y ago
      NFAs are decidable. As you said, a NFA can be converted to a DFA which is decidable. Maybe you mean they are non-deterministic (that's in the name)?
      - banish-m4 2y ago
        You know what I meant. I used the wrong word.
    - ablob 2y ago
      There exist algorithms that deal with state blow-up. In fact, these algorithms project any given DFA into an equivalent DFA of minimal size - guaranteeing a minimal automaton for the language that is accepted by it. In essence, you build equivalence classes between states with respect to possible paths they can take into other equivalence classes for further input. State machines for LR-Grammars are vastly more complex in comparison to NFA automata, so for most (if not all) applications, a computer that can deal with LR-Grammars will be able to handle a NFA conversion with a subsequent minimization.
    - mikhailfranco 2y ago
      It is possible to implement NFAs directly, in parallel: https://github.com/mike-french/myrex https://github.com/mike-french/myrex Just fan-out messages to all downstream states. Let a fair runtime system evaluate all progress, then tally results along all paths, for example: https://github.com/mike-french/myrex?tab=readme-ov-file#executor-example https://github.com/mike-french/myrex?tab=readme-ov-file#exec... The approach can also be adapted to captures and their many, many possible ambiguities. There is an example that generalizes a highly ambiguous match given in Cox: regex (a?){m}(a*){m} against a string of a{m}. The case m=9 gives 864k possible solutions (traversals), you may optionally ask for all of them to be returned: https://github.com/mike-french/myrex?tab=readme-ov-file#ambiguous-example https://github.com/mike-french/myrex?tab=readme-ov-file#ambi... The processes share nothing, all state is in the messages, so a single network can process multiple input strings simultaneously. It can also generate Monte-Carlo strings that match the regex, and those may also proceed simultaneously.
- bane 2y ago
  Many years ago, as a fresh out of college young coder, I had to come up with a way to check types on an text input file in C++ -- long before C++ had even a standard String type let alone regex libraries like pcre. The standard conversion functions at the time expected you to have done some type detection beforehand. Each field in the file could contain a string, an int, or a float. In particular to figure out the floats, I remember sitting down for a few hours and coming up with a regular expression, testing it in Perl on a bunch of test cases, and then went about the hard work of slowly converting the regex into an NFA to a DFA and then finally to an adjacency graph in a 2d matrix. A little bit of code to read in things a byte at a time and some simple arithmetic and I had a stupid fast bool isFloat(char *) Nobody at my work understood the code, they just sort of knew that if they submitted a character array with a field value into it, something happened with a big matrix, and it you let them know if it was a float or not and then they could call the appropriate conversion function -- I think stof() or whatever was in fashion back then. I had to make one revision to it for an edge case I missed and then it found its way into pretty much all code for the company after that. The tuition for the class that taught me how to do that payed for itself with that one function.
ChrisArchitect 2y ago
Some discussion from 5 years ago: https://news.ycombinator.com/item?id=20310669 https://news.ycombinator.com/item?id=20310669
- dang 2y ago
  Thanks! Macroexpanded: Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=20310669 https://news.ycombinator.com/item?id=20310669 - June 2019 (33 comments) Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=16341519 https://news.ycombinator.com/item?id=16341519 - Feb 2018 (20 comments) Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=9374858 https://news.ycombinator.com/item?id=9374858 - April 2015 (16 comments) Regular Expression Matching Can Be Simple And Fast [2007] - https://news.ycombinator.com/item?id=6593331 https://news.ycombinator.com/item?id=6593331 - Oct 2013 (1 comment) Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=820201 https://news.ycombinator.com/item?id=820201 - Sept 2009 (15 comments) Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=466845 https://news.ycombinator.com/item?id=466845 - Feb 2009 (17 comments)
rurban 2y ago
Perl needed a couple of years to catchup. At first they had no idea what Russ was talking about
adrianN 2y ago
Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.
- secondcoming 2y ago
  Well if people spend time learning arcane regex syntax it'd be a shame to not use them! But yes, you're right. Sometimes simple finds are sufficient.
- cies 2y ago
  Or write a parser! In most cases the parser will not be shorter (code) than the regex, but it will most certainly be simpler (cognitively; it's hard to understand all that regexes do, they're close to magic) and more testable (you can test the parts of the parser, like the number parser or the string parser, individually), and often faster too.
  - cies 2y ago
    https://stackoverflow.com/questions/11905506/regular-expression-vs-string-parsing https://stackoverflow.com/questions/11905506/regular-express...
- hyperpape 2y ago
  There's pretty wide variety in the performance of regular expressions between different languages, and efficient implementations will often recognize when your regular expression has a literal suffix/prefix, and optimize accordingly. That doesn't help you if you're stuck using a library that doesn't perform those optimizations, but it means you need to be careful about importing your assumptions about regex performance from one language to another. See also: https://github.com/burntSushi/rebar https://github.com/burntSushi/rebar
- zeckalpha 2y ago
  Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.
chx 2y ago
> As mentioned earlier, no one knows how to implement regular expressions with backreferences efficiently, though no one can prove that it's impossible either. (Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.) It really needs to be noted how NP-complete and an algorithm efficient in practice have nothing to do with each other. If an algorithm takes C * 1.000...eighty zeroes...1^n time it is exponential but for any n you will encounter in real life the time it takes will be indistinguishable from C.
- bubblyworld 2y ago
  There's a fun list of problems like this here: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant https://cstheory.stackexchange.com/questions/6660/polynomial... On the other hand, it's remarkable that so many algorithms _do_ have reasonable constants/exponents. So the concept works pretty well.
- andrewla 2y ago
  And the converse as well -- an algorithm that is 10,000,000 * n^17 is going to be effectively intractable but falls neatly into P. And the reality is that most NP-complete problems are well-solved by heuristics except in strange combinatorial corners. It's why we can't just create encryption systems based on knowing the correct answer to an NP-complete problem; most of the problem instances will be too easy to solve.
kayodelycaon 2y ago
It's easy to miss in the article, but the reason most regex engines exhibit Perl's behavior is due to features like back referencing. (And I assume look behinds and look aheads.) PCRE and theoretically pure regular expressions are different things.
- eyelidlessness 2y ago
  FWIW, it seems pretty likely the same multi-NFA algorithm described in the article could be applied to other backtracking scenarios (and therefore to back references and lookaround). Since I’m just speculating, I’ll hazard a guess that it would result in a meaningfully more complex implementation to derive each state machine, and potentially much slower (while still “linear” complexity).
  - burntsushi 2y ago
    As the OP specifically and explicitly says, back-references are definitively NP-complete. The OP even links to a proof[1]. If you found a way to implement them in worst case linear time, then I believe you would have discovered a constructive proof for p=np. Look-around is a different story, but I don't believe you can still guarantee linear time. [1]: https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html
    - mananaysiempre 2y ago
      I also wanted to post that link, but now that I’m rereading it I’m starting to doubt that it proves what we want it to prove here. The way it’s presented, the size of the 3-SAT formula corresponds to the size of the expression, not the size of the haystack; and that compiling a regex is exponential in its length is not exactly a surprise—the standard determinization procedure used to compile actually regular (no backreferences) regexes for linear matching is also exponential. So what we’d actually want to prove is along the lines of NP-completeness even if we allow for an exponential amount of preprocessing on the expression only. (I’m willing to believe backreference matching is NP-complete, I just think the linked statement is weaker than that.)
plesner 2y ago
This is a fine introduction to automata-based regexps but the framing of comparing "good" automata with "bad" perl-style is misguided. Automata and perl-style regexps are different beasts and solve different problems. The problem seems to be one of terminology: the perl style should never have been called regexps. That's not what they are. It's a pattern language that happens to have a variant of regexps as a subset.

141 points by momonga 2y ago

I've recently discovered Lua Parsing Expression Grammars (LPEG)[1]. They are built on a different approach to parsing and are much more capable than conventional regexes, able to handle recursive sequences, able to include code, have debugging utilities, are often much more performant than regexes and they are an absolute delight to work with. It also has a module called re [2] which uses a similar syntax to regexes. 1: https://www.inf.puc-rio.br/~roberto/lpeg/ https://www.inf.puc-rio.br/~roberto/lpeg/ 2: https://www.inf.puc-rio.br/~roberto/lpeg/re.html https://www.inf.puc-rio.br/~roberto/lpeg/re.html

jjice 2y ago

This and the associated series of regex posts from Russ Cox are probably the best content on practical regular expression engine internals you can get. If you have a cursory understanding of NFAs and DFAs, it's some of the best technical writing I've ever had the pleasure to read. These posts are responsible for my love of regular expressions :)

joe_guy 2y ago
You may also find this very detailed post interesting https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/ https://devblogs.microsoft.com/dotnet/regular-expression-imp... It's an indepth look at where regex in dotnet was prior to and after version 7.
kqr 2y ago
And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding. These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.
- banish-m4 2y ago
  NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence. The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions. PS: All your DAGs are belong to us.
  - gliptic 2y ago
    NFAs are decidable. As you said, a NFA can be converted to a DFA which is decidable. Maybe you mean they are non-deterministic (that's in the name)?
    - banish-m4 2y ago
      You know what I meant. I used the wrong word.
  - ablob 2y ago
    There exist algorithms that deal with state blow-up. In fact, these algorithms project any given DFA into an equivalent DFA of minimal size - guaranteeing a minimal automaton for the language that is accepted by it. In essence, you build equivalence classes between states with respect to possible paths they can take into other equivalence classes for further input. State machines for LR-Grammars are vastly more complex in comparison to NFA automata, so for most (if not all) applications, a computer that can deal with LR-Grammars will be able to handle a NFA conversion with a subsequent minimization.
  - mikhailfranco 2y ago
    It is possible to implement NFAs directly, in parallel: https://github.com/mike-french/myrex https://github.com/mike-french/myrex Just fan-out messages to all downstream states. Let a fair runtime system evaluate all progress, then tally results along all paths, for example: https://github.com/mike-french/myrex?tab=readme-ov-file#executor-example https://github.com/mike-french/myrex?tab=readme-ov-file#exec... The approach can also be adapted to captures and their many, many possible ambiguities. There is an example that generalizes a highly ambiguous match given in Cox: regex (a?){m}(a*){m} against a string of a{m}. The case m=9 gives 864k possible solutions (traversals), you may optionally ask for all of them to be returned: https://github.com/mike-french/myrex?tab=readme-ov-file#ambiguous-example https://github.com/mike-french/myrex?tab=readme-ov-file#ambi... The processes share nothing, all state is in the messages, so a single network can process multiple input strings simultaneously. It can also generate Monte-Carlo strings that match the regex, and those may also proceed simultaneously.
bane 2y ago
Many years ago, as a fresh out of college young coder, I had to come up with a way to check types on an text input file in C++ -- long before C++ had even a standard String type let alone regex libraries like pcre. The standard conversion functions at the time expected you to have done some type detection beforehand. Each field in the file could contain a string, an int, or a float. In particular to figure out the floats, I remember sitting down for a few hours and coming up with a regular expression, testing it in Perl on a bunch of test cases, and then went about the hard work of slowly converting the regex into an NFA to a DFA and then finally to an adjacency graph in a 2d matrix. A little bit of code to read in things a byte at a time and some simple arithmetic and I had a stupid fast bool isFloat(char *) Nobody at my work understood the code, they just sort of knew that if they submitted a character array with a field value into it, something happened with a big matrix, and it you let them know if it was a float or not and then they could call the appropriate conversion function -- I think stof() or whatever was in fashion back then. I had to make one revision to it for an edge case I missed and then it found its way into pretty much all code for the company after that. The tuition for the class that taught me how to do that payed for itself with that one function.

ChrisArchitect 2y ago

Some discussion from 5 years ago: https://news.ycombinator.com/item?id=20310669 https://news.ycombinator.com/item?id=20310669

dang 2y ago
Thanks! Macroexpanded: Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=20310669 https://news.ycombinator.com/item?id=20310669 - June 2019 (33 comments) Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=16341519 https://news.ycombinator.com/item?id=16341519 - Feb 2018 (20 comments) Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=9374858 https://news.ycombinator.com/item?id=9374858 - April 2015 (16 comments) Regular Expression Matching Can Be Simple And Fast [2007] - https://news.ycombinator.com/item?id=6593331 https://news.ycombinator.com/item?id=6593331 - Oct 2013 (1 comment) Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=820201 https://news.ycombinator.com/item?id=820201 - Sept 2009 (15 comments) Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=466845 https://news.ycombinator.com/item?id=466845 - Feb 2009 (17 comments)

rurban 2y ago

Perl needed a couple of years to catchup. At first they had no idea what Russ was talking about

adrianN 2y ago

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

secondcoming 2y ago
Well if people spend time learning arcane regex syntax it'd be a shame to not use them! But yes, you're right. Sometimes simple finds are sufficient.
cies 2y ago
Or write a parser! In most cases the parser will not be shorter (code) than the regex, but it will most certainly be simpler (cognitively; it's hard to understand all that regexes do, they're close to magic) and more testable (you can test the parts of the parser, like the number parser or the string parser, individually), and often faster too.
- cies 2y ago
  https://stackoverflow.com/questions/11905506/regular-expression-vs-string-parsing https://stackoverflow.com/questions/11905506/regular-express...
hyperpape 2y ago
There's pretty wide variety in the performance of regular expressions between different languages, and efficient implementations will often recognize when your regular expression has a literal suffix/prefix, and optimize accordingly. That doesn't help you if you're stuck using a library that doesn't perform those optimizations, but it means you need to be careful about importing your assumptions about regex performance from one language to another. See also: https://github.com/burntSushi/rebar https://github.com/burntSushi/rebar
zeckalpha 2y ago
Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

chx 2y ago

> As mentioned earlier, no one knows how to implement regular expressions with backreferences efficiently, though no one can prove that it's impossible either. (Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.) It really needs to be noted how NP-complete and an algorithm efficient in practice have nothing to do with each other. If an algorithm takes C * 1.000...eighty zeroes...1^n time it is exponential but for any n you will encounter in real life the time it takes will be indistinguishable from C.

bubblyworld 2y ago
There's a fun list of problems like this here: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant https://cstheory.stackexchange.com/questions/6660/polynomial... On the other hand, it's remarkable that so many algorithms _do_ have reasonable constants/exponents. So the concept works pretty well.
andrewla 2y ago
And the converse as well -- an algorithm that is 10,000,000 * n^17 is going to be effectively intractable but falls neatly into P. And the reality is that most NP-complete problems are well-solved by heuristics except in strange combinatorial corners. It's why we can't just create encryption systems based on knowing the correct answer to an NP-complete problem; most of the problem instances will be too easy to solve.

kayodelycaon 2y ago

It's easy to miss in the article, but the reason most regex engines exhibit Perl's behavior is due to features like back referencing. (And I assume look behinds and look aheads.) PCRE and theoretically pure regular expressions are different things.

eyelidlessness 2y ago
FWIW, it seems pretty likely the same multi-NFA algorithm described in the article could be applied to other backtracking scenarios (and therefore to back references and lookaround). Since I’m just speculating, I’ll hazard a guess that it would result in a meaningfully more complex implementation to derive each state machine, and potentially much slower (while still “linear” complexity).
- burntsushi 2y ago
  As the OP specifically and explicitly says, back-references are definitively NP-complete. The OP even links to a proof[1]. If you found a way to implement them in worst case linear time, then I believe you would have discovered a constructive proof for p=np. Look-around is a different story, but I don't believe you can still guarantee linear time. [1]: https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html
  - mananaysiempre 2y ago
    I also wanted to post that link, but now that I’m rereading it I’m starting to doubt that it proves what we want it to prove here. The way it’s presented, the size of the 3-SAT formula corresponds to the size of the expression, not the size of the haystack; and that compiling a regex is exponential in its length is not exactly a surprise—the standard determinization procedure used to compile actually regular (no backreferences) regexes for linear matching is also exponential. So what we’d actually want to prove is along the lines of NP-completeness even if we allow for an exponential amount of preprocessing on the expression only. (I’m willing to believe backreference matching is NP-complete, I just think the linked statement is weaker than that.)

plesner 2y ago

This is a fine introduction to automata-based regexps but the framing of comparing "good" automata with "bad" perl-style is misguided. Automata and perl-style regexps are different beasts and solve different problems. The problem seems to be one of terminology: the perl style should never have been called regexps. That's not what they are. It's a pattern language that happens to have a variant of regexps as a subset.