Regex: Matching por exclusão, sem olhar em frente - é possível?

Question

Em alguns sabores de regex, [negativo] afirmações de largura zero (look-ahead / look-atrás) não são suportados.

Isto torna extremamente difícil (impossível?) Para declarar uma exclusão. Por exemplo, "cada linha que não tem "foo" nele", assim:

^((?!foo).)*$

Pode a mesma coisa ser alcançado sem o uso de olhar-no todos (preocupações de complexidade e desempenho reservadas para o momento)?

Answer 1

UPDATE: Ele falha "com dois ff antes oo" como @ Ciantic apontou nos comentários.

---

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

NOTA: É muito mais fácil apenas para negar um jogo no lado do cliente em vez de usar o regex acima.

A expressão regular assume que cada um extremidades de linha com um caractere de nova linha, se não for, então, ver regexs de grep 's e C ++.

Os programas de amostra em Perl, Python, C ++, e grep todos dão o mesmo resultado.

• 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
  

arquivo de amostra:

foo
'foo'
abdfoode
abdfode
abdfde
abcde
f

fo
foo
fooo
ofooa
ofo
ofoo

Output:

abdfode
abdfde
abcde
f

fo
ofo

Answer 2

Veio este Pergunta e levou o fato de que não havia um regex totalmente funcional como um desafio pessoal. Eu acredito que eu consegui criar um regex que faz trabalho para todas as entradas - desde que você pode usar agrupamento atômica / possessivo quantificadores .

É claro, eu não tenho certeza se há são qualquer sabores que permitem agrupamento atômica, mas não LookAround, mas a pergunta se é possível em regex afirmar uma exclusão sem Lookaround, e < em> é tecnicamente possível:

\A(?:$|[^f]++|f++(?:[^o]|$)|(?:f++o)*+(?:[^o]|$))*\Z

Explicação:

\A                         #Start of string
(?:                        #Non-capturing group
    $                      #Consume end-of-line. We're not in foo-mode.
    |[^f]++                #Consume every non-'f'. We're not in foo-mode.
    |f++(?:[^o]|$)          #Enter foo-mode with an 'f'. Consume all 'f's, but only exit foo-mode if 'o' is not the next character. Thus, 'f' is valid but 'fo' is invalid.
    |(?:f++o)*+(?:[^o]|$)  #Enter foo-mode with an 'f'. Consume all 'f's, followed by a single 'o'. Repeat, since '(f+o)*' by itself cannot contain 'foo'. Only exit foo-mode if 'o' is not the next character following (f+o). Thus, 'fo' is valid but 'foo' is invalid.
)*                         #Repeat the non-capturing group
\Z                         #End of string. Note that this regex only works in flavours that can match $\Z

Se, por qualquer motivo, você pode usar agrupamento atômica, mas não quantificadores possessivo nem Lookaround, você pode usar:

\A(?:$|(?>[^f]+)|(?>f+)(?:[^o]|$)|(?>(?:(?>f+)o)*)(?:[^o]|$))*\Z

Como outros apontam, no entanto, é provavelmente mais prático simplesmente negar um jogo através de outros meios.

Answer 3

Você pode geralmente procuram foo e invertido o resultado da partida regex do código do cliente.

Para um exemplo simples, digamos que você deseja validar que uma string contém apenas alguns caracteres.

Você poderia escrever que como esta:

^[A-Za-z0-9.$-]*$

e aceitar um resultado true como válido, ou como isto:

[^A-Za-z0-9.$-]

e aceitar um resultado false como válido.

É claro que isso nem sempre é uma opção: às vezes você só tem que colocar a expressão em um arquivo de configuração ou passá-lo para outro programa, por exemplo. Mas vale a pena lembrar. O seu problema específico, por exemplo, a expressão é muito simples se você pode usar negação assim.

Answer 4

me deparei com esta questão procurando a minha própria solução exclusão regex, onde eu estou tentando excluir uma seqüência em minha regex.

A minha primeira reacção a esta situação: Por exemplo, "cada linha que não tem 'foo' nele" era simplesmente usar o sentido invertido -v da opção correspondente no grep

grep -v foo

este retorna todas as linhas em um arquivo que não correspondem 'foo'

É tão simples que eu tenho a sensação de forte Acabei descaracterizou sua pergunta ....