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

Я разрабатываю приложение, в котором пользователи вводят регулярное выражение в качестве критерия фильтра, однако я не хочу, чтобы люди (легко) могли вводить .* (т.е. соответствовать чему-либо). Проблема в том, что если я просто использую if (expression == ".*"), тогда это можно легко обойти, введя что-то вроде .*.*.

Кто-нибудь знает тест, который может взять кусок регулярного выражения и посмотреть, есть ли в основном .*, но в несколько более сложной форме?

Мои мысли:

Я мог видеть, является ли выражение одним или несколькими повторениями .* (т.е. если оно соответствует (\.\*)+ (цитаты/экраны могут быть не совсем точными, но вы получаете идею). это может быть и другие формы написания глобального соответствия (например, с $ и ^), которые являются слишком исчерпывающими, чтобы даже думать о начале, сдавать тест.
Я мог бы протестировать с ним несколько случайно сгенерированных строк и предположить, что если все они пройдут, пользователь ввел глобально соответствующий шаблон. Проблема с этим подходом заключается в том, что могут быть ситуации, когда выражение достаточно плотно, и я просто выбираю плохие строки для соответствия.

Мысли, кто-нибудь?

(FYI, приложение находится на Java, но я думаю, что это скорее алгоритмический вопрос, чем один для определенного языка.)

Ответ 1

Да, есть способ. Это связано с преобразованием регулярного выражения в каноническое представление FSM. См. http://en.wikipedia.org/wiki/Regular_expression#Deciding_equivalence_of_regular_expressions

Скорее всего, вы найдете опубликованный код, который будет работать для вас. Если нет, подробные шаги описаны здесь: http://swtch.com/~rsc/regexp/regexp1.html

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

Ответ 2

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

Вот несколько примеров, которые бы совпадали с .* (они будут дополнительно соответствовать символам новой строки)

/[\s\S]*/
/(\w|\W)*/
/(a|[^a])*/
/(a|b|[^ab])*/

Итак, я предполагаю, что ваша идея 2 будет намного легче достичь.

Ответ 3

Спасибо всем,

Я пропустил тестирование для записи эквивалентности в википедии, что было интересно.

Мои воспоминания о DFA (я, кажется, помню, что должен был доказать или хотя бы продемонстрировать на экзамене в 2-м классе CompSci, что регулярное выражение не может проверить для палиндромов), вероятно, лучше всего оставлено на отдыхе в данный момент!

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

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

С уважением, Russ.