java - 我可以确定正则表达式模式匹配的第一个字符集吗？

Question

我希望能够通过 java.util.regex.Pattern< 的给定实例计算可能与字符串中的 第一个 字符匹配的所有字符集。更正式地说，给定 DFA 等同于某个正则表达式，我想要从开始状态开始的所有传出转换的集合。

一个例子:

Pattern p = Pattern.compile("[abc]def|daniel|chris|\\s+");
Set<Character> first = getFirstSet(p);

集合first应该包含以下元素:

{ 'a', 'b', 'c', 'd', ' ', '\n', '\r', '\t' }

有什么想法吗？我很清楚我可以自己构建 DFA 并以这种方式确定相关状态，但我想避免这种麻烦(阅读:这对我来说不值得)。请注意，我的宿主语言实际上是 Scala，因此我可以访问所有核心 Scala 库(物有所值)。

Answer 1

我认为你可以解析正则表达式并定义一些递归函数，以从左到右的方式对解析的正则表达式进行操作，从而建立这样的一组第一。

有些事情很简单:

• 序列:first(r1r2) = first(r1) + ( if '' in first(r1) first(r2) else empty set )
• 交替:first(r1|r2) = first(r1) + first(r2)
• 迭代:first(r*) = first(r) + ''
• 字符:first(c) = c
• 字符类:first([c1-cn]) = set(c1, c2, ..., cn) ...

将此扩展到您的正则表达式方言知道的所有原语和特殊标志，您就可以开始了。