Как работает {m}{n} ("ровно n раз" дважды)?


Итак, так или иначе (играя вокруг), я оказался с регулярным выражением, как d{1}{2}.

логично, для меня, это должно означать:

(цифру ровно один раз) ровно в два раза, т. е. цифра ровно в два раза.

но это, по-видимому, просто означает "цифра ровно один раз" (таким образом, игнорируя {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

аналогичные результаты можно увидеть с помощью {n}{m,n} или аналогичные.

Почему это происходит? Это явно указано в документации regex / Java где-то или это просто решение разработчиков Java, сделанное на лету, или это может быть ошибка?

или это на самом деле не игнорируется, и это на самом деле означает нечто совершенно другое?

не то чтобы это имело большое значение, но это не сквозное поведение регулярных выражений, Rubular делает то, что я ожидал.

Примечание-название в основном для поиска для пользователей, которые хотят знать, как это работает (не почему).

7 74

7 ответов:

когда я ввожу ваше регулярное выражение в RegexBuddy, используя синтаксис Java regex, он отображает следующее сообщение

Кванторам должен предшествовать токен, который можно повторить "{2}"

изменение регулярного выражения для явного использования группировки ^(\d{1}){2} решает эту ошибку и работает, как вы ожидаете.


Я предполагаю, что механизм регулярных выражений java просто пренебрегает ошибкой/выражением и работает с тем, что было скомпилировано до сих пор.

Edit

ссылка IEEE-Standard на @piet.ответ Т кажется, поддерживает это предположение.

Edit 2(слава @fncomp)

для полноты картины обычно используется (?:)чтобы избежать захвата группы. Полное регулярное выражение тогда становится ^(?:\d{1}){2}

IEEE-Standard 1003.1 говорит:

поведение нескольких соседних символов дублирования ('*'и интервалов) приводит к неопределенным результатам.

поэтому каждая реализация может делать все, что угодно, просто не полагайтесь ни на что конкретное...

научный подход:
нажмите на шаблоны, чтобы увидеть пример на regexplanet.com и нажмите на зеленую кнопку Java.

  • вы уже показали \d{1}{2} игр "1", и не соответствует "12", Так что знаю это не интерпретируется как (?:\d{1}){2}.
  • тем не менее, 1-это скучное число, и {1}может оптимизироваться прочь, давайте попробуем что-то еще интересно:
    \d{2}{3}. Это все еще соответствует только двум символам (а не шести), {3} игнорируется.
  • ОК. Есть простой способ увидеть, что делает движок регулярных выражений. Это захватывает?
    Давайте попробуем (\d{1})({2}). Как ни странно, это работает. Вторая группа, , захватывает пустую строку.
  • так зачем нам нужна первая группа? Как насчет ({1})? Все еще работать.
  • и просто {1}? Нет проблема есть.
    Похоже, что Java здесь немного странно.
  • великолепно! Так что {1} действителен. Мы знаем!--57-->Java расширяется * и + до {0,0x7FFFFFFF} и {1,0x7FFFFFFF}, так * или + работы? Нет:

    висячий метасимвол ' + ' рядом с индексом 0
    +
    ^

    проверка должна предшествовать * и + расширяются.

I не нашел ничего в спецификации, что объясняет это, это выглядит как Квантор должны прийти, по крайней мере, после того, как символ, скобки, или круглые скобки.

сначала я был удивлен, что это не бросает PatternSyntaxException.

Я не могу основывать свой ответ на какие-то факты, так что это просто догадка:

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

Я никогда не видел {m}{n} синтаксис в любом месте. Похоже, что движок регулярных выражений на этой рублевой странице применяет {2} Квантор до наименьшего возможного маркера до того, что \d{1}. Чтобы имитировать это в Java (или большинство других движков регулярных выражений, казалось бы), вам нужно сгруппировать \d{1} вот так:

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

видеть в действии здесь.

составлена структура регулярного выражения

Коби!--42--> это пятно о поведении Java regex (реализация Sun / Oracle) для случая "^\d{1}{2}$" или "{1}".

Ниже приведена внутренняя скомпилированная структура "^\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

глядя на исходный код

из моего расследования, ошибка, вероятно, из-за того, что { должным образом не проверил в отдельный метод sequence().

метод sequence() звонки atom() чтобы разобрать атом, затем присоедините Квантор к атому, вызвав closure(), и связывает все атомы-с-замыканием вместе в одну последовательность.

например, если это регулярное выражение:

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

затем вызов верхнего уровня sequence() получит скомпилированные узлы для ^,\d{4},a,(bc|gh)+,d*,$ и их последовательности.

С этой идеей в ум, давайте посмотрим на исходный код sequence(), скопировал из OpenJDK 8-b132 (Oracle использует ту же базу кода):

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

обратите внимание на строку throw error("Dangling meta character '" + ((char)ch) + "'");. Это где ошибка если +,*,? болтаются и не является частью предыдущего маркера. Как видите, { не является одним из случаев, чтобы бросить ошибку. На самом деле, его нет в списке дел в sequence(), и процесс компиляции пройдет default случае напрямую к 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);
    }
}

когда процесс входит atom(), так как он встречает { сразу же, он ломается от switch и for петли, и новый срез длиной 0 создается (длина исходит от first, что равно 0).

когда этот срез возвращается, Квантор анализируется с помощью closure(), в результате чего мы видим.

сравнивая исходный код Java 1.4.0, Java 5 и Java 8, кажется, что нет много изменений в исходном коде sequence() и atom(). Кажется, эта ошибка была там с самого начала.

стандарт для регулярного выражения

The топ-проголосовали ответ со ссылкой на IEEE-Standard 1003.1 (или стандарт POSIX) не имеет отношения к обсуждению, так как Java не реализует Бре и здесь.

есть много синтаксиса, приводящего к неопределенному поведению в соответствии со стандартом, но это четко определенное поведение во многих других вариантах регулярных выражений (хотя согласны ли они или нет-это другой вопрос). Например, \d не определен в соответствии со стандартом, но он соответствует цифрам (ASCII/Unicode) во многих вариантах регулярных выражений.

к сожалению, нет никакого другого стандарта на синтаксис регулярных выражений.

существует, однако, стандарт на регулярное выражение Unicode, который фокусируется на функциях, которые должен иметь механизм регулярных выражений Unicode. Java Pattern класс более или менее реализует поддержку уровня 1, как описано в UTS #18: регулярное выражение Юникода и RL2.1 (хотя и очень глючит).

Я предполагаю, что в определении {} Это что - то вроде "оглянитесь назад, чтобы найти правильное выражение (исключая себя -{}", поэтому в вашем примере нет ничего между } и {.

в любом случае, если вы обернете его в скобки, он будет работать так, как вы ожидали:http://refiddle.com/gv6.