Регулярное выражение для сопоставления вложенных строк конечной глубины - медленное, аварийное поведение

Сегодня я писал некоторые регулярные выражения в своем текстовом редакторе (Sublime), пытаясь быстро найти определенные сегменты исходного кода, и это требовало немного творческого подхода, потому что иногда вызов функции мог содержать больше вызовов функций. Например, я искал селекторы jQuery:

$("div[class='should_be_using_dot_notation']");

$(escapeJQSelector("[name='crazy{"+getName(object)+"}']"));

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

Я достаточно сведущ в теории, чтобы знать, что этот вид синтаксического анализа - именно то, для чего нужен контекстно-свободный синтаксический анализатор, и что построение регулярного выражения может высосать больше памяти и времени (возможно, в показательной, а не 0 (п ^3) мода). Однако я не ожидаю увидеть такую ​​функцию в моем текстовом редакторе или веб-браузере в ближайшее время, и я просто хотел пропустить с большим неприятным регулярным выражением.

Начиная с этого (это соответствует нулевым уровням вложенных паренов, а не тривиальным пустым):

\$\([^)(]+?\)

Вот как выглядит одноуровневое вложенное число, которое я придумал:

\$\(((\([^)(]*\))|[^)(])+?\)

Разбивая это:

\$\(                   begin text
    (                  groups the contents of the $() call
        (\(            groups a level 1 nested pair of parens
            [^)(]*     only accept a valid pair of parens (it shall contain anything but parens)
        \))            close level 1 nesting
        |              contents also can be
        [^)(]          anything else that also is not made of parens
    )+?                not sure if this should be plus or star or if can be greedy (the contents are made up of either a level 1 paren group or any other character)
\)                     end

Это сработало отлично! Но мне нужен еще один уровень вложенности.

Я начал печатать двухуровневое вложенное выражение в моем редакторе, и оно начинало останавливаться на 2-3 секунды, когда я вставлял *"S.

Поэтому я отказался от этого и перешел на regextester.com, и совсем скоро вся вкладка браузера была заморожена.

У меня вопрос двоякий.

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

  2. Почему синтаксический анализ регулярных выражений блокирует или останавливает так долго?

Я понимаю, что линейное время O(n) для n, где n - длина ввода для выполнения регулярного выражения (то есть для моих тестовых строк). Но в системе, где он перекомпилирует регулярное выражение каждый раз, когда я набираю в нем нового символа, что может привести к его зависанию? Обязательно ли это ошибка в коде регулярных выражений (надеюсь, что нет, я думал, что Javascript регулярное выражение impl было довольно солидным)? Часть моих рассуждений о переходе к тестеру регулярных выражений, отличному от моего редактора, заключалась в том, что я больше не буду запускать его (при каждом нажатии клавиши) для всех ~2000 строк исходного кода, но это не помешало всей среде заблокироваться, поскольку я отредактировал мое регулярное выражение. Было бы разумно, если бы каждый символ, измененный в регулярном выражении, соответствовал некоторому простому преобразованию в DFA, которое представляет это выражение. Но, похоже, это не так. Если есть определенные экспоненциальные временные или пространственные последствия для добавления звезды в регулярное выражение, это может объяснить это поведение супер-медленного обновления.

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

Источник

2 ответа

Для совпадения с произвольным числом вложенных (), имея только одну пару на каждом уровне вложенности, вы можете использовать следующее, изменяя 2 на любое количество вложенных () вам требуется

/(?:\([^)(]*){2}(?:[^)(]*\)){2}/

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

Источник

Um. Итак, никто не хочет писать ответ, но в основном ответ здесь

Откат

Это может вызвать экспоненциальное время выполнения, когда вы делаете не жадные вещи.

Ответ на первую часть моего вопроса:

Выражение с двумя вложениями выглядит следующим образом:

\$\(((\(((\([^)(]*\))|[^)(])*\))|[^)(])*\)

Преобразование для создания следующего вложенного выражения заключается в замене экземпляров [^)(]* с ((\([^)(]*\))|[^)(])*или, в качестве мета-регулярного выражения (где раздел для замены не требуется экранировать):

s/\[^\)\(\]\*/((\([^)(]*\))|[^)(])*/

Это концептуально просто: в выражении, соответствующем N уровням вложения, если мы заменим часть, которая запрещает большее вложение, чем-то, что соответствует еще одному уровню вложения, мы получим выражение для N+1 уровней вложения!

Источник
Другие вопросы по тегам