在修改一个封闭源代码的游戏时,我正在运行时修改机器代码,以将其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/

10-17 03:13