Regex: corrispondenza per esclusione, senza guardare al futuro: è possibile?

Question

In alcuni tipi di regex, le asserzioni [negative] di larghezza zero (look-ahead / look-behind) non sono supportate.

Ciò rende estremamente difficile (impossibile?) dichiarare un'esclusione. Ad esempio " ogni riga che non ha " pippo " su di esso " ;, in questo modo:

^((?!foo).)*$

È possibile ottenere la stessa cosa senza usare affatto il look-around (problemi di complessità e prestazioni messi da parte per il momento)?

Answer 1

AGGIORNAMENTO: non riesce " con due volte prima di oo " come @Ciantic sottolineato nei commenti .

---

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

NOTA: è molto più semplice negare una corrispondenza sul lato client invece di usare la regex sopra.

Il regex presuppone che ogni riga termina con un carattere newline se non lo è, quindi vedere le regex di C ++ e grep.

I programmi di esempio in Perl, Python, C ++ e grep danno tutti lo stesso 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])*
  #include <iostream>
  #include <string>
  #include <boost/regex.hpp>
  
  int main()
  {
    boost::regex re("^(f(o([^o]|$)|([^o]|$))|[^f])*
  $ grep "^\(f\(o\([^o]\|$\)\|\([^o]\|$\)\)\|[^f]\)*
  foo
  'foo'
  abdfoode
  abdfode
  abdfde
  abcde
  f
  
  fo
  foo
  fooo
  ofooa
  ofo
  ofoo
  quot; in.txt
  quot;);
    //NOTE: "|
  abdfode
  abdfde
  abcde
  f
  
  fo
  ofo
  quot;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;
  }
  quot;)
  for line in ifilter(re_not_foo.match, fileinput.input()):
      sys.stdout.write(line)
  

• c ++

  <*>

• grep

  <*>

File di esempio:

<*>

Output:

<*>

Answer 2

Ho affrontato questa domanda e preso il fatto che non c'era una regex pienamente funzionante come una sfida personale. Credo di essere riuscito a creare una regex che funziona per tutti gli input, a condizione che tu possa usare raggruppamento atomico / quantificatori possessivi .

Certo, non sono sicuro che ci siano tutti gli aromi che consentano il raggruppamento atomico ma non lo sguardo, ma la domanda si è posta se è possibile in regex dichiarare un'esclusione senza lo sguardo, e < em> è tecnicamente possibile:

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

Spiegazione:

\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, per qualsiasi motivo, è possibile utilizzare il raggruppamento atomico ma non quantificatori possessivi né lookaround, è possibile utilizzare:

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

Come altri sottolineano, tuttavia, è probabilmente più pratico negare una partita con altri mezzi.

Answer 3

Di solito puoi cercare foo e invertire il risultato della corrispondenza regex dal codice client.

Per un semplice esempio, supponiamo che tu voglia confermare che una stringa contiene solo determinati caratteri.

Potresti scrivere così:

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

e accetta un risultato true come valido, o in questo modo:

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

e accetta un risultato false come valido.

Naturalmente, questa non è sempre un'opzione: a volte devi solo inserire l'espressione in un file di configurazione o passarla a un altro programma, ad esempio. Ma vale la pena ricordare. Il tuo problema specifico, ad esempio, l'espressione è molto più semplice se puoi usare la negazione in questo modo.

Answer 4

Mi sono imbattuto in questa domanda cercando la mia soluzione di esclusione regex, dove sto cercando di escludere una sequenza all'interno della mia regex.

La mia reazione iniziale a questa situazione: Ad esempio "ogni riga che non ha" pippo " su di esso " era semplicemente usare l'opzione -v inverti senso di corrispondenza in grep.

grep -v foo

restituisce tutte le righe in un file che non corrispondono a "pippo"

È così semplice che ho la forte sensazione di aver letto male la tua domanda ....