9

我正在寻找一种对数据流进行操作的正则表达式匹配的实现——即，它有一个 API，允许用户一次传入一个字符并在字符流上找到匹配项时报告到目前为止看到。只需要非常基本（经典）的正则表达式，因此基于 DFA/NFA 的实现似乎非常适合该问题。

基于可以在单次线性扫描中使用 DFA/NFA 进行正则表达式匹配的事实，似乎应该可以实现流式处理。

要求：

  • 在执行匹配之前，库不应尝试等到完整的字符串被读取。我真正拥有的数据是流式传输的；没有办法知道有多少数据会到达，不可能向前或向后搜索。

  • 为几个特殊情况实现特定的流匹配不是一种选择，因为我事先不知道用户可能想要寻找什么模式。

  • 语言：可从 C/C++ 使用

出于好奇，我的用例如下：我有一个在完整系统模拟器内拦截内存写入的系统，我想有一种方法来识别与正则表达式匹配的内存写入（例如，可以使用它来找到系统中将 URL 写入内存的点）。

我已经找到：

在 Stream 上应用正则表达式？

将正则表达式应用于 Java I/O 流

Code Guru - 使用 .NET Framework 构建正则表达式流搜索

但是所有这些都试图先将流转换为字符串，然后再使用常用的正则表达式库。

我的另一个想法是修改RE2 库，但根据作者的说法，它是围绕整个字符串同时在内存中的假设构建的。

如果没有可用的东西，那么我可以开始重新发明这个轮子以满足我自己的需求的不愉快的道路，但如果我可以避免它，我真的宁愿不这样做。任何帮助将不胜感激！

4

4 回答 4

5

我有你要找的东西：https ://github.com/agentzh/sregex http://agentzh.org/misc/slides/yapc-na-2013-sregex.pdf ‎</p>

如果你知道 javascript（或想要一个 javascript 版本），我有一个练习可以让你使用现有的 RE 实现轻松地做到这一点：https ://github.com/dhruvbird/regexp-js

于 2013-10-28T18:32:44.743 回答
2

英特尔已经发布了完全符合需要的hyperscan库。这里是它的简要概述。

于 2016-05-25T09:11:10.713 回答
0

看看Brian W. Kernighan 和 Rob Pike的一个旧的 grep 实现。它们在缓冲区中处理文本流，并应用于简单的正则表达式规则，甚至不是 BRE。

于 2012-11-15T23:31:33.360 回答
0

不幸的是，对此的“答案”是没有预先构建的库来执行此操作。相反，我选择了以下折衷方案：我实现了一个简单的字符串匹配器（不支持 RE），它使用每个流和每个搜索字符串的单个计数器来保持状态，该计数器跟踪在该流中匹配了多少个搜索字符串的字符。它随着每个正确的字符而增加，并在找到不匹配的字符时重置为零。这很快并且不需要太多的内存开销。

对于更复杂的搜索，我只是将所有流转储到磁盘，然后使用传统工具搜索它们。它非常慢，但幸运的是，我们的大多数用例都可以通过简单的字符串匹配来解决。

于 2013-03-06T03:22:07.677 回答