Pregunta ¿Cómo funciona {m} {n} ("exactamente n veces" dos veces)?


Entonces, de una forma u otra (jugando), me encontré con una expresión regular como \d{1}{2}.

Lógicamente, para mí, debería significar:

(Un dígito exactamente una vez) exactamente dos veces, es decir, un dígito exactamente dos veces.

Pero, de hecho, parece significar simplemente "un dígito exactamente una vez" (ignorando así el {2})

String regex = "^\\d{1}{2}$"; // ^$ to make those not familiar with 'matches' happy
System.out.println("1".matches(regex)); // true
System.out.println("12".matches(regex)); // false

Se pueden ver resultados similares usando {n}{m,n} o similar.

¿Por qué pasó esto? ¿Se menciona explícitamente en la documentación de regex / Java en alguna parte o es solo una decisión que los desarrolladores de Java hicieron sobre la marcha o es quizás un error?

¿O de hecho no se ignora y en realidad significa algo completamente diferente?

No es que importe mucho, pero no es un comportamiento regex general, Rubular hace lo que espero

Nota: el título es principalmente para búsqueda de usuarios que desean saber cómo funciona (no por qué).


74
2017-09-23 12:01


origen


Respuestas:


Cuando ingreso su expresión regular en RegexBuddy usando la sintaxis de expresiones regulares de Java, muestra el siguiente mensaje

Los cuantificadores deben ir precedidos de un token que se puede repetir «{2}»

Cambiar la expresión regular para usar explícitamente una agrupación ^(\d{1}){2} resuelve ese error y funciona como esperabas.


Supongo que el motor jage regex simplemente descuida el error / expresión y funciona con lo que se ha compilado hasta ahora.

Editar

La referencia al IEEE-Estándar en @ piet.t's answer parece apoyar esa suposición.

Editar 2  (felicitaciones a @fncomp)

Para completar, uno normalmente usaría (?:)para evitar capturar al grupo. La expresión regular completa se convierte en ^(?:\d{1}){2} 


73
2017-09-23 12:09



IEEE-Standard 1003.1 dice:

El comportamiento de múltiples símbolos de duplicación adyacentes ('*' e intervalos) produce resultados indefinidos.

Entonces, cada implementación puede hacer lo que quiera, simplemente no confíe en nada específico ...


107
2017-09-23 12:10



Enfoque científico:
haga clic en los patrones para ver el ejemplo en regexplanet.com, y haga clic en el botón verde de Java.

  • Ya has mostrado \d{1}{2} partidos "1"y no coincide "12", Así que nosotros saber no se interpreta como (?:\d{1}){2}.
  • Aún así, 1 es un número aburrido, y {1}  podría optimícese, intentemos algo más interesante:
    \d{2}{3}. Esto solo coincide con dos personajes (no seis), {3} es ignorado
  • De acuerdo. Hay una manera fácil de ver lo que hace un motor regex. ¿Captura?
    Intentemos (\d{1})({2}). Curiosamente, esto funciona. El segundo grupo, $2, captura la cadena vacía.
  • Entonces, ¿por qué necesitamos el primer grupo? Qué tal si ({1})? Todavía funciona.
  • Y solo {1}? No hay problema allí.
    Parece que Java está siendo un poco raro aquí.
  • ¡Estupendo! Asi que {1} es válida. Sabemos Java se expande * y + a {0,0x7FFFFFFF} y {1,0x7FFFFFFF}, Así será * o + ¿trabajo? No:

    Carácter meta colgando '+' cerca del índice 0
      +
      ^

    La validación debe venir antes * y +están expandidos

No encontré nada en la especificación que explique que, miradas como un cuantificador debe venir al menos después de un carácter, corchetes o paréntesis.

La mayoría de estos patrones se consideran inválidos por otros sabores de expresiones regulares, y por una buena razón, no tienen sentido.


10
2017-09-24 07:29



Al principio me sorprendió que esto no arroje PatternSyntaxException.

No puedo basar mi respuesta en ningún hecho, así que esto es solo una suposición educada:

"\\d{1}"    // matches a single digit
"\\d{1}{2}" // matches a single digit followed by two empty strings

4
2017-09-23 12:10



Nunca he visto el {m}{n} sintaxis en cualquier lugar. Parece que el motor de expresiones regulares en esta página de Rubular aplica el {2} cuantificador al token más pequeño posible antes de eso - que es \\d{1}. Para imitar esto en Java (o en la mayoría de los otros motores de expresiones regulares, parece), debe agrupar el \\d{1} al igual que:

^(\\d{1}){2}$

Míralo en acción aquí.


4
2017-09-23 12:12



Estructura compilada de la expresión regular

La respuesta de Kobi es acertada sobre el comportamiento de Java Regex (implementación de Sun / Oracle) para el caso "^\\d{1}{2}$", o "{1}".

A continuación se muestra la estructura compilada interna de "^\\d{1}{2}$":

^\d{1}{2}$
Begin. \A or default ^
Curly. Greedy quantifier {1,1}
  Ctype. POSIX (US-ASCII): DIGIT
  Node. Accept match
Curly. Greedy quantifier {2,2}
  Slice. (length=0)

  Node. Accept match
Dollar(multiline=false). \Z or default $
java.util.regex.Pattern$LastNode
Node. Accept match

Mirando el código fuente

