将多个正则表达式组合成一个自动机

Question

假设我有一个正则表达式列表(从外部源读取 - 文件,数据库等).我想检查字符串匹配哪些正则表达式.

我可以通过所有这些正则表达式创建迭代并匹配它们,但列表可能是一个巨大的,这是一个关键的操作.

我可以将所有这些正则表达式合并为一个(在它们之间),但问题是我只能识别第一个匹配的正则表达式,而不是所有.

另一个想法可能是为所有这些正则表达式创建一个自动机,并用相应正则表达式的索引标记最终状态.我正在查看http://cs.au.dk/~amoeller/automaton/,这个库似乎能够使用正则表达式和自动机,但不确定它是否可以扩展来解决我的问题.

你还有其他建议吗？

为了澄清一些评论,我添加了一个代码示例:

import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class PatternTest {
    public static void main(String[] args) {
        Pattern p = Pattern.compile("(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c))");     
        Matcher m = p.matcher("aba");
        System.out.println(m.matches());
        System.out.println(m.groupCount());
        for (int i = 0, n = m.groupCount(); i < n; i++) {
            System.out.println(m.group(i));
        }
    }
}

将打印出来

true
3
aba
aba
null

正如您所看到的,只有第一组匹配,我没有找到匹配其他两组的方法.

更多发现 - 使用上面的自动机库,问题将减少到以下几点:如果连接两个或多个自动机,如何识别哪个原始自动机对应的最终状态？

Answer 1

我实现了基于dk.brics.automaton的解决方案,你可以在这里找到它. https://github.com/fulmicoton/multiregexp

Answer 2

dk.brics.automaton不直接支持这一点，但您可以概括自动机的表示（以及相关的自动机操作）以区分不同类型的接受状态。例如，首先向State类添加一个 int 字段，并在设置“accept”时使用该字段。