На этом регулярном выражении не должно происходить катастрофического возврата - PullRequest
Новая
       8

На этом регулярном выражении не должно происходить катастрофического возврата

2 голосов
/ 11 сентября 2011

Может кто-нибудь объяснить, почему движок Java в этом регулярном выражении переходит в катастрофический режим возврата?Как я могу судить, каждое чередование является взаимоисключающим с любым другим чередованием. 

^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*|
\"(?:[^\"]+|\"\")+\"|
'(?:[^']+|'')+')

Текст: 'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

Добавление собственнического соответствия к некоторым чередованиям устраняет проблему, но японятия не имею, почему - Java regex lib должна быть чрезвычайно глючной, чтобы возвращаться к взаимоисключающим ветвям. 

 ^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*|
 \"(?:[^\"]++|\"\")++\"|
 '(?:[^']++|'')++')

Ответы [ 3 ]

17 голосов
/ 11 сентября 2011

РЕДАКТИРОВАТЬ: Добавлена ​​Java-версия в конце - несмотря на то, что она изначально неуклюжа, нечитаема и не поддерживается.

¡Больше никаких уродливых узоров!

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *} * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *} * от. * * * * секунда , что вам нужно сделать, это профилировать это, чтобы увидеть, что он на самом деле делает.

Это означает, что, как минимум, вам необходимо скомпилировать его в режиме Pattern.COMMENTS (или префикс "(?x)"), а затем добавить пробел, чтобы освободить пространство для визуального локтя. Насколько я могу судить, шаблон, с которым вы фактически пытаетесь сопоставить, таков: 

^ 
(?: [^'"\s~:/@\#|^&\[\]()\\{}]    # alt 1: unquoted
    [^"\s~:/@\#|^&\[\]()\\{}] *
  | " (?: [^"]+ | "" )+ "        # alt 2: double quoted
  | ' (?: [^']+ | '' )+ '        # alt 3: single quoted
)

Как вы видите, я ввел как вертикальные, так и горизонтальные пробелы в тех местах, где мог, чтобы направить взгляд и ум как своего рода когнитивное чанкинг. Я также удалил все твои посторонние слэши. Все это либо явные ошибки, либо обфускаторы, которые только смущают читателя.

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

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

Я также заметил, что в вашей первой альтернативе есть два слегка отличных (отрицательных) класса символов в квадратных скобках. Во втором отсутствует исключение из одинарных кавычек, которое можно увидеть в первом. Это намеренно? Даже если это так, я считаю это слишком большим дублированием для моих вкусов; некоторые или все из них должны быть в переменной, чтобы вы не рисковали обновлять проблемы когерентности.

Профилирование

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

Java-класс Pattern в настоящее время не способен сделать это, хотя я довольно долго об этом говорил с нынешним хранителем кода в OraSun, и он очень хочет добавить эту возможность в Java и думает, что он точно знает, как сделать это. Он даже прислал мне прототип, который выполняет первую часть: компиляцию. Поэтому я ожидаю, что он будет доступен на днях.

Тем временем давайте обратимся вместо этого к инструменту, в котором регулярные выражения являются неотъемлемой частью собственно языка программирования, а не чем-то вроде неловкой запоздалой мысли. Хотя этому критерию соответствуют несколько языков, ни в одном из них искусство сопоставления с образцом не достигло уровня сложности, наблюдаемого в Perl.

Вот тогда эквивалентная программа. 

#!/usr/bin/env perl
use v5.10;      # first release with possessive matches
use utf8;       # we have utf8 literals
use strict;     # require variable declarations, etc
use warnings;   # check for boneheadedness

my $match = qr{
    ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}]
          [^"\s~:/@\#|^&\[\]()\\{}] *
        | " (?: [^"]+ | "" )+ "
        | ' (?: [^']+ | '' )+ '
    )
}x;

my $text = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])";

my $count = 0;

while ($text =~ /$match/g) {
    print "Got it: $&\n";
    $count++;
}

if ($count == 0) {
    print "Match failed.\n";
}

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

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

Оба из них управляются с помощью 

use re "debug";

прагма, которая также может быть указана в командной строке через -Mre=debug. Это то, что мы сделаем здесь, чтобы избежать взлома исходного кода.

Regex Compilation

Прагма отладки re обычно показывает как компиляцию шаблона, так и его выполнение. Чтобы отделить их, мы можем использовать параметр Perl «только для компиляции», -c, который не пытается выполнить скомпилированную программу. Таким образом, все, на что мы смотрим - это скомпилированный шаблон. Делать это производит следующие 36 строк вывода: 

