Regex: определить, могут ли два регулярных выражения совпадать для одного и того же ввода?
Конечные точки службы ASP.NET и WCF JSON фактически переносят их JSON в объект со свойством «d», чтобы обойти тонкий потенциальный недостаток безопасности при использовании JSON
blockquote>Phil Haack's сообщение на этом: http://haacked.com/archive/2008/11/20/anatomy-of-a-subtle-json-vulnerability.aspx
Это было введено из ASP.NET3.5. Если вы хотите, чтобы
msgработал в обеих структурах до и после 3.5, просто попробуйте этот небольшой хак.var data = msg.hasOwnProperty("d") ? msg.d : msg;Courtesy Dave Ward: Никогда не беспокоиться об ASP.NET AJAX .d снова
3 ответа
Здесь нет проблемы с остановкой. Все, что вам нужно, это вычислить, не пусто ли пересечение ^ xy1 \ d и [^ \ d] \ d2 $ .
Я не могу дать вам здесь алгоритм, но вот два обсуждения метода генерации пересечения без использования построения DFA:
А еще есть RAGEL
, который тоже может вычислять пересечение регулярных выражений.
ОБНОВЛЕНИЕ: Я только что попробовал Ragel с регулярным выражением OP. Ragel может сгенерировать "точечный" файл для graphviz из конечного автомата, что потрясающе. Пересечение регулярного выражения OP выглядит так в синтаксисе Рагеля:
('xy1' digit any*) & (any* ^digit digit '2')
и имеет следующий конечный автомат:
В то время как пустое пересечение:
('xy1' digit any*) & ('q' any* ^digit digit '2')
выглядит так:
Итак, если все остальное терпит неудачу , то вы все равно можете заставить Ragel вычислить пересечение и проверить, выводит ли он пустой конечный автомат, сравнивая сгенерированный "точечный" файл.
Проблема может быть переформулирована как «ли языки, описываемые двумя или более регулярными выражения имеют непустое пересечение "?
Если вы ограничите вопрос чистыми регулярными выражениями (без обратных ссылок, просмотра вперед, поиск назад или другие функции, позволяющие распознавать контекстно-зависимые или более сложные языков), вопрос по крайней мере разрешим. Обычные языки закрыты пересечение, и есть алгоритм, который принимает два регулярных выражения в качестве входных данных и за конечное время создает DFA, который распознает пересечение.
Каждое регулярное выражение может быть преобразовано в недетерминированный конечный автомат, а затем к детерминированному конечному автомату. Пара DFA может быть преобразована к DFA, который распознает пересечение. Если есть путь от начальное состояние в любое принимающее состояние этого последнего DFA, пересечение не пусто («конфликт», используя вашу терминологию).
К сожалению, существует вероятность экспоненциального разрушения при преобразовании исходной NFA. в DFA, поэтому проблема быстро становится невыполнимой на практике, поскольку размер входные выражения растут.
И если расширения чистых регулярных выражений разрешены, все ставки отключены - такие языки больше не закрываются при пересечении, поэтому эта конструкция не будет Работа.
Да, я думаю, это разрешимо: вместо того, чтобы думать о регулярных выражениях как о совпадающих строках, вы также можете думать о них как о генерирующих строках. То есть все строки, которые им будут соответствовать.
Пусть [R] будет набором строк, сгенерированных регулярным выражением R. Затем, учитывая регулярные выражения R и T, мы могли бы попытаться сопоставить T с [R]. То есть [R] соответствует T, если в [R] есть строка, которая соответствует T.
Это должно быть возможно преобразовать в алгоритм, в котором [R] лениво строится по мере необходимости: где обычное сопоставление регулярных выражений будет пытаться чтобы сопоставить следующий символ из входной строки и затем перейти к следующему символу в строке, модифицированный алгоритм будет проверять, может ли конечный автомат, соответствующий входному регулярному выражению, сгенерировать соответствующий символ в его текущем состоянии, а затем переходит к 'все следующие состояний одновременно.