Wie funktioniert {m} {n} (zweimal „genau n-mal“)?

So oder so (herumspielen) fand ich mich mit einem Regex wie \d{1}{2}.

Logischerweise sollte es für mich bedeuten:

(Eine Ziffer genau einmal) genau zweimal, dh eine Ziffer genau zweimal.

Tatsächlich scheint es aber nur "eine Ziffer genau einmal" zu bedeuten (und ignoriert daher die {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

Ähnliche Ergebnisse können mit {n}{m,n}oder ähnlich gesehen werden .

Warum passiert das? Wird es irgendwo explizit in der Regex / Java-Dokumentation angegeben oder ist es nur eine Entscheidung, die Java-Entwickler spontan getroffen haben, oder ist es vielleicht ein Fehler?

Oder wird es tatsächlich nicht ignoriert und bedeutet tatsächlich etwas ganz anderes?

Nicht, dass es viel ausmacht, aber es ist kein allgemeines Regex-Verhalten. Rubular macht das, was ich erwarte.

Hinweis - Der Titel dient hauptsächlich der Suchbarkeit für Benutzer, die wissen möchten, wie er funktioniert (nicht warum).

Wenn ich Ihren regulären Ausdruck in RegexBuddy mithilfe der Java-regulären Ausdruckssyntax eingebe, wird die folgende Meldung angezeigt

Quantifizierern muss ein Token vorangestellt werden, das wiederholt werden kann «{2}»

Das Ändern des regulären Ausdrucks zur expliziten Verwendung einer Gruppierung ^(\d{1}){2}behebt diesen Fehler und funktioniert wie erwartet.

Ich gehe davon aus, dass die Java-Regex-Engine den Fehler / Ausdruck einfach vernachlässigt und mit dem arbeitet, was bisher kompiliert wurde.

Bearbeiten

Der Verweis auf den IEEE-Standard in der Antwort von @ piet.t scheint diese Annahme zu stützen.

Bearbeiten Sie 2 (ein großes Lob an @fncomp)

Der Vollständigkeit halber würde man normalerweise verwenden (?:), um die Erfassung der Gruppe zu vermeiden. Der vollständige Regex wird dann^(?:\d{1}){2}

IEEE-Standard 1003.1 sagt:

Das Verhalten mehrerer benachbarter Duplizierungssymbole ('*' und Intervalle) führt zu undefinierten Ergebnissen.

So kann jede Implementierung tun, was sie will, verlassen Sie sich einfach nicht auf etwas Bestimmtes ...

Wissenschaftlicher Ansatz:
^{Klicken Sie auf die Muster, um das Beispiel auf regexplanet.com anzuzeigen, und klicken Sie auf die grüne Java-Schaltfläche .}

• Sie haben bereits \d{1}{2}Übereinstimmungen gezeigt "1"und stimmen nicht überein "12", daher wissen wir, dass dies nicht als interpretiert wird (?:\d{1}){2}.
• Trotzdem ist 1 eine langweilige Zahl und {1} könnte wegoptimiert werden. Lassen Sie uns etwas interessanteres ausprobieren :
  \d{2}{3}. Dies entspricht immer noch nur zwei Zeichen (nicht sechs), {3}wird ignoriert.
• OK. Es gibt eine einfache Möglichkeit zu sehen, was eine Regex-Engine tut. Erfasst es?
  Lass es uns versuchen (\d{1})({2}). Seltsamerweise funktioniert das. Die zweite Gruppe $2erfasst die leere Zeichenfolge.
• Warum brauchen wir also die erste Gruppe? Wie wäre es ({1})? Funktioniert noch.
• Und nur {1}? Kein Problem da.
  Es sieht so aus, als wäre Java hier etwas komisch.

• Toll! Ist {1}also gültig. Wir wissen, dass Java expandiert *und +zu {0,0x7FFFFFFF}und{1,0x7FFFFFFF} , also wird *oder +funktioniert? Nein:

  Baumelndes Metazeichen '+' in der Nähe von Index 0
  +
  ^

  Die Validierung muss vorher erfolgen *und +wird erweitert.

Ich habe in der Spezifikation nichts gefunden, was das erklärt. Es sieht so aus, als müsste ein Quantifizierer mindestens nach einem Zeichen, Klammern oder Klammern stehen.

Die meisten dieser Muster werden von anderen Regex-Geschmacksrichtungen als ungültig angesehen, und das aus gutem Grund - sie sind nicht sinnvoll.

Zuerst war ich überrascht, dass dies keine wirft PatternSyntaxException.

Ich kann meine Antwort nicht auf Fakten stützen, daher ist dies nur eine fundierte Vermutung:

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

Ich habe die {m}{n}Syntax nirgendwo gesehen. Es scheint, dass die Regex-Engine auf dieser Rubular-Seite den {2}Quantifizierer auf das kleinstmögliche Token davor anwendet - das heißt \\d{1}. Um dies in Java (oder den meisten anderen Regex-Engines, wie es scheint) nachzuahmen, müssen Sie Folgendes gruppieren \\d{1}:

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

Sehen Sie es hier in Aktion .

Kompilierte Struktur des regulären Ausdrucks

Kobis Antwort ist genau auf das Verhalten von Java Regex (Sun / Oracle-Implementierung) für den Fall "^\\d{1}{2}$"oder "{1}".

Unten ist die interne kompilierte Struktur von "^\\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

Blick auf den Quellcode

Aus meiner Untersuchung geht hervor, dass der Fehler wahrscheinlich auf die Tatsache zurückzuführen {ist , dass er in der privaten Methode nicht ordnungsgemäß überprüft wurde sequence().

Die Methode sequence()ruft das atom()auf, um das Atom zu analysieren, hängt dann durch Aufrufen einen Quantifizierer an das Atom an closure()und verkettet alle Atome mit Verschluss zu einer Sequenz.

Zum Beispiel bei diesem regulären Ausdruck:

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

Dann wird der Top-Level - Aufruf sequence()erhält die kompilierten Knoten für ^, \d{4}, a, (bc|gh)+, d*, $und Kette sie zusammen.

Schauen wir uns vor diesem Hintergrund den Quellcode sequence()von OpenJDK 8-b132 an (Oracle verwendet dieselbe Codebasis):

@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;
}

Beachten Sie die Linie throw error("Dangling meta character '" + ((char)ch) + "'");. Dies ist , wo der Fehler ausgelöst wird , wenn +, *, ?baumeln und ist nicht Teil eines vorhergehenden Token. Wie Sie sehen können, {gehört nicht zu den Fällen, Fehler zu werfen. Tatsächlich ist es in der Liste der Fälle in nicht vorhanden sequence(), und der Kompilierungsprozess wird von defaultFall zu Fall direkt an weitergeleitet 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);
    }
}

