7 ms·

The Regular Expression Visualizer, Simulator and Cross-Compiler Tool

197 points by robertelder 6y ago

hprotagonist 6y ago
along these lines, https://regex101.com https://regex101.com is consistently a godsend for writing regex.
- joehx2 6y ago
  I've used https://regexr.com/ https://regexr.com/ for composing regex.
- eddyg 6y ago
  and https://regexper.com https://regexper.com is a different type of regex visualizer compared to the OP's
- rtkwe 6y ago
  Yeah regex101 is probably the best one I've found so far. It allows you to provide sample text and shows the analysis and output you'll get including captured groups.
- sakekasi 6y ago
  +1 Regex101 is my goto for whenever I need to whip up a more complex regex
robertelder 6y ago
Hi, I'm the author of this page. This tool has a lot of complexity in it and a huge number of corner-cases. If you discover any bugs or XSS vulnerabilities, feel free to let me know.
- simonebrunozzi 6y ago
  This is fantastic, thanks for sharing it. I wish I had it when I was a CS professor in 2004-2006, teaching Compilers to 2nd year university students. They would have found it really useful.
- andialo 6y ago
  That's really impressive work. What flavor of regular expressions do you follow there?
  - robertelder 6y ago
    I tried to follow a middle-of-the-road works mostly everywhere made up flavour. Here is a grammar for it: https://blog.robertelder.org/regular-expression-parser-grammar/ https://blog.robertelder.org/regular-expression-parser-gramm... I may add to it in the future if there is enough interest. At the moment it doesn't support a few common things like word breaks and backreferences, but I don't think it'd be too hard to add.
    - indentit 6y ago
      Any chance of open sourcing it so we can contribute some regex features to your awesome project? :)
