5 ms·

The goal with this article was never to show the best or most efficient way to match regular expressions, but rather to convey the correct interpretation of wha

The goal with this article was never to show the best or most efficient way to match regular expressions, but rather to convey the correct interpretation of what a given regular expression will do when you try to use it. Even discussions of slow and simple backtracking regular expression matchers are a pretty niche topic and likely too much for casual users of regular expressions. Yes, I was thinking about also allowing it to optionally cross-compile to the more asymptotically efficient matching algorithm, also documented by Russ Cox. Everything takes time though, and I figured it would make to put this out there before investing too much time in something that possibly no one would use.

chubot 6y ago
Sure, but automata based engines are also "correct" and used in common tools like grep, awk, and sed. It would be nice to make that clear in the article. ----- It's a matter of preference, but to me debugging by backtracking is a pointless exercise. It's easier to reason about regexes as sets of strings, composed by sequence and alternation. Write unit tests that enumerate what you accept and reject, and build them up by composition. There's no need for debugging or tracing. I understand that the imperative style is more natural to many programmers, but I don't think it requires too much of a leap of thinking. And once you get used to the other style, it saves effort overall (as well as bounding your worst case running time).
- robertelder 6y ago
  Agreed on the point that there are better mental models out there. The difficulty is to make content that is simultaneously correct, but also not over-complicated. I finished off the post with a reference to Russ Cox's work so any sufficiently motivated individual will find the right models there.
- ridiculous_fish 6y ago
  How does the "sets of strings" model express the difference between: /x*/ and /x*?/
  - chubot 6y ago
    Good question, and here's something I wrote a couple weeks ago to the author of the Regex Lingua Franca paper [1]: I admit I occasionally use non-greedy repetition in Python, but I think that is the only construct I use that's not in the shell-ish engines. I believe it's usually pretty easy to rewrite without non-greedy, but I haven't tested that theory. ---- OK so I started testing that theory. I collected all the times I used .*? https://github.com/oilshell/blog-code/blob/master/regular-languages/survey.txt https://github.com/oilshell/blog-code/blob/master/regular-la... With a cursory inspection, most of them are unnecessary in an automata-based "regular language" engine. They are "nice to have" in a Perl-style regex engine for PERFORMANCE. But automata-based engines don't have that performance problem. They don't backtrack. The distinction between .* and .*? doesn't affect whether it matches or not, by definition. It does affects how much it backtracks. (And it affects where the submatches are, which I need to test out) So I think most of my own usages ARE "nice to have" in Python, but unnecessary in awk because it uses an automata-based engine. But I'd like to look at it more carefully, and I'm interested in answering this question more thoroughly (feel free to contact me about it, e-mail in profile). I started a demo here. Still needs work. https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh https://github.com/oilshell/blog-code/blob/master/regular-la... ---- So here's another conjecture: regexes are bad because they force you to make UNNECESSARY DISTINCTIONS in the name of performance. You have to care about greedy vs. nongreedy, because there is backtracking. In contrast, with regular languages, you just write what you mean, and they do it quickly for you. You can't write a slow expression for a regular language. There are some caveats around that, like submatch extraction with nongreedy repetition, which I will test out. If anyone has specific examples or use cases, send them my way. I can't see where I really rely on nongreedy submatches, but I'll have to look more closely. I think the nongreedy use case is usually just "skip quickly until this other string appears", e.g. the one in pgen2/tokenize.py that I didn't write. ---- As far as I remember submatch extraction works fine in automata-based engines, and Cox's articles are in a large part about the (then) little known algorithms for doing it in automata-based engines. re2c also has a 2017 paper for their algorithm to do it in DFAs: http://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf http://re2c.org/2017_trofimovich_tagged_deterministic_finite... ---- [1] thread: https://news.ycombinator.com/item?id=23687478 https://news.ycombinator.com/item?id=23687478

chubot 6y ago

Sure, but automata based engines are also "correct" and used in common tools like grep, awk, and sed. It would be nice to make that clear in the article. ----- It's a matter of preference, but to me debugging by backtracking is a pointless exercise. It's easier to reason about regexes as sets of strings, composed by sequence and alternation. Write unit tests that enumerate what you accept and reject, and build them up by composition. There's no need for debugging or tracing. I understand that the imperative style is more natural to many programmers, but I don't think it requires too much of a leap of thinking. And once you get used to the other style, it saves effort overall (as well as bounding your worst case running time).

robertelder 6y ago
Agreed on the point that there are better mental models out there. The difficulty is to make content that is simultaneously correct, but also not over-complicated. I finished off the post with a reference to Russ Cox's work so any sufficiently motivated individual will find the right models there.
ridiculous_fish 6y ago
How does the "sets of strings" model express the difference between: /x*/ and /x*?/
- chubot 6y ago
  Good question, and here's something I wrote a couple weeks ago to the author of the Regex Lingua Franca paper [1]: I admit I occasionally use non-greedy repetition in Python, but I think that is the only construct I use that's not in the shell-ish engines. I believe it's usually pretty easy to rewrite without non-greedy, but I haven't tested that theory. ---- OK so I started testing that theory. I collected all the times I used .*? https://github.com/oilshell/blog-code/blob/master/regular-languages/survey.txt https://github.com/oilshell/blog-code/blob/master/regular-la... With a cursory inspection, most of them are unnecessary in an automata-based "regular language" engine. They are "nice to have" in a Perl-style regex engine for PERFORMANCE. But automata-based engines don't have that performance problem. They don't backtrack. The distinction between .* and .*? doesn't affect whether it matches or not, by definition. It does affects how much it backtracks. (And it affects where the submatches are, which I need to test out) So I think most of my own usages ARE "nice to have" in Python, but unnecessary in awk because it uses an automata-based engine. But I'd like to look at it more carefully, and I'm interested in answering this question more thoroughly (feel free to contact me about it, e-mail in profile). I started a demo here. Still needs work. https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh https://github.com/oilshell/blog-code/blob/master/regular-la... ---- So here's another conjecture: regexes are bad because they force you to make UNNECESSARY DISTINCTIONS in the name of performance. You have to care about greedy vs. nongreedy, because there is backtracking. In contrast, with regular languages, you just write what you mean, and they do it quickly for you. You can't write a slow expression for a regular language. There are some caveats around that, like submatch extraction with nongreedy repetition, which I will test out. If anyone has specific examples or use cases, send them my way. I can't see where I really rely on nongreedy submatches, but I'll have to look more closely. I think the nongreedy use case is usually just "skip quickly until this other string appears", e.g. the one in pgen2/tokenize.py that I didn't write. ---- As far as I remember submatch extraction works fine in automata-based engines, and Cox's articles are in a large part about the (then) little known algorithms for doing it in automata-based engines. re2c also has a 2017 paper for their algorithm to do it in DFAs: http://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf http://re2c.org/2017_trofimovich_tagged_deterministic_finite... ---- [1] thread: https://news.ycombinator.com/item?id=23687478 https://news.ycombinator.com/item?id=23687478