Wenn der Prozess eintritt atom(), {bricht er ab switchund forwiederholt sich, und es wird ein neues Slice mit der Länge 0 erstellt (die Länge kommt von first, was 0 ist).

Wenn dieses Slice zurückgegeben wird, wird der Quantifizierer von analysiert closure(), was zu dem führt, was wir sehen.

Beim Vergleich des Quellcodes von Java 1.4.0, Java 5 und Java 8 scheint sich der Quellcode von sequence()und nicht wesentlich zu ändern atom(). Es scheint, dass dieser Fehler von Anfang an vorhanden war.

Standard für regulären Ausdruck

Die am häufigsten gewählte Antwort unter Berufung auf den IEEE-Standard 1003.1 (oder den POSIX-Standard) ist für die Diskussion irrelevant, da Java BRE und ERE nicht implementiert .

Es gibt viele Syntaxen, die gemäß dem Standard zu undefiniertem Verhalten führen, aber es ist ein genau definiertes Verhalten für viele andere Regex-Varianten (obwohl es eine andere Sache ist, ob sie übereinstimmen oder nicht). Zum Beispiel \dist es gemäß dem Standard undefiniert, stimmt jedoch in vielen Regex-Varianten mit Ziffern (ASCII / Unicode) überein.

Leider gibt es keinen anderen Standard für die Syntax regulärer Ausdrücke.

Es gibt jedoch einen Standard für Unicode Regular Expression, der sich auf Funktionen konzentriert, die eine Unicode-Regex-Engine haben sollte. Die Java- PatternKlasse implementiert mehr oder weniger die Unterstützung der Stufe 1, wie in UTS # 18: Unicode Regular Expression und RL2.1 beschrieben (wenn auch extrem fehlerhaft).

Ich vermute, dass in der Definition von {}so etwas wie "Schau zurück, um einen gültigen Ausdruck zu finden (ohne mich selbst - {}"), also gibt es in deinem Beispiel nichts zwischen }und {.

Wenn Sie es in Klammern setzen, funktioniert es wie erwartet: http://refiddle.com/gv6 .