Построение составных ориентированных графов (алгоритм построения Томпсона для генератора сканера)

Question

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

Я думал о создании очень легкой структуры NFA, которая не будет иметь собственных узлов / состояний.

struct Transition {
  State* next_state;
  char transition_symbol;
};

struct State {
  std::vector<Transition> transitions;
};

struct NFA {
  State* start_state;
  State* accepting_state;
};

Это позволило бы мне просто переназначить указатели для создания новых NFA. Все мои состояния будут храниться в центральном месте (NFABuilder?). Композиция будет выполняться с помощью внешних функций, например:

NFA create_trivial_nfa(char symbol) {
  State* start_state = new State();
  State* accepting_state = new State();
  start_state->transitions.emplace_back(accepting_state, symbol);
  // Something must own start_state and accepting_state
  return NFA{start_state, accepting_state};
}

NFA concatenate_nfas(NFA&& nfa0, NFA&& nfa1) {
  nfa0.accepting_state->transitions.emplace_back(nfa1.start_state, '\0');
  return NFA{nfa0.start_state, nfa1.accepting_state};
}

Здесь я бы использовал семантику перемещения, чтобы прояснить, что nfa0 и nfa1 больше не будут использоваться в качестве автономных NFA (поскольку я изменил их внутренние состояний).

Имеет ли этот подход смысл или есть проблема, которую я еще не ожидал? Если это имеет смысл, что должно быть владельцем всех этих государств? Я также ожидаю проблему с заполнением моих переходов. Когда упаковано в вектор, Переход будет иметь размер 16 байтов вместо 9 (в 64-битной архитектуре). Это то, о чем я должен беспокоиться, или это просто шум в общей схеме вещей? (это мой первый компилятор. Я слежу за Разработка компилятора, Cooper & Torczon )

Answer 1

Суть конструкции Томпсона заключается в том, что он создает NFA со следующими характеристиками:

1. Существует не более 2|R| состояний, где |R| - длина регулярного выражения .

2. Каждое состояние имеет либо один выход, помеченный символом, либо не более двух ε-переходов. (То есть ни одно состояние не имеет как помеченного перехода, так и перехода ε.)

Последний факт предполагает, что представление состояния в виде

struct State {
  std::vector<std::tuple<char, State*>> transitions;
}

(что небольшая аббревиатура вашего кода) - это очень высокое представление служебной информации, где служебная информация имеет гораздо большее отношение к служебной информации std::vector, используемой для хранения ровно одного или двух переходов, чем заполнение одного перехода. Кроме того, вышеприведенное представление не обеспечивает четкого метода для представления ε-переходов, если только не было намерения зарезервировать один символьный код для ε (и тем самым сделать невозможным использование этого символьного кода в регулярном выражении).

Более практичным представлением может быть

enum class StateType { EPSILON, IMPORTANT };
struct State {
  StateType type;
  char      label;
  State*    next[2];
};

(Эта формулировка не хранит число переходов в next, при условии, что мы можем использовать значение часового, чтобы указать, что next[1] не Кроме того, мы могли бы просто установить next[1] = next[0]; в таком случае. Помните, что это имеет значение только для состояний ε.)

Более того, поскольку мы знаем, что в объектах не более 2|R| State NFA, мы могли бы заменить указатели State* на маленькие целые числа. Это установит какое-то ограничение на размер регулярного выражения, которое может быть обработано, но довольно редко встречаются регулярные выражения в гигабайтах. Использование последовательных целых чисел, а не указателей также сделает некоторые алгоритмы графов более управляемыми, в частности алгоритм транзитивного замыкания, который является фундаментальным для построения подмножества.

Еще один интересный факт о NFA, построенном по алгоритму Томпсона, заключается в том, что - степень состояний также ограничена 2 (и опять же, если есть два перехода, оба будут ε переходами). Это позволяет нам избежать преждевременного создания конечных состояний вспомогательных машин (что не потребуется, если вспомогательный механизм является левым аргументом для конкатенации). Вместо этого мы можем представить вспомогательную машину всего тремя индексами: индексом начального состояния и индексами не более двух внутренних состояний, которые после добавления будут иметь переходы в конечное состояние.

Я думаю, что вышеупомянутое достаточно близко к первоначальной реализации Томпсона, хотя я уверен, что он использовал гораздо больше приемов оптимизации. Но стоит прочитать Раздел 3.9 Aho, Lam, Sethi & Ullman («Книга Дракона»), в котором описаны способы оптимизации построения конечных автоматов.

Независимо от теоретических сокращений, стоит отметить, что помимо tr ie шаблонов ключевых слов, большинство переходов состояний в лексическом анализе включают наборы символов, а не отдельные символы, и часто эти наборы довольно велики, особенно если единицей лексического анализа является кодовая точка Unicode, а не символ ascii. Использование наборов символов вместо символов усложняет алгоритм построения подмножества, но, как правило, значительно уменьшает количество состояний.