может ли компилятор реально рассчитать DFA из регулярного выражения?
Модифицируя игру с закрытым исходным кодом, я изменяю машинный код во время выполнения в jmp в свой собственный код. Чтобы сделать это в общем виде, я использую сопоставление с образцом, чтобы найти места кода, которые я хочу изменить. (Шаблоны состоят только из символов / байтов и подстановочных знаков, где байты могут варьироваться.) Создавая детерминированный конечный автомат из всех моих шаблонов, я могу искать за линейное время.
Однако я обнаружил, что сборка DFA занимает больше времени, чем фактический запуск, особенно в отладочных сборках (что мне, безусловно, нужно во время разработки), и это будет только ухудшаться по мере добавления новых шаблонов. Но это может быть легко сделано в автономном режиме. Я сейчас думаю о том, как; может ли компилятор это сделать?
Насколько я знаю, это невозможно с constexpr функции, так как я не могу выделить статическую память с ними. Но у меня есть смутное ощущение, что это должно быть выполнимо безопасным способом с метапрограммированием шаблона. Или я могу столкнуться с рекурсивными пределами при создании автоматов с сотнями или тысячами состояний?
И независимо от технической возможности, это разумно? Или мне лучше, скажем, рассчитать исходный файл на отдельном этапе сборки?
Решение
Да, это возможно. Построение может быть сделано с помощью одного из стандартных алгоритмов, таких как Алгоритм построения Томпсона чтобы получить NFA, а затем построить DFA из этого. Проблема заключается в том, что при преобразовании NFA в DFA возможен экспоненциальный рост числа состояний.
Как справиться с требуемой глубиной рекурсии обсуждается в ответы на этот вопрос.
Реализовать алгоритм можно с помощью шаблонного метапрограммирования. Список основных строительных блоков можно найти Вот, что позволяет хранить значения, реализовывать ветви и функции.
Вот пример для функции из связанная страница:
template<int X, int Y>
struct Adder
{
enum { result = X + Y };
};
Это функция, которая добавляет два параметра и сохраняет результат
в результате enum член. Вы можете вызвать это во время компиляции с
что-то вроде Adder<1, 2> :: результат, который будет расширен при компиляции
время и действовать точно так же, как буквальный 3 в вашей программе.
Поскольку алгоритм Томпсона основан на рекурсии, вот пример для оценки рекурсии:
template <unsigned n>
struct factorial
{
enum { value = n * factorial<n-1>::value };
};
Это реализует факториал во время компиляции. Это может быть использовано во время выполнения, как это factorial<5>::value,
Другие решения
detector