$ perl -c -Mre=debug /tmp/bt
Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (79)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (79)
        <"> (29)
  29:     CURLYX[0] {1,32767} (49)
  31:       BRANCH (44)
  32:         PLUS (48)
  33:           ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  44:       BRANCH (FAIL)
  45:         EXACT <""> (48)
  47:       TAIL (48)
  48:     WHILEM[1/2] (0)
  49:     NOTHING (50)
  50:     EXACT <"> (79)
        <'> (55)
  55:     CURLYX[0] {1,32767} (75)
  57:       BRANCH (70)
  58:         PLUS (74)
  59:           ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  70:       BRANCH (FAIL)
  71:         EXACT <''> (74)
  73:       TAIL (74)
  74:     WHILEM[2/2] (0)
  75:     NOTHING (76)
  76:     EXACT <'> (79)
  78: TAIL (79)
  79: END (0)
anchored(BOL) minlen 1 
/tmp/bt syntax OK
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

Как видите, компиляцияПрограмма regex написана на чем-то вроде «языка ассемблера regex». (Это также выглядит очень похоже на то, что демонстрирует мне продемонстрированный мне прототип Java, так что я думаю, что однажды вы тоже увидите подобные вещи в Java.) Все детали не важны для этого, но я укажу, что инструкция на узле 2 - это BRANCH, который, в случае неудачи, выполняет ветвь 26, другой BRANCH. Этот второй BRANCH, который является единственной другой частью программы регулярных выражений, состоит из одного узла TRIE-EXACT, потому что он знает, что альтернативы имеют разные начальные литеральные строки. Что происходит с в этих двух ветвях три мы обсудим в ближайшее время.

Регулярное выполнение

Теперь пришло время посмотреть, что происходит, когда он запускается. Текстовая строка, которую вы используете, вызывает довольно существенное количество возвратов, что означает, что у вас будет большой объем выходных данных, прежде чем он, наконец, потерпит неудачу. Сколько выходной? Ну, это много: 

$ perl -Mre=debug /tmp/bt 2>&1 | wc -l
9987

Я предполагаю, что 10000 шагов - это то, что вы имели в виду под "катастрофическим режимом возврата". Давайте посмотрим, что мы не можем свести это к чему-то более понятному. Ваша входная строка имеет длину 61 символ. Чтобы лучше видеть, что происходит, мы можем обрезать его до 'pão, что составляет всего 4 символа. (Ну, в NFC, это пять кодовых точек в NFD, но здесь это ничего не меняет). В результате получается 167 строк: 

$ perl -Mre=debug /tmp/bt 2>&1 | wc -l
167

Фактически, вот строки профилирования выполнения регулярных выражений (компиляция плюс), которые вы получаете, когда длина вашей строки так много символов: 

chars   lines   string
    1     63   ‹'›
    2     78   ‹'p›  
    3    109   ‹'pã›
    4    167   ‹'pão› 
    5    290   ‹'pão ›
    6    389   ‹'pão d›
    7    487   ‹'pão de›
    8    546   ‹'pão de ›
    9    615   ‹'pão de a›
   10    722   ‹'pão de aç›
  ....
   61   9987   ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])›

Давайте посмотрим на выходные данные отладки, когда строка состоит из четырех символов 'pão. На этот раз я пропустил часть компиляции, чтобы показать только часть исполнения: 

$ perl -Mre=debug /tmp/bt
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o"
UTF-8 string...
   0 <> <'p%x{e3}o>  |  1:BOL(2)
   0 <> <'p%x{e3}o>  |  2:BRANCH(26)
   0 <> <'p%x{e3}o>  |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                            failed...
   0 <> <'p%x{e3}o>  | 26:BRANCH(78)
   0 <> <'p%x{e3}o>  | 27:  TRIE-EXACT["'](79)
   0 <> <'p%x{e3}o>  |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o>  |      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                            got 1 possible matches
                            TRIE matched word #2, continuing
                            only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o>  | 55:  CURLYX[0] {1,32767}(75)
   1 <'> <p%x{e3}o>  | 74:    WHILEM[2/2](0)
                              whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o>  | 57:      BRANCH(70)   1 <'> <p%x{e3}o>          | 58:        PLUS(74)
                                  ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:            BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                        failed...
   5 <'p%x{e3}o> <>  | 70:            BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:            NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   4 <'p%x{e3}> <o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:            BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                  BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                              failed...
   5 <'p%x{e3}o> <>  | 70:                  BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                  NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
                                        failed...
   4 <'p%x{e3}> <o>  | 70:            BRANCH(73)
   4 <'p%x{e3}> <o>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   4 <'p%x{e3}> <o>  | 75:            NOTHING(76)
   4 <'p%x{e3}> <o>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   2 <'p> <%x{e3}o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   2 <'p> <%x{e3}o>  | 57:            BRANCH(70)
   2 <'p> <%x{e3}o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 2 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                  BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                              failed...
   5 <'p%x{e3}o> <>  | 70:                  BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                  NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
   4 <'p%x{e3}> <o>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:                  BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                      WHILEM[2/2](0)
                                                whilem: matched 3 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                        BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                          PLUS(74)
                                                    ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647.
