Создайте программу, которая вводит регулярное выражение и выводит строки, которые удовлетворяют этому регулярному выражению

Question

Я думаю, что заголовок точно суммирует мой вопрос, но просто немного уточню.

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

Примечание : функция не должна генерировать каждую строку, которая удовлетворяет регулярному выражению (потому что для большого количества регулярных выражений это будет бесконечное число строк). Достаточно выбрать несколько допустимых строк.

Насколько это возможно? Если решение слишком сложное / большое, я доволен общим обсуждением / планом. Кроме того, я заинтересован в любых существующих программах или библиотеках (.NET), которые делают это.

Answer 1

Ну, регулярное выражение конвертируется в DFA, который можно рассматривать как граф. Чтобы сгенерировать строку, заданную этим DFA-графом, вы просто должны найти путь от начального состояния до конечного состояния. Вам просто нужно подумать о том, как вы хотите обрабатывать циклы (возможно, пройти каждый цикл хотя бы один раз, чтобы получить выборку? N раз?), Но я не понимаю, почему это не сработает.

Answer 2

Эта утилита на UtilityMill инвертирует некоторые простые регулярные выражения. Он основан на этом примере из википинга . Тестовые случаи для этой программы:

[A-EA]
[A-D]*
[A-D]{3}
X[A-C]{3}Y
X[A-C]{3}\(
X\d
foobar\d\d
foobar{2}
foobar{2,9}
fooba[rz]{2}
(foobar){2}
([01]\d)|(2[0-5])
([01]\d\d)|(2[0-4]\d)|(25[0-5])
[A-C]{1,2}
[A-C]{0,3}
[A-C]\s[A-C]\s[A-C]
[A-C]\s?[A-C][A-C]
[A-C]\s([A-C][A-C])
[A-C]\s([A-C][A-C])?
[A-C]{2}\d{2}
@|TH[12]
@(@|TH[12])?
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9]))?
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9])|OH(1[0-9]?|2[0-9]?|30?|[4-9]))?
(([ECMP]|HA|AK)[SD]|HS)T
[A-CV]{2}
A[cglmrstu]|B[aehikr]?|C[adeflmorsu]?|D[bsy]|E[rsu]|F[emr]?|G[ade]|H[efgos]?|I[nr]?|Kr?|L[airu]|M[dgnot]|N[abdeiop]?|Os?|P[abdmortu]?|R[abefghnu]|S[bcegimnr]?|T[abcehilm]|Uu[bhopqst]|U|V|W|Xe|Yb?|Z[nr]
(a|b)|(x|y)
(a|b) (x|y)

Answer 3

Это может быть сделано путем обхода DFA (включая псевдокод) или путем прямого обхода дерева абстрактного синтаксиса регулярного выражения или сначала преобразования в NFA, как объяснено Doug McIlroy бумага и код Haskell . (Он считает, что подход NFA идет быстрее, но он не сравнивал его с DFA.)

Все они работают с регулярными выражениями без обратных ссылок, то есть с «реальными» регулярными выражениями, а не с регулярными выражениями Perl. Для обработки дополнительных функций Perl было бы проще добавить пост-фильтр.

Добавлено: код для этого в Python от Питера Норвига и меня.

Answer 4

Так как тривиально можно написать регулярное выражение, которое не соответствует ни одной из возможных строк, и я считаю, что также возможно написать регулярное выражение, для которого вычисление совпадающей строки требует исчерпывающего поиска возможных строк любой длины, вы ' Возможно, потребуется верхняя граница для запроса ответа.

Answer 5

Я лично считаю, что это священный грааль рег-экс. Если бы вы могли это реализовать - хотя бы на 3/4 работы - я не сомневаюсь, что вы разбогатеете за 5 минут.

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

Если я ошибаюсь, я хочу поблагодарить этого разработчика.

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

Answer 6

Самый простой способ реализовать, но, безусловно, наиболее ресурсоемкий подход - это просто перебор. Установите таблицу символов с символами, которые должна содержать ваша строка, а затем просто последовательно сгенерируйте строки и выполните для них Regex.IsMatch.