(but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox rsc@swtch.com January 2007 This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep. The two approaches have wildly different performance characteristics: Time to match a? n a n against a n Let's use superscripts to denote string repetition, so that a? 3 a 3 is shorthand for a?a?a?aaa . The two graphs plot the time required by each approach to match the regular expression a? n a n against the string a n . Notice that Perl requires over sixty seconds to match a 29-character string. The other approach, labeled Thompson NFA for reasons that will be explained later, requires twenty microseconds to match the string. That's...