..
                                                    failed...
   5 <'p%x{e3}o> <>  | 70:                        BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                          EXACT <''>(74)
                                                    failed...
                                                  BRANCH failed...
                                                whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                        NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                        EXACT <'>(79)
                                                  failed...
                                                failed...
                                              failed...
   4 <'p%x{e3}> <o>  | 70:                  BRANCH(73)
   4 <'p%x{e3}> <o>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   4 <'p%x{e3}> <o>  | 75:                  NOTHING(76)
   4 <'p%x{e3}> <o>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
                                        failed...
   2 <'p> <%x{e3}o>  | 70:            BRANCH(73)
   2 <'p> <%x{e3}o>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   2 <'p> <%x{e3}o>  | 75:            NOTHING(76)
   2 <'p> <%x{e3}o>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
                                  failed...
   1 <'> <p%x{e3}o>  | 70:      BRANCH(73)
   1 <'> <p%x{e3}o>  | 71:        EXACT <''>(74)
                                  failed...
                                BRANCH failed...
                              failed...
                            failed...
                          BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

То, что вы видите там, это то, что три быстро переходит к узлу 55, который является последним из трех вариантов после он соответствует одинарной кавычке, потому что ваша целевая строка начинается с одинарной кавычки , Вот это: 

  | ' (?: [^']+ | '' )+ '        # alt 3: single quoted

Узел 55 - это трия: 

        <'> (55)
  55:     CURLYX[0] {1,32767} (75)
  57:       BRANCH (70)
  58:         PLUS (74)
  59:           ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  70:       BRANCH (FAIL)
  71:         EXACT <''> (74)

А вот трассировка выполнения, показывающая, где происходит ваш катастрофический откат: 

   1 <'> <p%x{e3}o>  | 74:    WHILEM[2/2](0)
                              whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o>  | 57:      BRANCH(70)
   1 <'> <p%x{e3}o>  | 58:        PLUS(74)
                                  ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:            BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                        failed...
   5 <'p%x{e3}o> <>  | 70:            BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:            NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   4 <'p%x{e3}> <o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:            BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767

Узел 58 сожрал все 3 оставшихся символа в строке, pão. Это привело к сбою завершающего точного совпадения одной кавычки. Поэтому он пытается использовать ваш альтернативный вариант, который представляет собой пару одинарных кавычек, но также не дает результатов.

Именно в этот момент я должен подвергнуть сомнению вашу модель. Не должен 

' (?: [^']+ | '' )+ '

неужели просто так? 

' [^']* '

То, что происходит, заключается в том, что существует множество способов вернуть его назад в поисках чего-то, что логически никогда не может произойти. У вас есть вложенный квантификатор, и это вызывает все виды безнадежной и бессмысленной занятой работы.

Если мы поменяем местами, упростим шаблон в этом: 

^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] +
    | " [^"]* "
    | ' [^']* '
  )

Теперь он выдает одинаковое количество строк трассировки независимо от размера входной строки: только 40, включая компиляцию. Наблюдайте за компиляцией и выполнением всей строки: 

Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (61)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (61)
        <"> (29)
  29:     STAR (41)
  30:       ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  41:     EXACT <"> (61)
        <'> (46)
  46:     STAR (58)
  47:       ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  58:     EXACT <'> (61)
  60: TAIL (61)
  61: END (0)
