Эффективный алгоритм для преобразования набора символов в nfa / dfa

Question

Я сейчас работаю над генератором сканера. Генератор уже работает нормально. Но при использовании классов символов алгоритм становится очень медленным.

Генератор сканера производит сканер для файлов в кодировке UTF8. Должен поддерживаться полный диапазон символов (от 0x000000 до 0x10ffff).

Если я использую большие наборы символов, например, оператор any '.' или свойство unicode {L}, nfa (а также dfa) содержит много состояний (> 10000). Таким образом, преобразование nfa в dfa и создание минимального dfa занимает много времени (даже если выходной минимальный dfa содержит только несколько состояний).

Вот моя текущая реализация создания части набора символов nfa.

void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters)
{
transitions[startStateIndex] = CreateEmptyTransitionsArray();
foreach (int character in characters) {
    // get the utf8 encoded bytes for the character
    byte[] encoded = EncodingHelper.EncodeCharacter(character);
    int tStartStateIndex = startStateIndex;
    for (int i = 0; i < encoded.Length - 1; i++) {
        int tEndStateIndex = transitions[tStartStateIndex][encoded[i]];
        if (tEndStateIndex == -1) {
           tEndStateIndex = CreateState();
               transitions[tEndStateIndex] = CreateEmptyTransitionsArray();
        }                   
        transitions[tStartStateIndex][encoded[i]] = tEndStateIndex;
        tStartStateIndex = tEndStateIndex;
    }
    transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex;
}

Кто-нибудь знает, как реализовать эту функцию гораздо эффективнее, чтобы создавать только необходимые состояния?

EDIT:

Чтобы быть более точным, мне нужна такая функция:

List<Set<byte>[]> Convert(Set<int> characters)
{
     ???????
}

Вспомогательная функция для преобразования символа (int) в байт кодировки UTF8 [] определяется как:

byte[] EncodeCharacter(int character)
{ ... }

Answer 1

Есть несколько способов справиться с этим. Все они сводятся к обработке наборов символов за раз в структурах данных вместо того, чтобы вообще перечислять весь алфавит. Это также, как вы делаете сканеры для Unicode при разумном объеме памяти.

У вас есть много вариантов представления и обработки наборов символов. В настоящее время я работаю с решением, которое хранит упорядоченный список граничных условий и соответствующих целевых состояний. Вы можете обрабатывать операции в этих списках намного быстрее, чем если бы вам приходилось сканировать весь алфавит на каждом этапе. На самом деле, он достаточно быстрый, чтобы работать на Python с приемлемой скоростью.

Answer 2

Посмотрите, что делают библиотеки регулярных выражений, такие как Google RE2 и TRE.

Answer 3

В этой библиотеке (http://mtimmerm.github.io/dfalex/) я делаю это, помещая диапазон последовательных символов в каждом переходе вместо отдельных символов. Это выполняется на всех этапах создания NFA, преобразования NFA-> DFA, DFAминимизация и оптимизация.

Это довольно компактно, но добавляет сложности кода на каждом этапе.

Answer 4

У меня была та же проблема с моим генератором сканера, поэтому мне пришла в голову идея заменить интервалы их идентификаторами, которые определяются с помощью дерева интервалов. Например, диапазон a..z в dfa может быть представлен как: 97, 98, 99, ..., 122, вместо этого я представляю диапазоны как [97, 122], а затем строю из них древовидную структуру интервалов они представлены как идентификаторы, которые ссылаются на дерево интервалов. Учитывая следующее RE: a..z +, мы получаем такой DFA:

0 -> a -> 1
0 -> b -> 1
0 -> c -> 1
0 -> ... -> 1
0 -> z -> 1

1 -> a -> 1
1 -> b -> 1
1 -> c -> 1
1 -> ... -> 1
1 -> z -> 1
1 -> E -> ACCEPT

Теперь сжимаем интервалы:

0 -> a..z -> 1

1 -> a..z -> 1
1 -> E -> ACCEPT

Извлеките все интервалы из вашего DFA и создайте из них дерево интервалов:

{
    "left": null,
    "middle": {
        id: 0,
        interval: [a, z],
    },
    "right": null
}

Заменить фактические интервалы на их идентификаторы:

0 -> 0 -> 1
1 -> 0 -> 1
1 -> E -> ACCEPT