Regular expressions are one of computer science's shining examples of the benefits of good computer science theory. They were originally developed by theorists as a way to describe infinite sets, but Ken Thompson introduced them to programmers as a way to describe text patterns in his implementation of the text editor QED for CTSS. Dennis Ritchie followed suit in his own implementation of QED, for GE-TSS. “We’ve built a new regular expression engine, called “RE2,” which’s based on automata theory and guarantees that searches complete in linear time with respect to the size of the input and in a fixed amount of stack space. Today, we released RE2 as an open source project. It's a mostly drop-in replacement for PCRE's C++ bindings and is available under a BSD-style license. See RE2 project page for details,” noted Google.