How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

Question

I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively simple for basic regular expressions. However I can't seem to wrap my head around how to simulate backreferences, lookaheads, and lookbehinds.

From what I read in the purple dragon book I understood that to simulate a lookahead $r/s$ where the regular expression $r$ is matched if and only if the match is followed by a match of the regular expression $s$, you create a non-deterministic finite state automaton in which $/$ is replaced by $\varepsilon$. Is it possible to create a deterministic finite state automaton that does the same?

What about simulating negative lookaheads and lookbehinds? I would really appreciate it if you would link me to a resource which describes how to do this in detail.

Answer 1

First of all, backreferences can not be simulated by finite automata as they allow you to describe non-regular languages. For example, ([ab]^*)\1 matches $\{ww \mid w \in \{a,b\}^*\}$, which is not even context-free.

Look-ahead and look-behind are nothing special in the world of finite automata as we only match whole inputs here. Therefore, the special semantic of "just check but don't consume" is meaningless; you just concatenate and/or intersect checking and consuming expressions and use the resulting automata. The idea is to check the look-ahead or look-behind expressions while you "consume" the input and store the result in a state.

When implementing regexps, you want to run the input through an automaton and get back start and end indices of matches. That is a very different task, so there is not really a construction for finite automata. You build your automaton as if the look-ahead or look-behind expression were consuming, and change your index storing resp. reporting accordingly.

Take, for instance, look-behinds. We can mimic the regexp semantics by executing the checking regexp concurrently to the implicitly consuming "match-all" regexp. only from states where the look-behind expression's automaton is in a final state can the automaton of the guarded expression be entered. For example, the regexp /(?=c)[ab]+/ (assuming $\{a,b,c\}$ is the full alphabet) -- note that it translates to the regular expression $\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$ -- could be matched by

^[source]

and you would have to

• store the current index as $i$ whenever you enter $q_2$ (initially or from $q_2$) and
• report a (maximum) match from $i$ to the current index ($-1$) whenever you hit (leave) $q_2$.

Note how the left part of the automaton is the parallel automaton of the canonical automata for [abc]* and c (iterated), respectively.

Look-aheads can be dealt with similarly; you have to remember the index $i$ when you enter the "main" automaton, the index $j$ when you leave the main automaton and enter the look-ahead automaton and report a match from $i$ to $j$ only when you hit the look-ahead automaton's final state.

Note that non-determinism is inherent to this: main and look-ahead/-behind automaton might overlap, so you have to store all transitions between them in order to report the matching ones later, or backtrack.

Answer 2

The authoritative reference on the pragmatic issues behind implementing regex engines is a series of three blog posts by Russ Cox. As described there, since backreferences make your language non-regular, they are implemented using backtracking.

Lookaheads and lookbehinds, like many features of of regex pattern matching engines, don't quite fit into the paradigm of deciding whether or not a string is a member of a language or not. Rather with regexes we are usually searching for substrings within a larger string. The "matches" are substrings that are members of the language, and the return value is the beginning and end points of the substring within the larger string.

The point of lookaheads and lookbehinds is not so much to introduce the ability to match non-regular languages, but rather to adjust where the engine reports the begin and end points of the matched substring.

I'm relying on the description at http://www.regular-expressions.info/lookaround.html. The regex engines that support this feature (Perl, TCL, Python, Ruby, ...) all seem to be based on backtracking (i.e., they support a much larger set of languages than just the regular languages). They seem to be implementing this feature as a relatively "simple" extension of backtracking, rather than trying to construct real finite automata to perform the task.

Positive Lookahead

The syntax for positive lookahead is (?=regex). So for example q(?=u) matches q only if it is followed by u, but does not match the u. I imagine they implement this with a variation on backtracking. Create a FSM for the expression before the positive lookahead. When that matches remember where it ended and start a new FSM that represents the expression inside the positive lookahead. If that matches then you have a "match", but the match "ends" just before the position where the positive lookahead match began.

The only part of this that would be hard without backtracking is that you need to remember the point in the input where the lookahead starts and move your input tape back to this position after you are done with the match.

Negative Lookahead

The syntax for negative lookahead is (?!regex). So for example q(?!u) matches q only if it is not followed by u. This could be either a q followed by some other character, or a q at the very end of the string. I imagine this is implemented by creating an NFA for the lookahead expression, then succeeding only if the NFA fails to match the subsequent string.

If you want to do it without relying on backtracking you could negate the NFA of the lookahead expression, then treat it the same way you treat positive lookahead.

Positive Lookbehind

The syntax for positive lookbehind is (?<=regex). So, for example, (?<=q)u matches u, but only if it is preceded by q, but does not match the q. Apparently this is implemented as a complete hack where the regex engine actually backs up $n$ characters and tries to match regex against those $n$ characters. This means that regex must be such that it only matches strings of length $n$.

You might be able to implement this without backtracking by taking the intersection of "string that ends with regex" with whatever part of the regex that comes before the lookbehind operator. This is going to be tricky though, because the lookbehind regex might need to look further back than the current beginning of the input.

Negative Lookbehind

The syntax for negative lookbehind is (?<!regex). So, for example, (?<!q)u matches u, but only if it is not preceded by q. So it would match the u in umbrella and the u in doubt, but not the u in quick. Again, this seems to be done by calculating the length of regex, backing up that many characters, testing for the match with regex, but now failing the whole match if the lookbehind matches.

You might be able to implement this without backtracking by taking the negation of regex and then doing the same as you would do for positive lookbehind.

Answer 3

At least for backreferences, this is not possible. For example, the regex (.*)\1 represents a language that is not regular. What that means is that it's impossible to create a finite automaton (deterministic or not) that would recognize this language. If you want to prove this formally, you can use the pumping lemma.

Answer 4

I've been looking into this myself, and you should be able to implement lookahead using an Alternating Finite Automaton. When you encounter lookahead, you nondeterministically run both the lookahead and the remainder of the expression, accepting only if both paths accept. You can convert an AFA to an NFA with reasonable blowup (and thus to a DFA), although I haven't verified that the obvious construction plays nicely with capture groups.

Fixed-width lookbehind should be perfectly possible without backtracking. Let n be the width. Starting from the point in your NFA where the lookbehind began, you'd split out states looking backward so that every path into the lookbehind ended with n characters worth of states that only went into the lookbehind. Then, add lookahead to the beginning of those states (and immediately compile the subgraph from AFA to NFA if desired).

Backreferences are, as others have mentioned, not regular, so they cannot be implemented by a finite automaton. In fact, they're NP-complete. In the implementation I'm working on, quick yes/no matching is paramount, so I chose not to implement backreferences at all.