Генерируйте все перестановки текста из шаблона регулярных выражений на C#

Question

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

Пример:

var pattern = "^My (?:biological|real)? Name is Steve$";
var permutations = getStringPermutations(pattern);

Это вернет приведенный ниже список строк:

Меня зовут Стив

Мое настоящее имя Стив

Мое биологическое имя Стив

Обновить: Очевидно, что регулярное выражение имеет бесконечное количество совпадений, поэтому я хочу сгенерировать только необязательные строковые литералы, как в (?:biological | real)?из моего примера выше.Что-то вроде (.) * имеет слишком много совпадений, поэтому я не буду генерировать их на основе этого.

Answer 1

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

<lang>   -> <begin> <middle> <end>
<begin>  -> "My "
<middle> -> "" | "real" | "biological"
<end>    -> " name is Steve"

Начните с продуктов, которые имеют только терминальные символы в RHS, и перечислите все возможные значения, которые может принимать нетерминальный параметр в LHS.Затем работайте по своему усмотрению вплоть до постановок с нетерминалами на RHS.Для объединения нетерминальных символов сформируйте декартово произведение множеств, представленных каждым нетерминальным значением RHS.Для чередования возьмите объединение множеств, представленных каждым вариантом.Продолжайте пока вы не пройдете свой путь до <lang>, тогда все готово.

Однако, как только вы включаете операторы '*' или '+', вам приходится иметь дело с бесконечным количеством совпадающих строк.И если вы также хотите обрабатывать расширенные функции, такие как обратные ссылки...вероятно, вы уже на пути к чему-то изоморфному к проблеме остановки!

Answer 2

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

Answer 3

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

public static List<string> Calculate(List<string> strings) {
            List<string> returnValue = new List<string>();
            int[] numbers = new int[strings.Count];
            for (int x = 0; x < strings.Count; x++) {
                numbers[x] = 0;
            }
            while (true) {
                StringBuilder value = new StringBuilder();
                for (int x = 0; x < strings.Count; x++) {
                    value.Append(strings[x][numbers[x]]);
                    //int absd = numbers[x];
                }
                returnValue.Add(value.ToString());
                numbers[0]++;
                for (int x = 0; x < strings.Count-1; x++) {
                    if (numbers[x] == strings[x].Length) {
                        numbers[x] = 0;
                        numbers[x + 1] += 1;
                    }
                }
                if (numbers[strings.Count-1] == strings[strings.Count-1].Length)
                    break;

            }
            return returnValue;
        }