Ошибка в двойном отрицании классов символов регулярных выражений?

Question

TL;DR
Зачем [^\\D2], [^[^0-9]2], [^2[^0-9]] получить разные результаты в Java?

---

Код, используемый для тестов. Вы можете пропустить это сейчас.

String[] regexes = { "[[^0-9]2]", "[\\D2]", "[013-9]", "[^\\D2]", "[^[^0-9]2]", "[^2[^0-9]]" };
String[] tests = { "x", "1", "2", "3", "^", "[", "]" };

System.out.printf("match | %9s , %6s | %6s , %6s , %6s , %10s%n", (Object[]) regexes);
System.out.println("-----------------------------------------------------------------------");
for (String test : tests)
    System.out.printf("%5s | %9b , %6b | %7b , %6b , %10b , %10b %n", test,
            test.matches(regexes[0]), test.matches(regexes[1]),
            test.matches(regexes[2]), test.matches(regexes[3]),
            test.matches(regexes[4]), test.matches(regexes[5]));

---

Допустим, мне нужно регулярное выражение, которое будет принимать символы, которые

• не цифры,
• за исключением 2,

Таким образом, такое регулярное выражение должно представлять каждый символ, кроме 0, 1, 3,4,..., 9, Я могу написать это по крайней мере двумя способами, которые будут суммой всего, что не является цифрой с 2:

• [[^0-9]2]
• [\\D2]

Оба эти регулярных выражения работают как ожидалось

match , [[^0-9]2] ,  [\D2]
--------------------------
    x ,      true ,   true
    1 ,     false ,  false
    2 ,      true ,   true
    3 ,     false ,  false
    ^ ,      true ,   true
    [ ,      true ,   true
    ] ,      true ,   true

Теперь допустим, что я хочу изменить принятые символы. (поэтому я хочу принять все цифры, кроме 2) Я мог бы создать регулярное выражение, которое явно содержит все принятые символы, такие как

• [013-9]

или попытайтесь опровергнуть два ранее описанных регулярных выражения, поместив их в другое [^...] лайк

• [^\\D2]
• [^[^0-9]2]
  или даже
• [^2[^0-9]]

но к моему удивлению только первые две версии работают как положено

match | [[^0-9]2] ,  [\D2] | [013-9] , [^\D2] , [^[^0-9]2] , [^2[^0-9]] 
------+--------------------+------------------------------------------- 
    x |      true ,   true |   false ,  false ,       true ,       true 
    1 |     false ,  false |    true ,   true ,      false ,       true 
    2 |      true ,   true |   false ,  false ,      false ,      false 
    3 |     false ,  false |    true ,   true ,      false ,       true 
    ^ |      true ,   true |   false ,  false ,       true ,       true 
    [ |      true ,   true |   false ,  false ,       true ,       true 
    ] |      true ,   true |   false ,  false ,       true ,       true 

Итак, мой вопрос почему [^[^0-9]2] или же [^2[^0-9]] не ведет себя как [^\D2]? Могу ли я как-то исправить эти регулярные выражения, чтобы я мог использовать [^0-9] внутри них?

Answer 1

В коде синтаксического анализа класса символов реализации Oracle Pattern класс, который поставляется с вашим JRE/JDK, если вы скачали его с веб-сайта Oracle или используете OpenJDK. Я не проверял, как другие реализации JVM (особенно GNU Classpath) анализируют регулярное выражение в вопросе.

С этого момента любая ссылка на Pattern Класс и его внутренняя работа строго ограничены реализацией Oracle (эталонная реализация).

Это займет некоторое время, чтобы прочитать и понять, как Pattern Класс анализирует вложенное отрицание, как показано в вопросе. Тем не менее, я написал программу ¹ для извлечения информации из Pattern объект (с Reflection API), чтобы посмотреть на результат компиляции. Ниже приводятся результаты запуска моей программы на Java HotSpot Client VM версии 1.7.0_51.

^{1: В настоящее время программа представляет собой неловкий беспорядок. Я дополню этот пост ссылкой, когда я закончу и проведу рефакторинг.}

