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

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

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

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

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

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

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

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

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

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

Разрушение:

\$\(                   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 секунд в то время, когда я вставлял *.

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

Мой вопрос в два раза.

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

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

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

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

Ответы

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

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

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