Bre*_*itt 8 regex stream dfa nfa
我正在寻找一个对数据流进行操作的正则表达式匹配的实现 - 也就是说,它有一个API,允许用户一次传入一个字符并报告何时在字符流上找到匹配项到目前为止看到了 只需要非常基本的(经典的)正则表达式,因此基于DFA/NFA的实现似乎非常适合于该问题.
基于在单个线性扫描中使用DFA/NFA进行正则表达式匹配的事实,似乎应该可以实现流式实现.
要求:
图书馆应不尝试等到满弦一直在进行比赛之前被读取.我的数据确实是流媒体; 没有办法知道有多少数据会到达,无法向前或向后搜索.
为一些特殊情况实现特定的流匹配不是一种选择,因为我事先并不知道用户可能想要查找哪些模式.
语言:可从C/C++中使用
对于好奇,我的用例如下:我有一个系统拦截整个系统模拟器中的内存写入,我想有一种方法来识别与正则表达式匹配的内存写入(例如,可以使用它来找到系统中将URL写入内存的点.
我已经找到:
Code Guru - 使用.NET Framework构建正则表达式流搜索
但所有这些尝试首先将流转换为字符串,然后使用库存正则表达式库.
我的另一个想法是修改RE2库,但根据作者的说法,它的构建围绕着整个字符串同时在内存中的假设.
如果没有什么可用,那么我可以开始重新发明这个轮子的不愉快的道路,以满足我自己的需要,但我真的不愿意,如果我可以避免它.任何帮助将不胜感激!
我知道你在寻找什么:https://github.com/agentzh/sregex http://agentzh.org/misc/slides/yapc-na-2013-sregex.pdf
如果你知道javascript(或想要一个javascript版本),我有一个练习,可以让你轻松地使用现有的RE实现:https://github.com/dhruvbird/regexp-js
不幸的是，这个问题的“答案”是没有预先构建的库来执行此操作。相反，我选择了以下折衷方案：我实现了一个简单的字符串匹配器（不支持 RE），它使用每个流和每个搜索字符串的单个计数器来保持状态，该计数器跟踪该流中已匹配的搜索字符串的字符数。它会随着每个正确的字符而递增，并在发现不匹配的字符时重置为零。这很快并且不需要太多的内存开销。
对于更复杂的搜索，我只是将所有流转储到磁盘，然后使用传统工具搜索它们。它非常慢，但幸运的是，我们的大多数用例只需简单的字符串匹配即可完成。