6 ms·

It's worth pointing out that the resource https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html linked above is also by the sa

It's worth pointing out that the resource https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html linked above is also by the same author, Russ Cox, as the reference I included at the end of the blog post: https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html All of the insights that I presented through this visualization tool are based upon the knowledge found in Russ Cox's articles. Also, the link above on RE2: https://github.com/google/re2 https://github.com/google/re2 is a project that was was also (started by|heavily contributed to by) Russ Cox. His writings on the topic of regular expressions are absolutely world-class and I have never found any better resource for understanding the deep low-level theory on how they work in practice.

chubot 6y ago
But Cox would dislike this formulation of regular expressions. His whole point is that Perl-stye regexes are not regular languages, and RE2 goes to great lengths to work around this fact. I'm taking up his arguments with some more traditional terminology that I think may help: http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html The entire O'Reilly book "Mastering Regular Expressions" by Friedl is based on the "debugging regexes by backtracking" approach you present here. It talks about "optimizing" regexes by reordering clauses and optimizing the backtracking. Russ Cox HATES THAT APPROACH and he wrote the entire RE2 project to advocate that it NOT be used! You do not need to optimize, reorder clauses, debug, or trace backtracking when you're using automata-based engines, because they run in guaranteed linear time and constant space (with respect to the length of the input). There is no backtracking. (I was at Google when he wrote RE2 and used it shortly afterward on big data, and regular languages are indeed better than regexes for such engineering. Also made clear by the HyperScan work.) Since his site is down I can't find the original comments, but here's a twitter exchange from 2018 that backs this up: https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/_rsc/status/1060702201159565313 https://twitter.com/_rsc/status/1060702201159565313 Also, I believe your article would be improved if you simply take out this sentence: In computer science theory, this node type should remind you of the difference between DFAs and NFAs. It is treading close to the confusion that Cox is talking about. So I would just remove, add a proper explanation, or add a link to the authoritative source. ---- I would love to see a followup that goes through the rest of the article with the Thompson VM and Pike VM approaches! :) I think the whole point is that you don't have to backtrack to implement this VM, and this page confuses that issue.
- robertelder 6y ago
  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

But Cox would dislike this formulation of regular expressions. His whole point is that Perl-stye regexes are not regular languages, and RE2 goes to great lengths to work around this fact. I'm taking up his arguments with some more traditional terminology that I think may help: http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html The entire O'Reilly book "Mastering Regular Expressions" by Friedl is based on the "debugging regexes by backtracking" approach you present here. It talks about "optimizing" regexes by reordering clauses and optimizing the backtracking. Russ Cox HATES THAT APPROACH and he wrote the entire RE2 project to advocate that it NOT be used! You do not need to optimize, reorder clauses, debug, or trace backtracking when you're using automata-based engines, because they run in guaranteed linear time and constant space (with respect to the length of the input). There is no backtracking. (I was at Google when he wrote RE2 and used it shortly afterward on big data, and regular languages are indeed better than regexes for such engineering. Also made clear by the HyperScan work.) Since his site is down I can't find the original comments, but here's a twitter exchange from 2018 that backs this up: https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/_rsc/status/1060702201159565313 https://twitter.com/_rsc/status/1060702201159565313 Also, I believe your article would be improved if you simply take out this sentence: In computer science theory, this node type should remind you of the difference between DFAs and NFAs. It is treading close to the confusion that Cox is talking about. So I would just remove, add a proper explanation, or add a link to the authoritative source. ---- I would love to see a followup that goes through the rest of the article with the Thompson VM and Pike VM approaches! :) I think the whole point is that you don't have to backtrack to implement this VM, and this page confuses that issue.

robertelder 6y ago
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*?/