c++ - 编译器能否从正则表达式中计算出 DFA？

Question

在修改封闭源代码游戏时，我在运行时修改机器代码以跳转到我自己的代码中。为了以通用方式执行此操作，我使用模式匹配来查找我想要修改的代码位置。 (模式仅由字符/字节和通配符组成，其中字节可以变化。)通过从我的所有模式构建确定性有限自动机，我可以在线性时间内搜索。

但是我发现构建 DFA 比实际运行它要花更多的时间，尤其是在调试构建中(我在开发过程中当然希望如此)，而且随着我添加更多模式，情况只会变得更糟。但这可以很容易地离线完成。我目前正在考虑如何；编译器能做到吗？

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

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

Answer 1

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

answers to this question 中讨论了如何处理所需的递归深度。 .

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

这是来自 linked page 的函数示例:

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

This is a function that adds its two parameters and stores the result in the result enum member. You can call this at compile time with something like Adder<1, 2>::result, which will be expanded at compile time and act exactly like a literal 3 in your program.

由于 Thompson 的算法依赖于递归，这里有一个评估递归的例子:

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

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