Может ли компилятор правильно вычислить DFA из регулярного выражения?

Question

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

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

Насколько я знаю, это невозможно с функциями constexpr, поскольку я не могу выделить им статическую память. Но у меня есть смутное ощущение, что это должно выполняться безопасным типом с мета-программированием шаблонов. Или я могу столкнуться с ограничениями при рекурсии при создании автоматов с сотнями или тысячами государств?

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

Answer 1

Да, это возможно. Конструкцию можно выполнить с помощью одного из стандартных алгоритмов, таких как Thompson's construction algorithm, чтобы получить NFA, а затем построить DFA. Проблема в том, что при преобразовании NFA в DFA возможно экспоненциальное раздутие числа состояний.

Как справиться с необходимой глубиной рекурсии обсуждается в answers to this question.

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

Ниже приведен пример для функции от linked page:

template<int X, int Y> 
struct Adder 
{ 
    enum { result = X + Y }; 
}; 

Это функция, которая добавляет свои два параметра и сохраняет результат в элементе результата перечисления. Вы можете назвать это во время компиляции с чем-то вроде Adder < 1, 2> :: result, который будет расширен при компиляции и действовать точно так же, как буква 3 в вашей программе.

Поскольку алгоритм Томпсона основан на рекурсии, здесь пример для оценки рекурсии:

template <unsigned n> 
struct factorial 
{ 
    enum { value = n * factorial<n-1>::value }; 
}; 

Это реализует факториал во время компиляции. Это можно было бы использовать во время выполнения, например, factorial<5>::value.