I recently faced the problem of requiring negative lookbehinds in a regex engine that does not support them (Golang's Regexp package, RE2, and Hyperscan).
For example, say you want to match the string "def" except if it is preceeded by "abc". In PCRE using negative lookbehinds you could achieve this with the regex:
(?<!abc)def
But this will not work in all regex engines, so I needed an alternative.
I found this Stackoverflow answer by user Sebastian Proske. The approach is clever, but tricky to comprehend and write for long and complex negative lookbehinds. I will try to explain the general approach here, and then present a script to help use this approach for longer and more complex cases.
Continuing the example above, the approach works by having alternatives for each possible prefix that is not "abc". These alternatives are:
- The beginning of the string, or a character that is not "c", followed by "def"
- The beginning of the string, or a character that is not "b", followed by "cdef"
- The beginning of the string, or a character that is not "a", followed by "bcdef"
Written as a regex (line breaks and indentation for readability are not part of the regex):
(
(^|[^c])def
|
(^|[^b])cdef
|
(^|[^a])bcdef
)
We can extract the common suffix out:
(
(^|[^c])
|
(^|[^b])c
|
(^|[^a])bc
)
def
To support multiple alternative negative lookbehinds, such as both "abc" and "1234", which in PCRE syntax this can be written as "(?<!abc|1234)def", we can write:
(
(^|[^c4])
|
(^|[^b])c
|
(^|[^a])bc
|
(^|[^3])4
|
(^|[^2])34
|
(^|[^1])234
)
def
To support character classes in the negative lookbehinds, such as "[bB]", which in PCRE syntax can be written as "(?<!a[bB]c)def", we can write:
(
(^|[^c])
|
(^|[^bB])c
|
(^|[^a])[bB]c
)
def
For better equivalence to the negative lookbehinds, we can additionally use non-capturing groups:
(?:
(?:^|[^c])
|
(?:^|[^b])c
|
(?:^|[^a])bc
)
def
Here's a quick and dirty Python script to help construct regexes following this approach. The example input here is equivalent to "(?<!a[bB]c|1234)".
The script is also available to conveniently run in your browser on repl.it: https://repl.it/@allanrbo/regexnegativelookbehindalternative1
negativePrefixes = [
"a[bB]c",
"1234",
]
def removeDuplicateChars(s):
return "".join([c for i,c in enumerate(s) if c not in s[:i]])
def removeChars(s, charsToRemove):
return "".join([c for i,c in enumerate(s) if c not in charsToRemove])
# Split into arrays of strings. Each string is either a single char, or a char class.
negativePrefixesSplit = []
for np in negativePrefixes:
npSplit = []
curCc = ""
inCc = False
for c in np:
if c == "[":
inCc = True
elif c == "]":
npSplit.append(removeDuplicateChars(curCc))
curCc = ""
inCc = False
else:
if inCc:
if c in "-\\":
raise "Only really simply char classes are currently supported. No ranges or escapes, sorry."
curCc += c
else:
npSplit.append(c)
negativePrefixesSplit.append(npSplit)
allexprs = []
class Expr():
pass
suffixLength = 0
while True:
suffixes = []
for np in negativePrefixesSplit:
if suffixLength < len(np):
suffixes.append(np[len(np)-suffixLength-1:])
if len(suffixes) == 0:
break
exprs = []
for suffix in suffixes:
curChar = suffix[0]
remainder = suffix[1:]
expr = Expr()
expr.curChar = curChar
expr.remainder = remainder
exprs.append(expr)
# Is the remainder a subset of any other suffixes remainders?
for i in range(len(exprs)):
e1 = exprs[i]
for j in range(len(exprs)):
e2 = exprs[j]
isSubset = True
for k in range(len(e1.remainder)):
if not set(e1.remainder[k]).issubset(set(e2.remainder[k])):
isSubset = False
break
if isSubset:
if e1.curChar == e2.curChar:
e1.remainder = e2.remainder
continue
e1.curChar += e2.curChar
e1.curChar = removeDuplicateChars(e1.curChar)
for k in range(len(e1.remainder)):
if len(set(e2.remainder[k]) - set(e1.remainder[k])) > 0:
charsInCommon = "".join(set(e2.remainder[k]) & set(e1.remainder[k]))
e2.remainder[k] = removeChars(e2.remainder[k], charsInCommon)
# Remove duplicate expressions
exprsFiltered = []
for i in range(len(exprs)):
e1 = exprs[i]
alreadyExists = False
for j in range(len(exprs)):
if i == j:
break
e2 = exprs[j]
sameC = set(e1.curChar) == set(e2.curChar)
sameR = True
for k in range(len(e1.remainder)):
if set(e1.remainder[k]) != set(e2.remainder[k]):
sameR = False
break
if sameC and sameR:
alreadyExists = True
break
if not alreadyExists:
exprsFiltered.append(e1)
allexprs.extend(exprsFiltered)
suffixLength += 1
continue
out = "(?:\n"
for i in range(len(allexprs)):
e = allexprs[i]
out += ("(?:^|[^" + e.curChar + "])")
for c in e.remainder:
if len(c) > 1:
out += "[" + c + "]"
else:
out += c
if i != len(allexprs)-1:
out += "|"
out += "\n"
out += ")"
print("Human readable:")
print(out)
print()
print("Single line:")
print(out.replace("\n",""))
Example output:
Human readable: (?: (?:^|[^c4])| (?:^|[^bB])c| (?:^|[^3])4| (?:^|[^a])[bB]c| (?:^|[^2])34| (?:^|[^1])234 ) Single line: (?:(?:^|[^c4])|(?:^|[^bB])c|(?:^|[^3])4|(?:^|[^a])[bB]c|(?:^|[^2])34|(?:^|[^1])234)
