regex - ingles - some any much many a lot of a few a little explicacion

¿Por qué no se pueden usar cuantificadores de repetición en una visión de ancho cero detrás de las aserciones?

Question

Siempre tuve la impresión de que no se podían usar cuantificadores de repetición en aserciones de ancho cero (Expresiones regulares compatibles con Perl [PCRE]). Sin embargo, recientemente se me ocurrió que puede usarlos en aseveraciones anticipadas.

Así que mi pregunta es:

¿Cómo funciona el motor de expresiones regulares de PCRE cuando se realiza una búsqueda con vista de atrás de ancho cero que impide el uso de cuantificadores de repetición?

Aquí hay un ejemplo simple de un PCRE en R:

# Our string
x <- ''MaaabcccM''

##  Does it contain a ''b'', preceeded by an ''a'' and followed by zero or more ''c'',
##  then an ''M''? 
grepl( ''(?<=a)b(?=c*M)'' , x , perl=T )
# [1] TRUE

##  Does it contain a ''b'': (1) preceeded by an ''M'' and then zero or more ''a'' and 
##                         (2) followed by zero or more ''c'' then an ''M''?
grepl( ''(?<=Ma*)b(?=c*M)'' , x , perl = TRUE )
# Error in grepl("(?<=Ma*)b(?=c*M)", x, perl = TRUE) : 
#   invalid regular expression ''(?<M=a*)b(?=c*M)''
# In addition: Warning message:
# In grepl("(?<=Ma*)b(?=c*M)", x, perl = TRUE) : PCRE pattern compilation error
#         ''lookbehind assertion is not fixed length''
#         at '')b(?=c*M)''

Answer 1

La página del manual de pcrepattern documenta la restricción de que las aserciones deben ser de ancho fijo o de varios patrones de ancho fijo separados por | ''s, y luego explica que esto se debe a que:

Para cada alternativa, la implementación de aserciones de Mirar por detrás es mover temporalmente la posición actual hacia atrás por la longitud fija y luego tratar de coincidir. Si no hay suficientes caracteres antes de la posición actual, la aserción falla.

No estoy seguro de por qué lo hacen de esta manera, pero supongo que pasaron mucho tiempo escribiendo un buen motor de emparejamiento de RE que sigue adelante, y no querían duplicar todo ese esfuerzo para escribir otro que corre hacia atras El enfoque obvio sería correr sobre la cadena hacia atrás, eso es fácil, mientras se empareja una versión "inversa" de su afirmación detrás de la mirada. Es posible revertir un RE "real" (compatible con DFA) - el reverso de un lenguaje regular es un lenguaje regular - pero los RE "extendidos" de PCRE están completos en IIRC, y puede que ni siquiera sea posible voltear uno a otro correr hacia atrás de manera eficiente en general. E incluso si lo fuera, probablemente a nadie le haya importado lo suficiente como para molestar. Después de todo, las afirmaciones de mirar por detrás son una característica bastante menor en el gran esquema de las cosas.

Answer 2

La respuesta definitiva a esta pregunta se encuentra en el código del motor, y en la parte inferior de la respuesta podrá sumergirse en la sección del código del motor PCRE responsable de garantizar una longitud fija en el aspecto, si está interesado Conociendo los más finos detalles. Mientras tanto, vamos a acercarnos gradualmente a la pregunta desde niveles más altos.

Mirada de ancho variable detrás de Mirada de ancho infinito detrás de

En primer lugar, una rápida aclaración sobre los términos. Un número creciente de motores (incluido el PCRE) admite alguna forma de apariencia de ancho variable, donde la variación se encuentra dentro de un rango determinado, por ejemplo:

• el motor sabe que el ancho de lo que precede debe tener entre 5 y diez caracteres (no se admite en PCRE)
• el motor sabe que el ancho de lo que precede debe ser de 5 o diez caracteres (compatible con PCRE)

Por el contrario, en el aspecto de ancho infinito, puede usar tokens cuantificados como a+

Motores que soportan la apariencia de ancho infinito

Para el registro, estos motores soportan una mirada infinita detrás de:

