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

在修改一个封闭源代码的游戏时，我正在运行时修改机器代码，以将其jmp转换为我自己的代码。为此，我使用模式匹配来查找要修改的代码位置。 (模式仅由字符/字节和通配符组成，其中字节可以变化。)通过根据我所有的模式构建确定性有限自动机，我可以在线性时间内进行搜索。

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

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

而且，不管技术可能性如何，这是否合理？还是我想在一个单独的构建步骤中计算源文件？

最佳答案

是的，这是可能的。可以使用诸如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 };
};

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

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

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

关于c++ - 编译器可以从正则表达式可行地计算DFA吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27611389/