De mi investigación, el error probablemente se deba a que { no se verifica correctamente en el método privado sequence().

El método sequence() llama a la atom() para analizar el átomo, luego adjuntar cuantificador al átomo llamando closure()y encadena todos los átomos con cierre juntos en una secuencia.

Por ejemplo, dada esta expresión regular:

^\d{4}a(bc|gh)+d*$

Luego, la llamada de nivel superior a sequence() recibirá los nodos compilados para ^, \d{4}, a, (bc|gh)+, d*, $ y encadenarlos juntos.

Con esa idea en mente, echemos un vistazo al código fuente de sequence(), copiado de OpenJDK 8-b132 (Oracle usa la misma base de código):

@SuppressWarnings("fallthrough")
/**
 * Parsing of sequences between alternations.
 */
private Node sequence(Node end) {
    Node head = null;
    Node tail = null;
    Node node = null;
LOOP:
    for (;;) {
        int ch = peek();
        switch (ch) {
        case '(':
            // Because group handles its own closure,
            // we need to treat it differently
            node = group0();
            // Check for comment or flag group
            if (node == null)
                continue;
            if (head == null)
                head = node;
            else
                tail.next = node;
            // Double return: Tail was returned in root
            tail = root;
            continue;
        case '[':
            node = clazz(true);
            break;
        case '\\':
            ch = nextEscaped();
            if (ch == 'p' || ch == 'P') {
                boolean oneLetter = true;
                boolean comp = (ch == 'P');
                ch = next(); // Consume { if present
                if (ch != '{') {
                    unread();
                } else {
                    oneLetter = false;
                }
                node = family(oneLetter, comp);
            } else {
                unread();
                node = atom();
            }
            break;
        case '^':
            next();
            if (has(MULTILINE)) {
                if (has(UNIX_LINES))
                    node = new UnixCaret();
                else
                    node = new Caret();
            } else {
                node = new Begin();
            }
            break;
        case '$':
            next();
            if (has(UNIX_LINES))
                node = new UnixDollar(has(MULTILINE));
            else
                node = new Dollar(has(MULTILINE));
            break;
        case '.':
            next();
            if (has(DOTALL)) {
                node = new All();
            } else {
                if (has(UNIX_LINES))
                    node = new UnixDot();
                else {
                    node = new Dot();
                }
            }
            break;
        case '|':
        case ')':
            break LOOP;
        case ']': // Now interpreting dangling ] and } as literals
        case '}':
            node = atom();
            break;
        case '?':
        case '*':
        case '+':
            next();
            throw error("Dangling meta character '" + ((char)ch) + "'");
        case 0:
            if (cursor >= patternLength) {
                break LOOP;
            }
            // Fall through
        default:
            node = atom();
            break;
        }

        node = closure(node);

        if (head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
    }
    if (head == null) {
        return end;
    }
    tail.next = end;
    root = tail;      //double return
    return head;
}

Toma nota de la línea throw error("Dangling meta character '" + ((char)ch) + "'");. Aquí es donde se produce el error si +, *, ? están colgando y no es parte de una ficha anterior. Como puedes ver, { no está entre los casos para arrojar error. De hecho, no está presente en la lista de casos en sequence(), y el proceso de compilación pasará default caso directamente a atom().

@SuppressWarnings("fallthrough")
/**
 * Parse and add a new Single or Slice.
 */
private Node atom() {
    int first = 0;
    int prev = -1;
    boolean hasSupplementary = false;
    int ch = peek();
    for (;;) {
        switch (ch) {
        case '*':
        case '+':
        case '?':
        case '{':
            if (first > 1) {
                cursor = prev;    // Unwind one character
                first--;
            }
            break;
        // Irrelevant cases omitted
        // [...]
        }
        break;
    }
    if (first == 1) {
        return newSingle(buffer[0]);
    } else {
        return newSlice(buffer, first, hasSupplementary);
    }
}

Cuando el proceso entra atom(), ya que se encuentra { de inmediato, se rompe de switch y for loop, y una nueva porción con longitud 0 se crea (la longitud proviene de first, que es 0).

Cuando se devuelve esta porción, el cuantificador es analizado por closure(), lo que resulta en lo que vemos.

Comparando el código fuente de Java 1.4.0, Java 5 y Java 8, no parece haber muchos cambios en el código fuente de sequence() y atom(). Parece que este error ha estado allí desde el principio.

Estándar para expresión regular

los respuesta mejor votada citando IEEE-Standard 1003.1 (o el estándar POSIX) es irrelevante para la discusión, ya que Java no implementa BRE y ERE.

Hay muchas sintaxis que dan como resultado un comportamiento indefinido de acuerdo con el estándar, pero es un comportamiento bien definido en muchos otros sabores de expresiones regulares (aunque si están de acuerdo o no es otro tema). Por ejemplo, \dno está definido de acuerdo con el estándar, pero coincide con los dígitos (ASCII / Unicode) en muchos sabores de expresiones regulares.

Lamentablemente, no hay otro estándar en la sintaxis de expresiones regulares.

Sin embargo, existe un estándar en Expresión regular Unicode, que se centra en las características que debe tener un motor de expresiones regulares Unicode. Java Pattern clase más o menos implementa soporte de nivel 1 como se describe en UTS # 18: Expresión regular Unicode y RL2.1 (aunque extremadamente con errores).


4
2018-04-21 11:21



Supongo que en la definición de {} es algo así como "mira hacia atrás para encontrar una expresión válida (excluyéndome a mí mismo, {}", entonces en tu ejemplo no hay nada entre } y {.

De todos modos, si lo envuelves entre paréntesis, funcionará como esperabas: http://refiddle.com/gv6.


0
2017-09-23 12:08