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.
The syntax for positive lookahead is
). So for example
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.
The syntax for negative lookahead is
). So for example
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.
The syntax for positive lookbehind is
). So, for example,
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.
The syntax for negative lookbehind is
). So, for example,
u, but only if it is not preceded by
q. So it would match the
umbrella and the
doubt, but not the
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.