增量正则表达式匹配

问题:程序需要从输入的字符流中读取,并根据预定义的正则表达式模式列表匹配输入。程序应该在找到匹配项后立即报告匹配项(如果有多个匹配项,则报告所有匹配项),或者在没有任何匹配项的情况下使用整个流后报告失败。输入可能不会一次全部出现,因此每当程序调用 read

简单的解决方案是缓冲到目前为止已读取的所有字符,并尝试将其与整个正则表达式模式组相匹配。但这不是很有效。正则表达式匹配本质上是有状态的,因此应该有一个不缓冲输入的方法。理想情况下,有一种使用类似于Aho Corasick的简单字符串匹配技术的一次性解决方案。我搜索了现有的库,但没有找到一个能够进行这种增量正则表达式匹配的库。哪些库或算法可以帮助(C,C++,Python或Perl库优先)?

一个现有的解决方案通过 -正在生成小正则表达式模式。但我不确定这是否比迭代小的正则表达式模式快。这不是增量匹配:每个匹配都需要整个缓冲输入。

Incremental Pattern (RegEx) matching in Java? 那里公认的答案表明了方向,但没有具体的解决办法。其他用户报告说,合并后的FSA占用了非常大的内存,但这个答案没有提到如何优化以使其实用。

帮助解决问题的Python框架:

regex_list = [ r'0+', r'1+', r'2+', r'3+' ]
class Matcher:
    def match(self):
        ...
        buffer += sys.stdin.read()
        ...
        return ([ matched_regex, ... ], matched_token)
matcher = Matcher()
while True:
    matched_regex_list, token = matcher.match()