<story><title>Regex engine internals as a library</title><url>https://blog.burntsushi.net/regex-internals/</url></story><parent_chain><item><author>jjice</author><text>I&amp;#x27;ve only given a quick read&amp;#x2F;skim, but this is extremely impressive. BurntSushi has a lot of create stuff out there, but the Rust regex crate is legendary. The fact that Rust has had such a performant and easy to use regular expression library for so long is a real treat to the community.&lt;p&gt;This article as a whole is also a treasure. There&amp;#x27;s a fairly limited number of people who have written a ton about regular expressions, but they all do so extremely well. Russ Cox&amp;#x27;s article series (as mentioned in this one) is really great. I used it in college to write a regular expression engine one summer after I had started to fall in love with the perfect cross between theory and practice that regular expressions are.&lt;p&gt;The changes for more in depth testing here are also very interesting, especially for a crate that I&amp;#x27;m sure if critical so a lot of the ecosystem, and I appreciate the writeup on such a deep dive topic.&lt;p&gt;Are regular expressions hard to read? Sometimes they can, especially if you haven&amp;#x27;t gone out of your way to take deep dives. Are they not perfect for a lot of parsing tasks? Sure, there are definitely things people shouldn&amp;#x27;t use regexs for that they do, like validating emails. At their core though, regular expressions are one of the most power dense tools we have in pretty much every language. The insane stuff you can get done (sometimes in a way that would be frowned upon) in so little time if just incredible.&lt;p&gt;I&amp;#x27;d love for there to be more content on regular expressions as well. Right now I&amp;#x27;m only familiar with one book that really does a great job (at a practical level), and that&amp;#x27;s Mastering Regular Expressions by Jeffrey Friedl. On a theory level, a lot of compiler books will talk about them to varying degrees. The Dragon Book has some good content on regular expressions at an implementation level too.&lt;p&gt;Does anyone have any other book recommendations for regular expressions?&lt;p&gt;And if BurntSushi or any other regular expression engine contributors see this, I really appreciate the effort y&amp;#x27;all put in to building such powerful software.</text></item></parent_chain><comment><author>btown</author><text>&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.cs.princeton.edu&amp;#x2F;courses&amp;#x2F;archive&amp;#x2F;fall19&amp;#x2F;cos226&amp;#x2F;lectures&amp;#x2F;54RegularExpressions.pdf&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.cs.princeton.edu&amp;#x2F;courses&amp;#x2F;archive&amp;#x2F;fall19&amp;#x2F;cos226&amp;#x2F;l...&lt;/a&gt; and &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;kean.blog&amp;#x2F;post&amp;#x2F;lets-build-regex&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;kean.blog&amp;#x2F;post&amp;#x2F;lets-build-regex&lt;/a&gt; are excellent introductions to implementing a (very) simplified regex engine: construct a nondetermistic finite state automaton for the regex, then perform a graph search on the resulting digraph; if the vertex corresponding to your end state is reachable, you have a match.&lt;p&gt;I think this exercise is valuable for anyone writing regexes to not only understand that there&amp;#x27;s less magic than one might think, but also to visualize a bunch of balls bouncing along an NFA - that bug you inevitably hit in production due to catastrophic backtracking now takes on a physical meaning!&lt;p&gt;Separately re: the OP, &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;rust-lang&amp;#x2F;regex&amp;#x2F;issues&amp;#x2F;822&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;rust-lang&amp;#x2F;regex&amp;#x2F;issues&amp;#x2F;822&lt;/a&gt; (and specifically BurntSushi&amp;#x27;s comment at the very end of the issue) adds really useful context to the paragraph in the OP about niche APIs: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;blog.burntsushi.net&amp;#x2F;regex-internals&amp;#x2F;#problem-requests-for-niche-apis&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;blog.burntsushi.net&amp;#x2F;regex-internals&amp;#x2F;#problem-request...&lt;/a&gt; - searching with multiple regexes simultaneously against a text is both incredibly complex and incredibly useful, and I can&amp;#x27;t wait to see what the community comes up with for this pattern!</text></comment>
<story><title>Regex engine internals as a library</title><url>https://blog.burntsushi.net/regex-internals/</url></story><parent_chain><item><author>jjice</author><text>I&amp;#x27;ve only given a quick read&amp;#x2F;skim, but this is extremely impressive. BurntSushi has a lot of create stuff out there, but the Rust regex crate is legendary. The fact that Rust has had such a performant and easy to use regular expression library for so long is a real treat to the community.&lt;p&gt;This article as a whole is also a treasure. There&amp;#x27;s a fairly limited number of people who have written a ton about regular expressions, but they all do so extremely well. Russ Cox&amp;#x27;s article series (as mentioned in this one) is really great. I used it in college to write a regular expression engine one summer after I had started to fall in love with the perfect cross between theory and practice that regular expressions are.&lt;p&gt;The changes for more in depth testing here are also very interesting, especially for a crate that I&amp;#x27;m sure if critical so a lot of the ecosystem, and I appreciate the writeup on such a deep dive topic.&lt;p&gt;Are regular expressions hard to read? Sometimes they can, especially if you haven&amp;#x27;t gone out of your way to take deep dives. Are they not perfect for a lot of parsing tasks? Sure, there are definitely things people shouldn&amp;#x27;t use regexs for that they do, like validating emails. At their core though, regular expressions are one of the most power dense tools we have in pretty much every language. The insane stuff you can get done (sometimes in a way that would be frowned upon) in so little time if just incredible.&lt;p&gt;I&amp;#x27;d love for there to be more content on regular expressions as well. Right now I&amp;#x27;m only familiar with one book that really does a great job (at a practical level), and that&amp;#x27;s Mastering Regular Expressions by Jeffrey Friedl. On a theory level, a lot of compiler books will talk about them to varying degrees. The Dragon Book has some good content on regular expressions at an implementation level too.&lt;p&gt;Does anyone have any other book recommendations for regular expressions?&lt;p&gt;And if BurntSushi or any other regular expression engine contributors see this, I really appreciate the effort y&amp;#x27;all put in to building such powerful software.</text></item></parent_chain><comment><author>jcranmer</author><text>&amp;gt; Are regular expressions hard to read? Sometimes they can, especially if you haven&amp;#x27;t gone out of your way to take deep dives. Are they not perfect for a lot of parsing tasks? Sure, there are definitely things people shouldn&amp;#x27;t use regexs for that they do, like validating emails. At their core though, regular expressions are one of the most power dense tools we have in pretty much every language. The insane stuff you can get done (sometimes in a way that would be frowned upon) in so little time if just incredible.&lt;p&gt;The real crowning use case for regular expressions (at least in terms of parsing-like tasks) is when you&amp;#x27;ve got formats with varied delimiters. So one format I was parsing this weekend was basically header:field1,field2,field3&amp;quot;data&amp;quot;hash (with a fixed number of fields). Or another format I work with is suite~split&amp;#x2F;test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 (most of the elements of which are optional). Regular expressions shine here; using primitives like split don&amp;#x27;t quite cut it in these formats.&lt;p&gt;And I think this also is a major cause of why regular expressions tend to become unreadable quickly. If you look at parsing via regular expressions as a whole, there&amp;#x27;s basically three things that are being jammed into one expression: what are the delimiters between fields, what is valid in each field, and which fields are optional. These are basically three separate concerns, but most regex APIs are absolutely terrible at letting you separate these concerns into separate steps (all you can do is provide the string that combines all of them).</text></comment>