anchored(BOL) minlen 1 
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mast
ercard platinum S"...
UTF-8 string...
   0 <> <'p%x{e3}o >  |  1:BOL(2)
   0 <> <'p%x{e3}o >  |  2:BRANCH(26)
   0 <> <'p%x{e3}o >  |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                             failed...
   0 <> <'p%x{e3}o >  | 26:BRANCH(60)
   0 <> <'p%x{e3}o >  | 27:  TRIE-EXACT["'](61)
   0 <> <'p%x{e3}o >  |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o d> |      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                             got 1 possible matches
                             TRIE matched word #2, continuing
                             only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o d> | 46:  STAR(58)
                             ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647...
                             failed...
                           BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

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

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

   ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] +    # alt 1: unquoted
       | " (?: [^"]++ | "" )++ "        # alt 2: double quoted
       | ' (?: [^']++ | '' )++ '        # alt 3: single quoted
     )

Профиль компиляции плюс выполнения выглядит следующим образом: 

Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (95)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (95)
        <"> (29)
  29:     SUSPEND (58)
  31:       CURLYX[0] {1,32767} (55)
  33:         BRANCH (50)
  34:           SUSPEND (54)
  36:             PLUS (48)
  37:               ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  48:             SUCCEED (0)
  49:           TAIL (53)
  50:         BRANCH (FAIL)
  51:           EXACT <""> (54)
  53:         TAIL (54)
  54:       WHILEM[1/2] (0)
  55:       NOTHING (56)
  56:       SUCCEED (0)
  57:     TAIL (58)
  58:     EXACT <"> (95)
        <'> (63)
  63:     SUSPEND (92)
  65:       CURLYX[0] {1,32767} (89)
  67:         BRANCH (84)
  68:           SUSPEND (88)
  70:             PLUS (82)
  71:               ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  82:             SUCCEED (0)
  83:           TAIL (87)
  84:         BRANCH (FAIL)
  85:           EXACT <''> (88)
  87:         TAIL (88)
  88:       WHILEM[2/2] (0)
  89:       NOTHING (90)
  90:       SUCCEED (0)
  91:     TAIL (92)
  92:     EXACT <'> (95)
  94: TAIL (95)
  95: END (0)
anchored(BOL) minlen 1 
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mastercard platinum S"...
UTF-8 string...
   0 <> <'p%x{e3}o > |  1:BOL(2)
   0 <> <'p%x{e3}o > |  2:BRANCH(26)
   0 <> <'p%x{e3}o > |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                            failed...
   0 <> <'p%x{e3}o > | 26:BRANCH(94)
   0 <> <'p%x{e3}o > | 27:  TRIE-EXACT["'](95)
   0 <> <'p%x{e3}o > |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o d>|      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                            got 1 possible matches
                            TRIE matched word #2, continuing
                            only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o d>| 63:  SUSPEND(92)
   1 <'> <p%x{e3}o d>| 65:    CURLYX[0] {1,32767}(89)
   1 <'> <p%x{e3}o d>| 88:      WHILEM[2/2](0)
                                whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o d>| 67:        BRANCH(84)
   1 <'> <p%x{e3}o d>| 68:          SUSPEND(88)
   1 <'> <p%x{e3}o d>| 70:            PLUS(82)
                                      ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647...
  64 <NTABILIDAD])> <| 82:              SUCCEED(0)
                                        subpattern success...
  64 <NTABILIDAD])> <| 88:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
  64 <NTABILIDAD])> <| 67:            BRANCH(84)
  64 <NTABILIDAD])> <| 68:              SUSPEND(88)
  64 <NTABILIDAD])> <| 70:                PLUS(82)
                                          ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                          failed...
                                        failed...
  64 <NTABILIDAD])> <| 84:            BRANCH(87)
  64 <NTABILIDAD])> <| 85:              EXACT <''>(88)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
  64 <NTABILIDAD])> <| 89:            NOTHING(90)
  64 <NTABILIDAD])> <| 90:            SUCCEED(0)
                                      subpattern success...
  64 <NTABILIDAD])> <| 92:  EXACT <'>(95)
                failed...
              BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

Мне все еще нравится мое решение. Это короче.

EDIT

Похоже, что Java-версия действительно делает в 100 раз больше шагов, чем Perl-версия идентичного шаблона, и я понятия не имею, почему - за исключением того, что компилятор регулярного выражения Perl примерно в 100 раз умнее при оптимизации, чем регулярное выражение Java компилятор, который вообще ничего не говорит и должен.

Вот эквивалент Java program.Я удалил ведущую привязку, чтобы мы могли правильно зацикливаться. 

$ cat java.crap
import java.util.regex.*;

