Regex: Matching by exclusion, without look-ahead - is it possible?

regex, regex-negation

Solution

UPDATE: It fails "with two ff before oo" as @Ciantic pointed out in the comments.

^(f(o[^o]|[^o])|[^f])*$

NOTE: It is much much easier just to negate a match on the client side instead of using the above regex.

The regex assumes that each line ends with a newline char if it is not then see C++'s and grep's regexs.

Sample programs in Perl, Python, C++, and `grep` all give the same output.

perl

#!/usr/bin/perl -wn
print if /^(f(o[^o]|[^o])|[^f])*$/;

python

#!/usr/bin/env python
import fileinput, re, sys
from itertools import ifilter

re_not_foo = re.compile(r"^(f(o[^o]|[^o])|[^f])*$")
for line in ifilter(re_not_foo.match, fileinput.input()):
    sys.stdout.write(line)

c++

#include <iostream>
#include <string>
#include <boost/regex.hpp>

int main()
{
  boost::regex re("^(f(o([^o]|$)|([^o]|$))|[^f])*$");
  //NOTE: "|$"s are there due to `getline()` strips newline char

  std::string line;
  while (std::getline(std::cin, line)) 
    if (boost::regex_match(line, re))
      std::cout << line << std::endl;
}

grep

$ grep "^\(f\(o\([^o]\|$\)\|\([^o]\|$\)\)\|[^f]\)*$" in.txt

Sample file:

foo
'foo'
abdfoode
abdfode
abdfde
abcde
f

fo
foo
fooo
ofooa
ofo
ofoo

Output:

abdfode
abdfde
abcde
f

fo
ofo

Problem

In some regex flavors, [negative] zero-width assertions (look-ahead/look-behind) are not supported. This makes it extremely difficult (impossible?) to state an exclusion. For example "every line that does not have "foo" on it", like this: ``` ^((?!foo).)*$ ``` Can the same thing be achieved without using look-around at all (complexity and performance concerns set aside for the moment)?

Original source