Regular Expression Matching Can Be Simple and Fast (2007)

Each state in the DFA corresponds to a list of states from the NFA.

In a sense, Thompson's NFA simulation is executing the equivalent DFA: each List corresponds to some DFA state, and the step function is computing, given a list and a next character, the next DFA state to enter. Thompson's algorithm simulates the DFA by reconstructing each DFA state as it is needed. Rather than throw away this work after each step, we could cache the Lists in spare memory, avoiding the cost of repeating the computation in the future and essentially computing the equivalent DFA as it is needed. This section presents the implementation of such an approach. Starting with the NFA implementation from the previous section, we need to add less than 100 lines to build a DFA implementation.

To implement the cache, we first introduce a new data type that represents a DFA state:

struct DState { List l; DState *next[256]; DState *left; DState *right; };

A DState is the cached copy of the list l. The array next contains pointers to the next state for each possible input character: if the current state is d and the next input character is c, then d->next[c] is the next state. If d->next[c] is null, then the next state has not been computed yet. Nextstate computes, records, and returns the next state for a given state and character.

The regular expression match follows d->next[c] repeatedly, calling nextstate to compute new states as needed.

int match(DState *start, char *s) { int c; DState *d, *next;

d = start; for(; *s; s++){ c = *s & 0xFF; if((next = d->next[c]) == NULL) next = nextstate(d, c); d = next; } return ismatch(&d->l); }

All the DStates that have been computed need to be saved in a structure that lets us look up a DState by its List. To do this, we arrange them in a binary tree using the sorted List as the key. The dstate function returns the DState for a given List, allocating one if necessary:

DState* dstate(List *l) { int i; DState **dp, *d; static DState *alldstates;

qsort(l->s, l->n, sizeof l->s[0], ptrcmp);

/* look in tree for existing DState */ dp = &alldstates; while((d = *dp) != NULL){ i = listcmp(l, &d->l); if(i < 0) dp = &d->left; else if(i > 0) dp = &d->right; else return d; }

/* allocate, initialize new DState / d = malloc(sizeof d + l->nsizeof l->s[0]); memset(d, 0, sizeof d); d->l.s = (State)(d+1); memmove(d->l.s, l->s, l->n*sizeof l->s[0]); d->l.n = l->n;

/* insert in tree */ *dp = d; return d; }

Nextstate runs the NFA step and returns the corresponding DState:

DState* nextstate(DState *d, int c) { step(&d->l, c, &l1); return d->next[c] = dstate(&l1); }

Finally, the DFA's start state is the DState corresponding to the NFA's start list:

DState* startdstate(State *start) { return dstate(startlist(start, &l1)); }

(As in the NFA simulation, l1 is a preallocated List.)

The DStates correspond to DFA states, but the DFA is only built as needed: if a DFA state has not been encountered during the search, it does not yet exist in the cache. An alternative would be to compute the entire DFA at once. Doing so would make match a little faster by removing the conditional branch, but at the cost of increased startup time and memory use.

One might also worry about bounding the amount of memory used by the on-the-fly DFA construction. Since the DStates are only a cache of the step function, the implementation of dstate could choose to throw away the entire DFA so far if the cache grew too large. This cache replacement policy only requires a few extra lines of code in dstate and in nextstate, plus around 50 lines of code for memory management. An implementation is available online. (Awk uses a similar limited-size cache strategy, with a fixed limit of 32 cached states; this explains the discontinuity in its performance at n=28 in the graph above.)

NFAs derived from regular expressions tend to exhibit good locality: they visit the same states and follow the same transition arrows over and over when run on most texts. This makes the caching worthwhile: the first time an arrow is followed, the next state must be computed as in the NFA simulation, but future traversals of the arrow are just a single memory access. Real DFA-based implementations can make use of additional optimizations to run even faster. A companion article (not yet written) will explore DFA-based regular expression implementations in more detail.

Regular expression usage in real programs is somewhat more complicated than what the regular expression implementations described above can handle. This section briefly describes the common complications; full treatment of any of these is beyond the scope of this introductory article.

Character classes. A character class, whether [0-9] or \w or . (dot), is just a concise representation of an alternation. Character classes can be expanded into alternations during compilation, though it is more efficient to add a new kind of NFA node to represent them explicitly. POSIX defines special character classes like [[:upper:]] that change meaning depending on the current locale, but the hard part of accommodating these is determining their meaning, not encoding that meaning into an NFA.

Escape sequences. Real regular expression syntaxes need to handle escape sequences, both as a way to match metacharacters ((, ), \, etc.) and to specify otherwise difficult-to-type characters such as \n.

Counted repetition. Many regular expression implementations provide a counted repetition operator {n} to match exactly n strings matching a pattern; {n,m} to match at least n but no more than m; and {n,} to match n or more. A recursive backtracking implementation can implement counted repetition using a loop; an NFA or DFA-based implementation must expand the repetition: e{3} expands to eee; e{3,5} expands to eeee?e?, and e{3,} expands to eee+.