- chii 6y ago
  I tried using this expression: ^((?:(?:https?|ftps?):\/\/)|irc:\/\/|mailto:)([\w?!~^\/\\#$%&'()*+,\-.\/:;<=@]*[\w~^\/\\#$%&'()*+,\-\/:;<=@]) and it seems to fail to visualize it.
  - robertelder 6y ago
    The (?:stuff) part is for a non-capturing group which I didn't add support for. Maybe in the near future. That would be one of the easiest features to add since the tool also doesn't support backreferences yet. Edit: Actually, since the non-capturing group part doesn't add much here, you can just remove the '?:'s and this works: https://blog.robertelder.org/regular-expression-visualizer/?the_regex=%5E(((https%3F%7Cftps%3F)%3A%5C%2F%5C%2F)%7Circ%3A%5C%2F%5C%2F%7Cmailto%3A)(%5B%5Cw%3F!~%5E%5C%2F%5C%5C%23%24%25%26'()*%2B%2C%5C-.%5C%2F%3A%3B%3C%3D%40%5D*%5B%5Cw~%5E%5C%2F%5C%5C%23%24%25%26'()*%2B%2C%5C-%5C%2F%3A%3B%3C%3D%40%5D)&the_subject=mailto%3A%5Ep81 https://blog.robertelder.org/regular-expression-visualizer/?...
    - Serow225 6y ago
      The first one that I tried also failed for the same reason, FWIW. Cool tool! :)
- mlyle 6y ago
  I'm having trouble with backtracking and groups. It's possible I'm doing something wrong, but [bc]*(cd)+ doesn't seem to match cbcdcd Nor does the simpler a*(ab) match aab But a*ab matches aab.
  - robertelder 6y ago
    You found a bug. The bug was: When I was computing the animation frames for the visual, after a backtracking event, I forgot to restore the 'progress' values for the PROGRESS nodes to what they were before the stack push took place. I think I fixed this issue, and I just pushed an update which should appear any second when the cache invalidates.
    - mlyle 6y ago
      Cool! Thanks for looking at it/fixing it. P.S. The whole split() thing you do is an interesting hack to not have to preserve/rewind so much state. :D I've never quite seen fork() used so...
vmchale 6y ago
neato bandito
jjice 6y ago
I would have loved this when I worked on a regex engine a few years back. It was before I took my CS theory course and had no idea what an automaton was. Let me tell you, having a formal theory and visualization in front of you while working on something is extremely helpful. This looks like it would be a great tool for both people looking to learn, and those who are looking to optimize their regular expressions as well.
maddyboo 6y ago
When I read the title, I half hoped ‘cross-compiler’ referred to translating between different regex varieties. Anyone know of a tool that does this?
gfxgirl 6y ago
Any one write an AST aware regex engine? Examples: replace s/(?ast:comment)foo/bar to replace foo with bar but only in comments. Or s/(\w+): (?ast:openparent)(.?)(?ast:closeparen)\s+(?ast:openbracked)(.?)(?ast:closebracket)/function $1($2)\n{\n$3\n}\n/ to convert from foo: (args) { codeblock } to function foo(args) { codeblock } etc..?
- vnorilo 6y ago
  That's awkward because parsing ASTs can't usually be done with a regular language (for most programming languages), so a language-specific parser would be needed on top anyway. This stuff is useful, though, and easy to do in lisps and schemes.
- chubot 6y ago
  semgrep will at least do the search portion, not sure about replace. Posted a few days ago: https://news.ycombinator.com/item?id=23919313 https://news.ycombinator.com/item?id=23919313 Slightly related: How to Build Static Checking Systems Using Orders of Magnitude Less Code https://web.stanford.edu/~mlfbrown/paper.pdf https://web.stanford.edu/~mlfbrown/paper.pdf They use "microgrammars" and found that the technique is surprisingly effective despite not being "correct".
- arnsholt 6y ago
  Perl 6 extends the regex system to be a full fledged recursive descent parser, which lets you do this kind of stuff. But as is pointed out in a sibling comment, a purely regular regex engine won't really do it since it's non-regular language. Of course, some regex engines do let you do this (notably Perl 5), but it requires code of the "just because you can doesn't mean you should" variety.
twistedpair 6y ago
Nice graphical explanations! It would be nice to see positive/negative look ahead/behind support as they're pretty powerful. The `\K` flag to clear the capture buffer (e.g. Perl flavor) is also a very useful regexp feature absent here (e.g. when testing `grep` commands).
chubot 6y ago
Note that when you use grep, awk, sed, libc regexec(), RE2 [1], or rust/regex, this isn't how your regexes are executed. They use automata-based engines whereas this is a backtracking engine, which can blow up on small inputs. (Although I will say the C code here is cool, because it gives you a fork() bomb, so it might exhaust your operating system and not just your CPU!) Canonical reference: Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Archive since it's down at the moment due to some App Engine stuff (!): https://web.archive.org/web/20200624195819/https://swtch.com/~rsc/regexp/regexp1.html https://web.archive.org/web/20200624195819/https://swtch.com... My blog post and sample code that verifies that GNU grep, awk, sed, and libc don't backtrack: Comments on Eggex and Regular Languages http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html https://github.com/oilshell/blog-code/tree/master/regular-languages https://github.com/oilshell/blog-code/tree/master/regular-la... [1] https://github.com/google/re2 https://github.com/google/re2 ---- Also, the production quality way of compiling regular expressions to C code looks like this [2], which is completely different than what's shown in the article: https://www.oilshell.org/release/0.8.pre8/source-code.wwz/_devbuild/gen/osh-lex.h https://www.oilshell.org/release/0.8.pre8/source-code.wwz/_d... The regex is converted to an NFA, then a DFA, then a bunch of switch/goto statements in C that implement the DFA. This example is huge, but the switch/goto and lack of any notion of "threading" is the important point. Essentially, the instruction pointer is used as the DFA state. It's a very natural use of "goto" (where you don't write or debug them yourself) [2] via http://re2c.org/ http://re2c.org/ (not related to RE2)
- robertelder 6y ago
  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.
x87678r 6y ago
Any suggestions to keep regexes simple? They often grow to huge lengths which are hard to read and/or debug. It would be nice to keep modular. Maybe using websites like this is the only way.
- chubot 6y ago
  In Python or Perl, you can use re.VERBOSE or /x to spread your regex across multiple lines. That helps a little, but the syntax is still pretty obscure. I created a new regular language syntax for Oil which looks more like a grammar: Eggex Example: Recognizing Python Integer Literals http://www.oilshell.org/blog/2019/12/22.html http://www.oilshell.org/blog/2019/12/22.html And the nice thing is that you can modularize and compose patterns (without string concatenation). It is more like AST splicing of regexes. There are details in the article but here's how it looks: DecDigit = / [0-9] / BinDigit = / [0-1] / OctDigit = / [0-7] / HexDigit = / [0-9 a-f A-F] / DecInt = / [1-9] ('_'? DecDigit)* | '0'+ ('_'? '0')* / BinInt = / '0' [b B] ('_'? BinDigit)+ / OctInt = / '0' [o O] ('_'? OctDigit)+ / HexInt = / '0' [x X] ('_'? HexDigit)+ / Integer = / DecInt | BinInt | OctInt | HexInt / To accept 123, 0b10101, 0o755, 0xff but reject non-integers.

197 points by robertelder 6y ago

hprotagonist 6y ago

along these lines, https://regex101.com https://regex101.com is consistently a godsend for writing regex.

joehx2 6y ago
I've used https://regexr.com/ https://regexr.com/ for composing regex.
eddyg 6y ago
and https://regexper.com https://regexper.com is a different type of regex visualizer compared to the OP's
rtkwe 6y ago
Yeah regex101 is probably the best one I've found so far. It allows you to provide sample text and shows the analysis and output you'll get including captured groups.
sakekasi 6y ago
+1 Regex101 is my goto for whenever I need to whip up a more complex regex

robertelder 6y ago

Hi, I'm the author of this page. This tool has a lot of complexity in it and a huge number of corner-cases. If you discover any bugs or XSS vulnerabilities, feel free to let me know.

simonebrunozzi 6y ago
This is fantastic, thanks for sharing it. I wish I had it when I was a CS professor in 2004-2006, teaching Compilers to 2nd year university students. They would have found it really useful.
andialo 6y ago
That's really impressive work. What flavor of regular expressions do you follow there?
- robertelder 6y ago
  I tried to follow a middle-of-the-road works mostly everywhere made up flavour. Here is a grammar for it: https://blog.robertelder.org/regular-expression-parser-grammar/ https://blog.robertelder.org/regular-expression-parser-gramm... I may add to it in the future if there is enough interest. At the moment it doesn't support a few common things like word breaks and backreferences, but I don't think it'd be too hard to add.
  - indentit 6y ago
    Any chance of open sourcing it so we can contribute some regex features to your awesome project? :)
