Может ли регулярное выражение быть проверено, чтобы увидеть, сокращается ли оно до. * - PullRequest
Новая
       1

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

10 голосов
/ 21 ноября 2011

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

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

Мои мысли:

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

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

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

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

Ответы [ 3 ]

8 голосов
/ 21 ноября 2011

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

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

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

1 голос
/ 21 ноября 2011

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

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

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

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

0 голосов
/ 21 ноября 2011

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

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

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

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

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

С уважением, Расс.

...