Submatch extraction. When regular expressions are used for splitting or parsing strings, it is useful to be able to find out which sections of the input string were matched by each subexpression. After a regular expression like ([0-9]+-[0-9]+-[0-9]+) ([0-9]+:[0-9]+) matches a string (say a date and time), many regular expression engines make the text matched by each parenthesized expression available. For example, one might write in Perl:

if(/([0-9]+-[0-9]+-[0-9]+) ([0-9]+:[0-9]+)/){ print "date: $1, time: $2\n"; }

The extraction of submatch boundaries has been mostly ignored by computer science theorists, and it is perhaps the most compelling argument for using recursive backtracking. However, Thompson-style algorithms can be adapted to track submatch boundaries without giving up efficient performance. The Eighth Edition Unix regexp(3) library implemented such an algorithm as early as 1985, though as explained below, it was not very widely used or even noticed.

Unanchored matches. This article has assumed that regular expressions are matched against an entire input string. In practice, one often wishes to find a substring of the input that matches the regular expression. Unix tools traditionally return the longest matching substring that starts at the leftmost possible point in the input. An unanchored search for e is a special case of submatch extraction: it is like searching for .(e). where the first .* is constrained to match as short a string as possible.

Non-greedy operators. In traditional Unix regular expressions, the repetition operators ?, *, and + are defined to match as much of the string as possible while still allowing the entire regular expression to match: when matching (.+)(.+) against abcd, the first (.+) will match abc, and the second will match d. These operators are now called greedy. Perl introduced ??, *?, and +? as non-greedy versions, which match as little of the string as possible while preserving the overall match: when matching (.+?)(.+?) against abcd, the first (.+?) will match only a, and the second will match bcd. By definition, whether an operator is greedy cannot affect whether a regular expression matches a particular string as a whole; it only affects the choice of submatch boundaries. The backtracking algorithm admits a simple implementation of non-greedy operators: try the shorter match before the longer one. For example, in a standard backtracking implementation, e? first tries using e and then tries not using it; e?? uses the other order. The submatch-tracking variants of Thompson's algorithm can be adapted to accommodate non-greedy operators.

Assertions. The traditional regular expression metacharacters ^ and $ can be viewed as assertions about the text around them: ^ asserts that the previous character is a newline (or the beginning of the string), while $ asserts that the next character is a newline (or the end of the string). Perl added more assertions, like the word boundary \b, which asserts that the previous character is alphanumeric but the next is not, or vice versa. Perl also generalized the idea to arbitrary conditions called lookahead assertions: (?=re) asserts that the text after the current input position matches re, but does not actually advance the input position; (?!re) is similar but asserts that the text does not match re. The lookbehind assertions (?<=re) and (?<!re) are similar but make assertions about the text before the current input position. Simple assertions like ^, $, and \b are easy to accommodate in an NFA, delaying the match one byte for forward assertions. The generalized assertions are harder to accommodate but in principle could be encoded in the NFA.

Backreferences. As mentioned earlier, no one knows how to implement regular expressions with backreferences efficiently, though no one can prove that it's impossible either. (Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.) The simplest, most effective strategy for backreferences, taken by the original awk and egrep, is not to implement them. This strategy is no longer practical: users have come to rely on backreferences for at least occasional use, and backreferences are part of the POSIX standard for regular expressions. Even so, it would be reasonable to use Thompson's NFA simulation for most regular expressions, and only bring out backtracking when it is needed. A particularly clever implementation could combine the two, resorting to backtracking only to accommodate the backreferences.

Backtracking with memoization. Perl's approach of using memoization to avoid exponential blowup during backtracking when possible is a good one. At least in theory, it should make Perl's regular expressions behave more like an NFA and less like backtracking. Memoization does not completely solve the problem, though: the memoization itself requires a memory footprint roughly equal to the size of the text times the size of the regular expression. Memoization also does not address the issue of the stack space used by backtracking, which is linear in the size of the text: matching long strings typically causes a backtracking implementation to run out of stack space:

$ perl -e '("a" x 100000) =~ /^(ab?)*$/;' Segmentation fault (core dumped) $

Character sets. Modern regular expression implementations must deal with large non-ASCII character sets such as Unicode. The Plan 9 regular expression library incorporates Unicode by running an NFA with a single Unicode character as the input character for each step. That library separates the running of the NFA from decoding the input, so that the same regular expression matching code is used for both UTF-8 and wide-character inputs.

Michael Rabin and Dana Scott introduced non-deterministic finite automata and the concept of non-determinism in 1959 [7], showing that NFAs can be simulated by (potentially much larger) DFAs in which each DFA state corresponds to a set of NFA states. (Th