chii 6y ago
I tried using this expression: ^((?:(?:https?|ftps?):\/\/)|irc:\/\/|mailto:)([\w?!~^\/\\#$%&'()*+,\-.\/:;<=@]*[\w~^\/\\#$%&'()*+,\-\/:;<=@]) and it seems to fail to visualize it.
- robertelder 6y ago
  The (?:stuff) part is for a non-capturing group which I didn't add support for. Maybe in the near future. That would be one of the easiest features to add since the tool also doesn't support backreferences yet. Edit: Actually, since the non-capturing group part doesn't add much here, you can just remove the '?:'s and this works: https://blog.robertelder.org/regular-expression-visualizer/?the_regex=%5E(((https%3F%7Cftps%3F)%3A%5C%2F%5C%2F)%7Circ%3A%5C%2F%5C%2F%7Cmailto%3A)(%5B%5Cw%3F!~%5E%5C%2F%5C%5C%23%24%25%26'()*%2B%2C%5C-.%5C%2F%3A%3B%3C%3D%40%5D*%5B%5Cw~%5E%5C%2F%5C%5C%23%24%25%26'()*%2B%2C%5C-%5C%2F%3A%3B%3C%3D%40%5D)&the_subject=mailto%3A%5Ep81 https://blog.robertelder.org/regular-expression-visualizer/?...
  - Serow225 6y ago
    The first one that I tried also failed for the same reason, FWIW. Cool tool! :)
mlyle 6y ago
I'm having trouble with backtracking and groups. It's possible I'm doing something wrong, but [bc]*(cd)+ doesn't seem to match cbcdcd Nor does the simpler a*(ab) match aab But a*ab matches aab.
- robertelder 6y ago
  You found a bug. The bug was: When I was computing the animation frames for the visual, after a backtracking event, I forgot to restore the 'progress' values for the PROGRESS nodes to what they were before the stack push took place. I think I fixed this issue, and I just pushed an update which should appear any second when the cache invalidates.
  - mlyle 6y ago
    Cool! Thanks for looking at it/fixing it. P.S. The whole split() thing you do is an interesting hack to not have to preserve/rewind so much state. :D I've never quite seen fork() used so...

vmchale 6y ago

neato bandito

jjice 6y ago

I would have loved this when I worked on a regex engine a few years back. It was before I took my CS theory course and had no idea what an automaton was. Let me tell you, having a formal theory and visualization in front of you while working on something is extremely helpful. This looks like it would be a great tool for both people looking to learn, and those who are looking to optimize their regular expressions as well.

maddyboo 6y ago

When I read the title, I half hoped ‘cross-compiler’ referred to translating between different regex varieties. Anyone know of a tool that does this?

gfxgirl 6y ago

Any one write an AST aware regex engine? Examples: replace s/(?ast:comment)foo/bar to replace foo with bar but only in comments. Or s/(\w+): (?ast:openparent)(.?)(?ast:closeparen)\s+(?ast:openbracked)(.?)(?ast:closebracket)/function $1($2)\n{\n$3\n}\n/ to convert from foo: (args) { codeblock } to function foo(args) { codeblock } etc..?

vnorilo 6y ago
That's awkward because parsing ASTs can't usually be done with a regular language (for most programming languages), so a language-specific parser would be needed on top anyway. This stuff is useful, though, and easy to do in lisps and schemes.
chubot 6y ago
semgrep will at least do the search portion, not sure about replace. Posted a few days ago: https://news.ycombinator.com/item?id=23919313 https://news.ycombinator.com/item?id=23919313 Slightly related: How to Build Static Checking Systems Using Orders of Magnitude Less Code https://web.stanford.edu/~mlfbrown/paper.pdf https://web.stanford.edu/~mlfbrown/paper.pdf They use "microgrammars" and found that the technique is surprisingly effective despite not being "correct".
arnsholt 6y ago
Perl 6 extends the regex system to be a full fledged recursive descent parser, which lets you do this kind of stuff. But as is pointed out in a sibling comment, a purely regular regex engine won't really do it since it's non-regular language. Of course, some regex engines do let you do this (notably Perl 5), but it requires code of the "just because you can doesn't mean you should" variety.

twistedpair 6y ago

Nice graphical explanations! It would be nice to see positive/negative look ahead/behind support as they're pretty powerful. The `\K` flag to clear the capture buffer (e.g. Perl flavor) is also a very useful regexp feature absent here (e.g. when testing `grep` commands).

chubot 6y ago

Note that when you use grep, awk, sed, libc regexec(), RE2 [1], or rust/regex, this isn't how your regexes are executed. They use automata-based engines whereas this is a backtracking engine, which can blow up on small inputs. (Although I will say the C code here is cool, because it gives you a fork() bomb, so it might exhaust your operating system and not just your CPU!) Canonical reference: Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Archive since it's down at the moment due to some App Engine stuff (!): https://web.archive.org/web/20200624195819/https://swtch.com/~rsc/regexp/regexp1.html https://web.archive.org/web/20200624195819/https://swtch.com... My blog post and sample code that verifies that GNU grep, awk, sed, and libc don't backtrack: Comments on Eggex and Regular Languages http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html https://github.com/oilshell/blog-code/tree/master/regular-languages https://github.com/oilshell/blog-code/tree/master/regular-la... [1] https://github.com/google/re2 https://github.com/google/re2 ---- Also, the production quality way of compiling regular expressions to C code looks like this [2], which is completely different than what's shown in the article: https://www.oilshell.org/release/0.8.pre8/source-code.wwz/_devbuild/gen/osh-lex.h https://www.oilshell.org/release/0.8.pre8/source-code.wwz/_d... The regex is converted to an NFA, then a DFA, then a bunch of switch/goto statements in C that implement the DFA. This example is huge, but the switch/goto and lack of any notion of "threading" is the important point. Essentially, the instruction pointer is used as the DFA state. It's a very natural use of "goto" (where you don't write or debug them yourself) [2] via http://re2c.org/ http://re2c.org/ (not related to RE2)

robertelder 6y ago
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.

x87678r 6y ago

Any suggestions to keep regexes simple? They often grow to huge lengths which are hard to read and/or debug. It would be nice to keep modular. Maybe using websites like this is the only way.

chubot 6y ago
In Python or Perl, you can use re.VERBOSE or /x to spread your regex across multiple lines. That helps a little, but the syntax is still pretty obscure. I created a new regular language syntax for Oil which looks more like a grammar: Eggex Example: Recognizing Python Integer Literals http://www.oilshell.org/blog/2019/12/22.html http://www.oilshell.org/blog/2019/12/22.html And the nice thing is that you can modularize and compose patterns (without string concatenation). It is more like AST splicing of regexes. There are details in the article but here's how it looks: DecDigit = / [0-9] / BinDigit = / [0-1] / OctDigit = / [0-7] / HexDigit = / [0-9 a-f A-F] / DecInt = / [1-9] ('_'? DecDigit)* | '0'+ ('_'? '0')* / BinInt = / '0' [b B] ('_'? BinDigit)+ / OctInt = / '0' [o O] ('_'? OctDigit)+ / HexInt = / '0' [x X] ('_'? HexDigit)+ / Integer = / DecInt | BinInt | OctInt | HexInt / To accept 123, 0b10101, 0o755, 0xff but reject non-integers.