Проверьте, будет ли данное регулярное выражение соответствовать чему-либо

Question

Можно ли проверить, будет ли данное регулярное выражение соответствовать любой строке? В частности, я ищу функцию matchesEverything($regex), которая возвращает true, если $regex будет соответствовать любой строке.

Я полагаю, что это эквивалентно запросу: «Если задано регулярное выражение r, существует ли строка, которая не соответствует r?» и я не думаю, что это разрешимо, не помещая границы на множество «всех строк». I.e., если я предполагаю, что строки никогда не будут содержать «блаббаль», тогда я могу просто проверить, соответствует ли r «бла-бла». Но что, если таких границ нет? Мне интересно, можно ли решить эту проблему, если регулярное выражение r эквивалентно .*.

Answer 1

Это не точно ответить на ваш вопрос, но мы надеемся, объясняет немного, почему простой ответ трудно найти:

Во-первых, термин «регулярное выражение» немного мутная, так что просто уточнить, мы имеют:

• «Строгие» регулярные выражения, эквивалентные детерминированным конечным автоматам (DFA).
• Perl-совместимые регулярные выражения (PCRE), которые добавляют кучу колоколов и свистов, таких как lookaheads, backreferences и т. Д. Они реализованы и на других языках, таких как Python и Java.
• Фактические регулярные выражения Perl, которые могут стать еще более сумасшедшими, включая произвольный код Perl, через конструкцию ?{...}.

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

Я не думаю, что PCRE является Turing-complete (хотя я не знаю - см. Этот вопрос тоже: Are Perl regexes turing complete?). Если бы это было так, то я думаю, как прокомментировал Джим Гаррисон, это в основном проблема с остановкой. Это не так просто превратить их в DFA, либо сделать этот метод бесполезным ...

У меня нет ответа для PCRE, но имейте в виду, что вышеупомянутые конструкции (обратные ссылки и т. Д.), Полагаю, что это будет довольно сложно. Хотя я не решаюсь сказать «невозможно».

Подлинное Perl регулярное выражение с ?{...} в нем определенно Turing-complete, поэтому есть драконы, и я думаю, вам не повезло.