• .NET (C #, VB.NET etc.)
• Módulo de regex Matthew Barnett para Python
• JGSoft (EditPad, etc.; No disponible en un lenguaje de programación).

Por lo que yo sé, ellos son los únicos.

Mirada variable detrás de PCRE

En PCRE, la sección más relevante en la documentación es esta:

El contenido de una aserción detrás de la vista está restringido de modo que todas las cadenas que coincida deben tener una longitud fija. Sin embargo, si hay varias alternativas de nivel superior, no todas tienen que tener la misma longitud fija.

Por lo tanto, el siguiente aspecto es válido:

(?<=a |big )cat

Sin embargo, ninguno de estos son:

• (?<=a/s?|big )cat (los lados de la alternancia no tienen un ancho fijo)
• (?<=@{1,10})cat (ancho variable)
• (?<=/R)cat ( /R no tiene un ancho fijo, ya que puede coincidir con /n , /r/n , etc.)
• (?<=/X)cat ( /X no tiene un ancho fijo, ya que un clúster de grafema Unicode puede contener un número variable de bytes).
• (?<=a+)cat (claramente no arreglado)

Mire detrás de la igualación de ancho cero pero la repetición infinita

Ahora considera esto:

(?<=(?=@+))(cat#+)

A primera vista, se trata de un aspecto de ancho fijo, porque solo puede encontrar una coincidencia de ancho cero (definida por el lookahead (?=@++) ). ¿Es ese un truco para sortear la mirada infinita detrás de la limitación?

No. PCRE se ahogará con esto. A pesar de que el contenido de la mirada detrás es de ancho cero, PCRE no permitirá una repetición infinita en la mirada detrás de. En cualquier sitio. Cuando la documentación dice que todas las cadenas que coincide deben tener una longitud fija, realmente debería ser:

Todas las cadenas que coincida con cualquiera de sus componentes deben tener una longitud fija.

Soluciones: La vida sin mirada infinita detrás de

En PCRE, las dos soluciones principales a problemas en los que una mirada infinita puede ayudar son /K y capturar Grupos.

Solución # 1: /K

La afirmación de /K le dice al motor que descarte lo que coincidió tan lejos de la partida final que devuelve.

Supongamos que desea (?<=@+)cat#+ , que no es legal en PCRE. En su lugar, puede utilizar:

@+/Kcat#+

Solución # 2: Grupos de captura

Otra forma de proceder es hacer coincidir lo que hubiera colocado en una mirada detrás, y capturar el contenido de interés en un grupo de captura. A continuación, recupera la coincidencia del grupo de captura.

Por ejemplo, en lugar del (?<=@+)cat#+ ilegal (?<=@+)cat#+ , Usaría:

@+(cat#+)

En R, esto podría verse así:

matches <- regexpr("@+(cat#+)", subject, perl=TRUE);
result <- attr(matches, "capture.start")[,1]
attr(result, "match.length") <- attr(matches, "capture.length")[,1]
regmatches(subject, result)

En idiomas que no admiten /K , esta es a menudo la única solución.

Partes internas del motor: ¿Qué dice el código PCRE?

La respuesta definitiva se encuentra en pcre_compile.c . Si examinas el bloque de código que comienza con este comentario:

Si mira detrás, verifique que esta rama coincida con una cadena de longitud fija

Usted encuentra que el trabajo de gruñido se realiza mediante la función find_fixedlength() .

Lo reproduzco aquí para cualquier persona que quiera profundizar en más detalles.

static int
find_fixedlength(pcre_uchar *code, BOOL utf, BOOL atend, compile_data *cd)
{
int length = -1;

register int branchlength = 0;
register pcre_uchar *cc = code + 1 + LINK_SIZE;

/* Scan along the opcodes for this branch. If we get to the end of the
branch, check the length against that of the other branches. */

for (;;)
  {
  int d;
  pcre_uchar *ce, *cs;
  register pcre_uchar op = *cc;

  switch (op)
    {
    /* We only need to continue for OP_CBRA (normal capturing bracket) and
    OP_BRA (normal non-capturing bracket) because the other variants of these
    opcodes are all concerned with unlimited repeated groups, which of course
    are not of fixed length. */

    case OP_CBRA:
    case OP_BRA:
    case OP_ONCE:
    case OP_ONCE_NC:
    case OP_COND:
    d = find_fixedlength(cc + ((op == OP_CBRA)? IMM2_SIZE : 0), utf, atend, cd);
    if (d < 0) return d;
    branchlength += d;
    do cc += GET(cc, 1); while (*cc == OP_ALT);
    cc += 1 + LINK_SIZE;
    break;

    /* Reached end of a branch; if it''s a ket it is the end of a nested call.
    If it''s ALT it is an alternation in a nested call. An ACCEPT is effectively
    an ALT. If it is END it''s the end of the outer call. All can be handled by
    the same code. Note that we must not include the OP_KETRxxx opcodes here,
    because they all imply an unlimited repeat. */

    case OP_ALT:
    case OP_KET:
    case OP_END:
    case OP_ACCEPT:
    case OP_ASSERT_ACCEPT:
    if (length < 0) length = branchlength;
      else if (length != branchlength) return -1;
    if (*cc != OP_ALT) return length;
    cc += 1 + LINK_SIZE;
    branchlength = 0;
    break;

    /* A true recursion implies not fixed length, but a subroutine call may
    be OK. If the subroutine is a forward reference, we can''t deal with
    it until the end of the pattern, so return -3. */

    case OP_RECURSE:
    if (!atend) return -3;
    cs = ce = (pcre_uchar *)cd->start_code + GET(cc, 1);  /* Start subpattern */
    do ce += GET(ce, 1); while (*ce == OP_ALT);           /* End subpattern */
    if (cc > cs && cc < ce) return -1;                    /* Recursion */
    d = find_fixedlength(cs + IMM2_SIZE, utf, atend, cd);
    if (d < 0) return d;
    branchlength += d;
    cc += 1 + LINK_SIZE;
    break;

    /* Skip over assertive subpatterns */

    case OP_ASSERT:
    case OP_ASSERT_NOT:
    case OP_ASSERTBACK:
    case OP_ASSERTBACK_NOT:
    do cc += GET(cc, 1); while (*cc == OP_ALT);
    cc += PRIV(OP_lengths)[*cc];
    break;

    /* Skip over things that don''t match chars */

    case OP_MARK:
    case OP_PRUNE_ARG:
    case OP_SKIP_ARG:
    case OP_THEN_ARG:
    cc += cc[1] + PRIV(OP_lengths)[*cc];
    break;

    case OP_CALLOUT:
    case OP_CIRC:
    case OP_CIRCM:
    case OP_CLOSE:
    case OP_COMMIT:
    case OP_CREF:
    case OP_DEF:
    case OP_DNCREF:
    case OP_DNRREF:
    case OP_DOLL:
    case OP_DOLLM:
    case OP_EOD:
    case OP_EODN:
    case OP_FAIL:
    case OP_NOT_WORD_BOUNDARY:
    case OP_PRUNE:
    case OP_REVERSE:
    case OP_RREF:
    case OP_SET_SOM:
    case OP_SKIP:
    case OP_SOD:
    case OP_SOM:
    case OP_THEN:
    case OP_WORD_BOUNDARY:
    cc += PRIV(OP_lengths)[*cc];
    break;

    /* Handle literal characters */

    case OP_CHAR:
    case OP_CHARI:
    case OP_NOT:
    case OP_NOTI:
    branchlength++;
    cc += 2;
#ifdef SUPPORT_UTF
    if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
#endif
    break;

    /* Handle exact repetitions. The count is already in characters, but we
    need to skip over a multibyte character in UTF8 mode.  */

    case OP_EXACT:
    case OP_EXACTI:
    case OP_NOTEXACT:
    case OP_NOTEXACTI:
    branchlength += (int)GET2(cc,1);
    cc += 2 + IMM2_SIZE;
#ifdef SUPPORT_UTF
    if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
#endif
    break;

    case OP_TYPEEXACT:
    branchlength += GET2(cc,1);
    if (cc[1 + IMM2_SIZE] == OP_PROP || cc[1 + IMM2_SIZE] == OP_NOTPROP)
      cc += 2;
    cc += 1 + IMM2_SIZE + 1;
    break;

    /* Handle single-char matchers */

    case OP_PROP:
    case OP_NOTPROP:
    cc += 2;
    /* Fall through */

    case OP_HSPACE:
    case OP_VSPACE:
    case OP_NOT_HSPACE:
    case OP_NOT_VSPACE:
    case OP_NOT_DIGIT:
    case OP_DIGIT:
    case OP_NOT_WHITESPACE:
    case OP_WHITESPACE:
    case OP_NOT_WORDCHAR:
    case OP_WORDCHAR:
    case OP_ANY:
    case OP_ALLANY:
    branchlength++;
    cc++;
    break;

    /* The single-byte matcher isn''t allowed. This only happens in UTF-8 mode;
    otherwise /C is coded as OP_ALLANY. */

    case OP_ANYBYTE:
    return -2;

    /* Check a class for variable quantification */

    case OP_CLASS:
    case OP_NCLASS:
#if defined SUPPORT_UTF || defined COMPILE_PCRE16 || defined COMPILE_PCRE32
    case OP_XCLASS:
    /* The original code caused an unsigned overflow in 64 bit systems,
    so now we use a conditional statement. */
    if (op == OP_XCLASS)
      cc += GET(cc, 1);
    else
      cc += PRIV(OP_lengths)[OP_CLASS];
#else
    cc += PRIV(OP_lengths)[OP_CLASS];
#endif

    switch (*cc)
      {
      case OP_CRSTAR:
      case OP_CRMINSTAR:
      case OP_CRPLUS:
      case OP_CRMINPLUS:
      case OP_CRQUERY:
      case OP_CRMINQUERY:
      case OP_CRPOSSTAR:
      case OP_CRPOSPLUS:
      case OP_CRPOSQUERY:
      return -1;

      case OP_CRRANGE:
      case OP_CRMINRANGE:
      case OP_CRPOSRANGE:
      if (GET2(cc,1) != GET2(cc,1+IMM2_SIZE)) return -1;
      branchlength += (int)GET2(cc,1);
      cc += 1 + 2 * IMM2_SIZE;
      break;

      default:
      branchlength++;
      }
    break;

    /* Anything else is variable length */

    case OP_ANYNL:
    case OP_BRAMINZERO:
    case OP_BRAPOS:
    case OP_BRAPOSZERO:
    case OP_BRAZERO:
    case OP_CBRAPOS:
    case OP_EXTUNI:
    case OP_KETRMAX:
    case OP_KETRMIN:
    case OP_KETRPOS:
    case OP_MINPLUS:
    case OP_MINPLUSI:
    case OP_MINQUERY:
    case OP_MINQUERYI:
    case OP_MINSTAR:
    case OP_MINSTARI:
    case OP_MINUPTO:
    case OP_MINUPTOI:
    case OP_NOTMINPLUS:
    case OP_NOTMINPLUSI:
    case OP_NOTMINQUERY:
    case OP_NOTMINQUERYI:
    case OP_NOTMINSTAR:
    case OP_NOTMINSTARI:
    case OP_NOTMINUPTO:
    case OP_NOTMINUPTOI:
    case OP_NOTPLUS:
    case OP_NOTPLUSI:
    case OP_NOTPOSPLUS:
    case OP_NOTPOSPLUSI:
    case OP_NOTPOSQUERY:
    case OP_NOTPOSQUERYI:
    case OP_NOTPOSSTAR:
    case OP_NOTPOSSTARI:
    case OP_NOTPOSUPTO:
    case OP_NOTPOSUPTOI:
    case OP_NOTQUERY:
    case OP_NOTQUERYI:
    case OP_NOTSTAR:
    case OP_NOTSTARI:
    case OP_NOTUPTO:
    case OP_NOTUPTOI:
    case OP_PLUS:
    case OP_PLUSI:
    case OP_POSPLUS:
    case OP_POSPLUSI:
    case OP_POSQUERY:
    case OP_POSQUERYI:
    case OP_POSSTAR:
    case OP_POSSTARI:
    case OP_POSUPTO:
    case OP_POSUPTOI:
    case OP_QUERY:
    case OP_QUERYI:
    case OP_REF:
    case OP_REFI:
    case OP_DNREF:
    case OP_DNREFI:
    case OP_SBRA:
    case OP_SBRAPOS:
    case OP_SCBRA:
    case OP_SCBRAPOS:
    case OP_SCOND:
    case OP_SKIPZERO:
    case OP_STAR:
    case OP_STARI:
    case OP_TYPEMINPLUS:
    case OP_TYPEMINQUERY:
    case OP_TYPEMINSTAR:
    case OP_TYPEMINUPTO:
    case OP_TYPEPLUS:
    case OP_TYPEPOSPLUS:
    case OP_TYPEPOSQUERY:
    case OP_TYPEPOSSTAR:
    case OP_TYPEPOSUPTO:
    case OP_TYPEQUERY:
    case OP_TYPESTAR:
    case OP_TYPEUPTO:
    case OP_UPTO:
    case OP_UPTOI:
    return -1;

    /* Catch unrecognized opcodes so that when new ones are added they
    are not forgotten, as has happened in the past. */

    default:
    return -4;
    }
  }
/* Control never gets here */
}

Answer 3

Los motores Regex están diseñados para funcionar de izquierda a derecha .

Para lookaheads, el motor coincide con todo el texto a la derecha de la posición actual. Sin embargo, para lookbehinds, el motor de expresiones regulares determina la longitud de la cadena a dar un paso atrás y luego verifica la coincidencia (nuevamente de izquierda a derecha).

Por lo tanto, si proporciona algunos cuantificadores infinitos como * o + , fíjese que no funcionará porque el motor no sabe cuántos pasos hay que retroceder.

Daré un ejemplo de cómo funciona la mirada (el ejemplo es bastante tonto).

Supongamos que desea hacer coincidir el apellido Panta , solo si el primer nombre tiene entre 5 y 7 caracteres.

Tomemos la cuerda:

Full name is Subigya Panta.

Considere la expresión regular:

(?<=/b/w{5,7}/b)/sPanta

Como funciona el motor

El motor reconoce la existencia de un aspecto positivo detrás de él, por lo que primero busca la palabra Panta (con un carácter de espacio en blanco delante de ella). Es un partido.

Ahora, el motor parece coincidir con la expresión regular dentro de la apariencia detrás. Retrocede 7 caracteres (ya que el cuantificador es codicioso). La palabra límite coincide con la posición entre el espacio y S Luego coincide con todos los 7 caracteres, y luego el siguiente límite de palabra coincide con la posición entre a y el espacio.

La expresión regular dentro del lookbe es una coincidencia y, por lo tanto, toda la expresión regular devuelve true porque la cadena coincidente contiene Panta . (Tenga en cuenta que las aserciones de búsqueda son de ancho cero y no consumen ningún carácter).