What's the use of Deterministic Regular Expressions?

What are most interesting (crazy) use cases of regexes (regular expressions)?

• I recently read this article http://cory.li/battlecode-intro/ and was really impressed with the way regex were used to encode Dijkstra's algorithm. That got me wondering about people who have use regexes in interesting places.

• Answer:

  I don't know if this is crazy per se, but many people probably don't realize that Emacs's syntax highlighting and indentation are implemented almost exclusively with regexes. And yet they're surprisingly good! Syntax highlighting with regexes is, for the most part, not much of a surprise. Most languages have a relatively sane lexical syntax to simplify lexing, so they're almost perfectly regular already. And since regexes in practice are actually more powerful¹ than academic "regular expressions" (ie they can match more than just regular languages), it's easy to cover most of the parts that are not regular too. Indentation, on the other hand, is quite a difficult problem, with or without regexes. Steve Yegge, who wrote JS2-mode which does not use regexes, sums it up well: See, I thought that since I had gone to all the thousands of lines of  effort to produce a strongly-typed AST (abstract syntax tree) for  JavaScript, it should therefore be really easy to do indentation.  The  AST tells me exactly what the syntax is at any given point in the  buffer, so how hard could it be? It turns out to be, oh, about fifty times harder than incremental parsing.  Surprise! (From http://steve-yegge.blogspot.com/2008/03/js2-mode-new-javascript-mode-for-emacs.html) So the fact that Emacs does a really good job without a full AST—just with regexes—is pretty impressive! There's also some very interesting and, serendipitously, very useful emergent behavior: indentation in Emacs is local. It is only based on the line immediately above. Now, sometimes, this is actually a problem, but in my experience it works well enough something like 99.99% of the time (ie I have an indentation problem at most every ~10k lines). More importantly, though, it means Emacs indentation adapts to my code! In particular, there are often weird language constructs and patterns that I indent differently from the rest of the code. With Emacs, I just need to do the first line of a block like this manually, and everything else lines up automatically—it just follows the lead of that first line. On the other hand, a global system like Eclipse insists or reindenting everything according to its built-in styling guide; this means I have to fiddle with the tool to add an exception for whatever weird one-off pattern I want to indent properly! (Or just give up and settle for the default style even if it ends up harder to read.) I take advantage of this far more often than I run into limitations of Emacs's indentation, so I think it's a net benefit. It also means that Emacs gracefully handles files that are not completely well-formatted: it can indent properly as soon as you have a single valid line, ignoring everything that comes before (or after!) it. Both of these features are particularly useful when working with embedded DSLs in languages with flexible syntaxes like Scheme or Haskell. Often, while the DSL is actually made up of normal Scheme/Haskell code, its meaning and conventions are different; Emacs ends up adapting to these new conventions by itself just thanks to this locality property.