Создание набора строк из заданного регулярного выражения на языке L

Question

Я пытаюсь создать последовательность слов в алфавите (заданную пользователем) в соответствии с регулярным выражением (также заданную пользователем), но не могу сделать это.

Пример сценария 1:

Alphabet = [a,b,c]

Regex = (a+c)b*

Word Count = 6

Words = ["a", "c", "ab", "cb", "abb", "cbb"]

Пример сценария 2:

Alphabet = [a,b]

Regex = (a+b)*a

Word Count = 3

Words = ["a", "aa", "ba"]

Я попытался преобразовать регулярное выражение в постфикс / инфикс, а затем пошел оттуда, но не смог построить алгоритм движка.

В основном есть 3 операции;

Союз (+)
Concat ()
Закрытие (*)

Я написал одну функцию для каждого типа оператора;

void union(char* x[], char y)
{
    printf("%s\n%c\n", x, y);

    remainingWordCount -= 2;
}

void concat(char* x[], char* y[])
{
    printf("%s%s\n", x, y);
    remainingWordCount--;
}

void closure(char* x[], char* y[])
{
    while (remainingWordCount > 0)
    {
        concat(x, y);
    }
}

Это работает только в большинстве основных сценариев.

Итак, мой вопрос: как я могу создать набор строк в соответствии с заданным регулярным выражением без использования какой-либо библиотеки регулярных выражений? Есть ли известные алгоритмы для этого?

Answer 1

Основной алгоритм прост (если вы знаете, как сделать все части):

1. Создайте DFA из регулярного выражения . (Построение NFA недостаточно, потому что NFA будет создавать дублирующиеся строки, если регулярное выражение не является детерминированным.) Ссылка показывает один способ сделать это, но есть другие; Вы, вероятно, найдете более длинную экспозицию в своем учебнике по языкам, если у вас есть.

2. Выполните упорядоченную прогулку ( «поиск в первую очередь» ) (бесконечного) графа, сгенерированного из DFA, где каждый узел представляет собой пару (state, prefix), а ребра соответствуют переходам в ДФА. Во время обхода, если встречается узел, принимающий state, выведите его prefix.

Этот базовый алгоритм будет работать для любых отношений упорядочения между строками со свойством prefix: любой правильный префикс строки гарантированно будет меньше строки. (Если это не так, возможно, что в наборе строк нет элемента "наименьшего". Например, если отношение упорядочивания ставит строку перед любым префиксом этой строки, но в противном случае является лексикографическим, тогда любая строка в a* предшествует следующая более длинная строка, которая создаст бесконечный цикл.)

Важно отметить, что state в узле только для удобства; он избыточен в вычислительном отношении, потому что его можно восстановить, пропустив prefix через DFA. Как следствие, граф никогда не содержит двух разных узлов с одинаковым prefix. Следствием этого наблюдения является то, что нет необходимости поддерживать набор «видимых» узлов, потому что последующие наборы двух различных узлов не пересекаются.

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

Например, лексикографическое («алфавитное») упорядочение определяется как:

(S<sub>1</sub>, P<sub>1</sub>) < (S<sub>2</sub>, P<sub>2</sub>) <strong>iff</strong> P<sub>1</sub> <<sub>lexicographic</sub> P<sub>2</sub>

В этом случае наименее принятый преемник определенно имеет наименее непосредственный преемник в качестве префикса, поэтому достаточно упорядочить кандидатов по префиксу.

По ограничениям, с более распространенным «по длине, чем лексикографическим» порядком, определяемым как:

(S<sub>1</sub>, P<sub>1</sub>) < (S<sub>2</sub>, P<sub>2</sub>) <strong>iff</strong> |P<sub>1</sub>| < |P<sub>2</sub>| <strong>or</strong> (|P<sub>1</sub>| &equals; |P<sub>2</sub>| <strong>and</strong> P<sub>1</sub> <<sub>lexicographic</sub> P<sub>2</sub>)

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

Answer 2

Я бы порекомендовал использовать шаблон проектирования "итератор". Я вижу, что вы используете C, который не особенно ориентирован на объектно-ориентированный код, но вы можете сделать это, используя структуру, содержащую указатель на функцию next, указатель на функцию restart и указатель на объект «context», который будет передан в те функции, где природа объекта «context» будет зависеть от оператора.

Что-то вроде a, функция next возвращает "a" в первый раз и NULL во второй раз. (Объект контекста следит за "a" и за тем, был ли он уже возвращен.)

В чем-то вроде ...+..., next может либо исчерпать первый итератор ... перед переходом ко второму, либо он может чередоваться между ними, как вы предпочитаете. (Объект контекста сохраняет указатели на два итератора ..., и какой из них вызывать следующим.)

. , , и т. д.

Самая сложная часть - это синтаксический анализ выражения для создания всех этих объектов, но, похоже, вам уже удобно анализировать выражение?

Answer 3

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

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

Обрабатывать пути в отсортированном порядке (так, чтобы более короткие пути предшествовали более длинным с тем же префиксом, т. Е. Согласно strcmp в C). Это позволяет избежать зацикливания и дает нужный порядок.

Например, для регулярного выражения a* (псевдокод):

state[0] = { {'a', 0}, {'\0', 1} };
state[1] = { }; // terminal state
paths = { { .state = 0, .string = "" } }; // set initial state

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

paths = { { .state = 1, .string = "" },
          { .state = 0, .string = "a" } };

Поскольку путь с пустой строкой упорядочен первым (из-за сортировки пустой строки перед любой непустой строкой), он обрабатывается первым, и, поскольку он находится в терминальном состоянии без переходов, он печатает пустую Количество строк и уменьшений слов. Затем вы берете другой путь и снова добавляете переходы из состояния 0, заканчивающиеся на:

paths = { { .state = 1, .string = "a" },
          { .state = 0, .string = "aa" } };

и т.д.

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