Implementing Regular Expressions | Search for a title, author or keyword | ||||||||
Implementing Regular Expressions by Russ Cox. 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, labeled Thompson NFA, is used only in a few places, notably most implementations of awk and grep. The two approaches have wildly different performance characteristics: the Thompson NFA implementation is a million times faster than Perl. It may be hard to believe the graphs: perhaps you've used Perl, and it never seemed like regular expression matching was particularly slow. Most of the time, in fact, regular expression matching in Perl is fast enough. As the graph shows, though, it is possible to write so-called “pathological” regular expressions that Perl matches very very slowly. In contrast, there are no regular expressions that are pathological for the Thompson NFA implementation. "Why doesn't Perl use the Thompson NFA approach?” It can, it should, and that's what the rest of this article is about.
|
|||||||||
Implementing Regular Expressions | Disclaimer: this link points to content provided by other sites. |