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

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

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

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

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


c++ regex c++11 dfa template-meta-programming
person Mr. Wonko    schedule 22.12.2014    source источник
comment
Еще одна вещь, которую следует учитывать: вы можете создать DFA для регулярного выражения, используя собственный инструмент, который вы пишете, и сериализовать его в какой-то двоичный файл. Затем во время выполнения вам нужно будет просто импортировать DFA, а не создавать его с нуля. Это должно быть быстрее, чем просто создание DFA во время выполнения.   -  person bialpio    schedule 23.12.2014
comment
Я думаю, я просто невежественен, но почему DFA, созданный во время компиляции и зная его размер, требует какого-либо выделения памяти? Конечно, каждая конструкция даст другой тип, но это не должно быть проблемой. Я подозреваю, что глубина рекурсии является более вероятным ограничением (я не пытался создать DFA во время компиляции).   -  person Dietmar Kühl    schedule 23.12.2014
comment
Я не уверен, действительно ли он генерирует DFA или NFA, но Boost Xpressive (только для одного примера) по крайней мере преобразует регулярное выражение в какой-то тип FSM во время компиляции (и ряд других тоже делают подобные вещи).   -  person Jerry Coffin    schedule 23.12.2014
comment
DFA выполняется за линейное время после его построения, но в худшем случае построение DFA занимает экспоненциальное время (поскольку он идет от RE -> NFA -> DFA). cs.stackexchange.com/questions/130/   -  person nhahtdh    schedule 23.12.2014
comment
Если построение DFA непомерно дорого во время выполнения, я сомневаюсь, что компилятор сможет успешно построить его во время компиляции. Даже если бы это было возможно, я не понимаю, как это могло бы купить вам что-нибудь. Однако вам все равно придется пересобирать его каждый раз при компиляции для отладки последних изменений. Я думаю, вы обнаружите, что использование TMP медленнее и сложнее в устранении неполадок, чем во время выполнения.   -  person bfair    schedule 20.01.2015
comment
Развивая идею bialpo, вместо сериализации и повторного импорта DFA во время выполнения создайте DFA как автономную службу. Затем вам нужно построить его только один раз, когда служба инициализируется, и после этого вы можете делать столько запросов на службу (через определенный вами API), сколько захотите. Вы можете дешево перекомпилировать и повторно запустить другие части своей программы, в то время как служба DFA работает в фоновом режиме.   -  person bfair    schedule 20.01.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

Вот пример функции на связанной странице:

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.

person Beginner    schedule 27.02.2015
comment
Я просто не понимаю, как представить и вычислить произвольно большой набор состояний, указывающих друг на друга в TMP. Но я, вероятно, не буду делать это с TMP, вместо этого кэшируя результат онлайн-вычисления в файле, это намного проще. - person Mr. Wonko; 28.02.2015