[^0-9]
Start. Start unanchored match (minLength=1)
CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
  Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Ничего удивительного здесь.

[^[^0-9]]
Start. Start unanchored match (minLength=1)
CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
  Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

[^[^[^0-9]]]
Start. Start unanchored match (minLength=1)
CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
  Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Следующие 2 случая выше скомпилированы в ту же программу, что и [^0-9], что нелогично.

[[^0-9]2]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

[\D2]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Ctype. Match POSIX character class DIGIT (US-ASCII)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

Ничего странного в 2 случаях выше, как указано в вопросе.

[013-9]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 2 character(s):
    [U+0030][U+0031]
    01
  Pattern.rangeFor (character range). Match any character within the range from code point U+0033 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

[^\D2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
      Ctype. Match POSIX character class DIGIT (US-ASCII)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

Эти 2 случая работают как положено, как указано в вопросе. Однако обратите внимание на то, как движок принимает дополнение первого класса символов (\D) и применить разность наборов к классу символов, состоящему из остатка.

[^[^0-9]2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

[^[^[^0-9]]2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

[^[^[^[^0-9]]]2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

Как было подтверждено тестированием Keppil в комментарии, приведенный выше вывод показывает, что все три приведенных выше регулярных выражения скомпилированы в одну и ту же программу!

[^2[^0-9]]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
      [U+0032]
      2
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Вместо NOT(UNION(2, NOT(0-9)), который 0-13-9, мы получаем UNION(NOT(2), NOT(0-9)), что эквивалентно NOT(2),

[^2[^[^0-9]]]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
      [U+0032]
      2
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Регулярное выражение [^2[^[^0-9]]] компилируется в ту же программу, что и [^2[^0-9]] из-за той же ошибки.

Существует неразрешенная ошибка, которая, кажется, имеет ту же природу: JDK-6609854.

---

объяснение

предварительный

Ниже приведены детали реализации Pattern класс, который нужно знать, прежде чем читать дальше:

• Pattern класс составляет String в цепочку узлов каждый узел отвечает за небольшую и четко определенную ответственность и передает работу следующему узлу в цепочке. Node класс является базовым классом всех узлов.
• CharProperty класс является базовым классом всех классов символов, связанных Node s.
• BitClass класс является подклассом CharProperty класс, который использует boolean[] массив для ускорения сопоставления символов Latin-1 (кодовая точка <= 255). Имеет add метод, который позволяет добавлять символы во время компиляции.
• CharProperty.complement, Pattern.union, Pattern.intersection являются методами, соответствующими операциям над множествами. То, что они делают, говорит само за себя.
• Pattern.setDifference является асимметричной разностью множеств.

Разбор класса персонажа на первый взгляд

Прежде чем смотреть на полный код CharProperty clazz(boolean consume) Метод, который является методом, отвечающим за синтаксический анализ символьного класса, давайте рассмотрим чрезвычайно упрощенную версию кода, чтобы понять поток кода:

private CharProperty clazz(boolean consume) {
    // [Declaration and initialization of local variables - OMITTED]
    BitClass bits = new BitClass();
    int ch = next();
    for (;;) {
        switch (ch) {
            case '^':
                // Negates if first char in a class, otherwise literal
                if (firstInClass) {
                    // [CODE OMITTED]
                    ch = next();
                    continue;
                } else {
                    // ^ not first in class, treat as literal
                    break;
                }
            case '[':
                // [CODE OMITTED]
                ch = peek();
                continue;
            case '&':
                // [CODE OMITTED]
                continue;
            case 0:
                // [CODE OMITTED]
                // Unclosed character class is checked here
                break;
            case ']':
                // [CODE OMITTED]
                // The only return statement in this method
                // is in this case
                break;
            default:
                // [CODE OMITTED]
                break;
        }
        node = range(bits);

        // [CODE OMITTED]
        ch = peek();
    }
}

Код в основном читает входные данные (вход String конвертируется в ноль int[] кодовых точек), пока не попадет ] или конец строки (класс закрытых символов).

Код немного сбивает с толку continue а также break смешивание внутри switch блок. Тем не менее, пока вы понимаете, что continue принадлежит внешнему for петля и break принадлежит к switch блок, код легко понять:

• Случаи, заканчивающиеся на continue никогда не выполнит код после switch заявление.
• Случаи, заканчивающиеся на break может выполнить код после switch заявление (если это не так return уже).

Из вышеприведенного наблюдения мы можем видеть, что всякий раз, когда обнаруживается, что символ не является специальным и должен быть включен в класс символов, мы выполняем код после switch утверждение, в котором node = range(bits); это первое утверждение.

Если вы проверите исходный код, метод CharProperty range(BitClass bits) анализирует "один символ или диапазон символов в классе символов". Метод либо возвращает то же самое BitClass объект передан (с добавлением нового символа) или возвращает новый экземпляр CharProperty учебный класс.

Кровавые детали

Далее, давайте посмотрим на полную версию кода (с пересечением символа класса части пересечения && опущены):

private CharProperty clazz(boolean consume) {
    CharProperty prev = null;
    CharProperty node = null;
    BitClass bits = new BitClass();
    boolean include = true;
    boolean firstInClass = true;
    int ch = next();
    for (;;) {
        switch (ch) {
            case '^':
                // Negates if first char in a class, otherwise literal
                if (firstInClass) {
                    if (temp[cursor-1] != '[')
                        break;
                    ch = next();
                    include = !include;
                    continue;
                } else {
                    // ^ not first in class, treat as literal
                    break;
                }
            case '[':
                firstInClass = false;
                node = clazz(true);
                if (prev == null)
                    prev = node;
                else
                    prev = union(prev, node);
                ch = peek();
                continue;
            case '&':
                // [CODE OMITTED]
                // There are interesting things (bugs) here,
                // but it is not relevant to the discussion.
                continue;
            case 0:
                firstInClass = false;
                if (cursor >= patternLength)
                    throw error("Unclosed character class");
                break;
            case ']':
                firstInClass = false;

                if (prev != null) {
                    if (consume)
                        next();

                    return prev;
                }
                break;
            default:
                firstInClass = false;
                break;
        }
        node = range(bits);

        if (include) {
            if (prev == null) {
                prev = node;
            } else {
                if (prev != node)
                    prev = union(prev, node);
            }
        } else {
            if (prev == null) {
                prev = node.complement();
            } else {
                if (prev != node)
                    prev = setDifference(prev, node);
            }
        }
        ch = peek();
    }
}

Глядя на код в case '[': из switch заявление и код после switch заявление:

• node переменная хранит результат разбора модуля (автономный символ, диапазон символов, класс сокращенных символов, класс символов POSIX/Unicode или вложенный класс символов)
• prev переменная хранит результат компиляции и всегда обновляется сразу после компиляции модуля в node,

Поскольку локальная переменная boolean include, который записывает, отменяется ли класс символов, никогда не передается ни в один вызов метода, на него можно воздействовать только в этом методе. И единственное место include читается и обрабатывается после switch заявление.

Пост в стадии строительства

Answer 2

Согласно JavaDoc, классы вложения страниц производят объединение двух классов, что делает невозможным создание пересечения с использованием этой записи:

Чтобы создать объединение, просто вложите один класс в другой, например, [0-4[6-8]]. Этот конкретный союз создает один класс символов, который соответствует числам 0, 1, 2, 3, 4, 6, 7 и 8.

Для создания пересечения вам придется использовать &&:

Чтобы создать отдельный класс символов, соответствующий только символам, общим для всех его вложенных классов, используйте &&, как в [0-9&&[345]]. Это конкретное пересечение создает один класс символов, соответствующий только числам, общим для обоих классов символов: 3, 4 и 5.

Последняя часть вашей проблемы до сих пор для меня загадка. Союз [^2] а также [^0-9] действительно должно быть [^2], так [^2[^0-9]] ведет себя как ожидалось. [^[^0-9]2] вести себя как [^0-9] действительно странно, хотя.