public class crap {

public static void
main(String[ ] argv) {
    String input = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])";
    String regex = "\n"
                + "(?: [^'\"\\s~:/@\\#|^&\\[\\]()\\\\{}]    # alt 1: unquoted         \n"
                + "    [^\"\\s~:/@\\#|^&\\[\\]()\\\\{}] *                     \n"
                + "  | \" (?: [^\"]++ | \"\" )++ \"       # alt 2: double quoted   \n"
                + "  | ' (?: [^']++ | '' )++ '       # alt 3: single quoted   \n"
                + ")                                                          \n"
                ;
    System.out.printf("Matching ‹%s› =~ qr{%s}x\n\n", input, regex);

    Pattern regcomp = Pattern.compile(regex, Pattern.COMMENTS);
    Matcher regexec = regcomp.matcher(input);

    int count;
    for (count = 0; regexec.find(); count++) {
       System.out.printf("Found match: ‹%s›\n", regexec.group());
    }
    if (count == 0) {
        System.out.printf("Match failed.\n");
    }
  }
}

При запуске это выдает: 

$ javac -encoding UTF-8 crap.java && java -Dfile.encoding=UTF-8 crap
Matching ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])› =~ qr{
(?: [^'"\s~:/@\#|^&\[\]()\\{}]    # alt 1: unquoted         
    [^"\s~:/@\#|^&\[\]()\\{}] *                     
  | " (?: [^"]++ | "" )++ "       # alt 2: double quoted   
  | ' (?: [^']++ | '' )++ '       # alt 3: single quoted   
)                                                          
}x

Found match: ‹pão›
Found match: ‹de›
Found match: ‹açúcar›
Found match: ‹itaucard›
Found match: ‹mastercard›
Found match: ‹platinum›
Found match: ‹SUSTENTABILIDAD›

Как вы можете видеть, сопоставление с образцом в Java имеетоб этом можно сказать довольно много, абсолютно ни один из которых не пройдет мимо полиции.Это просто королевская боль в заднице.

6 голосов
/ 11 сентября 2011

Я должен признать, что это меня тоже удивило, но я получаю тот же результат в RegexBuddy: он прекращает попытки после миллиона шагов.Я знаю, что предупреждения о катастрофическом обратном отслеживании имеют тенденцию сосредотачиваться на вложенных квантификаторах, но в моем опыте чередование, по крайней мере, столь же опасно.На самом деле, если я изменю последнюю часть вашего регулярного выражения с этого: 

'(?:[^']+|'')+'

... на это: 

'(?:[^']*(?:''[^']*)*)'

... это завершится неудачей всего за одиннадцать шагов.Это пример техники "развернутой петли" Friedl , которую он ломает следующим образом: 

opening normal * ( special normal * ) * closing
   '     [^']        ''     [^']           '

Вложенные звезды безопасны, если:

  1. special и normal никогда не могут совпадать с одним и тем же,
  2. special всегда совпадает хотя бы с одним символом, а
  3. special является атомарным (должно бытьтолько один способ его сопоставления).

Регулярное выражение затем не сможет совпадать с минимальным возвратом, а преуспеет без возврата.Чередующаяся версия, с другой стороны, почти гарантированно откатится назад, и там, где никакое совпадение невозможно, она быстро выходит из-под контроля по мере увеличения длины целевой строки.Если он не чрезмерно откатывается в некоторых вариантах, это потому, что в него встроены оптимизации, специально предназначенные для решения этой проблемы - что пока делают очень немногие варианты.

0 голосов
/ 11 сентября 2011

Может кто-нибудь объяснить, почему движок Java в этом регулярном выражении переходит в катастрофический режим?

Для строки: 

'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

Кажется, что эта частьВозникает проблема с регулярным выражением: 

'(?:[^']+|'')+'

Сопоставление с первым ', затем не с совпадением с закрывающим ' и, таким образом, обратное отслеживание всех комбинаций вложенных квантификаторов.

Если вы разрешитеregex для возврата, он будет возвращаться (при неудаче).Используйте атомарные группы и / или собственнические квантификаторы, чтобы предотвратить это.

Кстати, вам не нужно большинство выходов в этом регулярном выражении.Единственное, что вам (возможно) нужно избегать в классах персонажей ([]) - это символы ^-].Но обычно вы можете расположить их так, чтобы их не нужно было убегать.Конечно, \ и что бы вы ни указали, строку, с которой вы все еще должны быть (двойной), экранировать. 

"^(?:[^]['\"\\s~:/@#|^&(){}\\\\][^][\"\s~:/@#|^&(){}\\\\]*|\"(?:[^\"]++|\"\")++\"|'(?:[^']++|'')++')"
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...