Программа зависания регулярных выражений (100% использование ЦП)

Ответ 1

Другой классический случай катастрофического обратного отслеживания.

У вас есть вложенные кванторы, которые вызывают проверку гигантского количества перестановок, когда регулярное выражение приходит в : в вашей строке ввода, которая не является частью вашего класса символов (если вы используете метод .matches()),.

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

^([^:]+)+$

и эта строка:

1234:

Механизм регулярных выражений должен проверять

1234    # no repetition of the capturing group
123 4   # first repetition of the group: 123; second repetition: 4
12 34   # etc.
12 3 4 
1 234
1 23 4
1 2 34
1 2 3 4

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

Как вы можете это решить?

Вы можете запретить регулярное выражение с возвратом с помощью притяжательных квантификаторов:

^([A-Za-z0-9_.&,-]++\\s*+)+

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

Edit:

Несколько измерений:

В строке "was wrong :-)" для вычисления несоответствия требуется выполнить шаги RegexBuddy 862.
Для "me was wrong :-)" это 1,742 шага.
Для "gave me was wrong :-)", 14014 шагов.
Для "he gave me was wrong :-)", 28 046 шагов.
Для "one he gave me was wrong :-)", 112 222 шагов.
Для "first one he gave me was wrong :-)", > 1,000,000 шагов.

Ответ 2

Во-первых, вам нужно понять, что ваши регулярные выражения НЕ МОГУТ соответствовать введенной строке ввода. Строки содержат числовые символы ('<' '>' '/' ':' и ')'), которые не являются символами слова.

Так почему это так долго?

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

Вот что говорит ваше регулярное выражение:

• Один или несколько символов слова
• Вслед за нулевым или большим количеством символов пробела
• Повторите предыдущие 2 шаблона столько раз, сколько захотите.

Проблема состоит в том, что часть "ноль или больше пробелов". В первый раз совпадение будет соответствовать всем до первого неожиданного символа (т.е. '<'). Затем он отступит немного и повторит попытку с другой альтернативой... которая включает в себя "нулевые пробелы" перед последней буквой, а затем, когда это не удастся, оно переместит "нулевые пространства" назад на одну позицию.

Проблема заключается в том, что для String с N непространственными символами существует N разные места, которые могут быть сопоставлены с "нулевыми пространствами" и что делает 2^N различными комбинациями. Это быстро превращается в ОГРОМНОЕ число, когда N растет, а конечный результат трудно отличить от бесконечного цикла.

Ответ 3

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

^[A-Za-z0-9_.&,-]+(?:\s+[A-Za-z0-9_.&,-]+)*$

Теперь существует только один "путь", который движок регулярных выражений может принимать через строку. Если перед достижением конца пробегает символ, который соответствует [A-Za-z0-9_.&,-], а следующий символ не соответствует \s, он немедленно сработает. Если он достигнет конца, все еще совпадающий с символами пробела, он терпит неудачу, потому что для каждого пробега пробела требуется совместить по крайней мере один символ без пробелов.

Если вы хотите убедиться, что есть только один пробельный символ, разделяющий прогоны без пробелов, просто удалите квантификатор из \s+:

^[A-Za-z0-9_.&,-]+(?:\s[A-Za-z0-9_.&,-]+)*$

Если вам все равно, где пробел относится к не-пробелу, просто сопоставьте их всем с тем же классом символов:

^[A-Za-z0-9_.&,\s-]+$

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

И, конечно, поскольку вы создаете регулярное выражение в форме строкового литерала Java, вы должны написать:

"^[A-Za-z0-9_.&,-]+(?:\\s+[A-Za-z0-9_.&,-]+)*$"

или

"^[A-Za-z0-9_.&,-]+(?:\\s[A-Za-z0-9_.&,-]+)*$"

или

"^[A-Za-z0-9_.&,\\s-]+$"

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