编译器可以从正则表达式中可行地计算DFA吗？

Question

在修改一个闭源游戏时,我正在运行时将机器代码修改为jmp到我自己的代码中.为了以通用方式执行此操作,我使用模式匹配来查找我想要修改的代码位置.(模式只包含字符/字节和通配符,其中字节可以变化.)通过从我的所有模式构建确定性有限自动机,我可以在线性时间内搜索.

但是我发现构建DFA比实际运行它需要更多的时间,特别是在调试版本中(我在开发过程中肯定需要它),并且随着我添加更多模式,这只会变得更糟.但这可以很容易地离线完成.我正在考虑如何; 编译器能做到吗？

据我所知,这是不可能的constexpr功能,因为我不能用它们分配静态内存.但我有一种模糊的感觉,即它应该以类型安全的方式使用模板元编程.或者在创建具有数百或数千个状态的自动机时,我是否可能遇到递归限制？

而且无论技术可能性如何,这是否合理？或者我应该在单独的构建步骤中计算源文件？

Answer 1

是的，这是可能的。可以使用一种标准算法来完成构建，例如Thompson 的构建算法，以获得 NFA，然后从中构建 DFA。问题在于，当将 NFA 转换为 DFA 时，状态数量可能会呈指数级增长。

如何处理所需的递归深度在这个问题的答案中讨论。

可以使用模板元编程来实现该算法。可以在此处找到基本构建块的列表，它允许您存储值、实现分支和函数。

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

这是一个将两个参数相加并将结果存储在结果枚举成员中的函数。您可以在编译时使用诸如 Adder<1, 2>::result 之类的东西来调用它，它将在编译时展开，并且其作用与程序中的文字 3 完全相同。

由于 Thompson 的算法依赖于递归，因此这里有一个评估递归的示例：

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

这在编译时实现了阶乘。然后可以像这样在运行时使用它factorial<5>::value。