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

前端之家收集整理的这篇文章主要介绍了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 };
};

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 };
};

这在编译时实现了一个阶乘.然后,这可以在运行时期间使用,如此阶乘< 5> ::值.

原文链接:https://www.f2er.com/c/118148.html

猜你在找的C&C++相关文章