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) ...

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

Answer 2

你可以递归地解决它......

• 带括号并递归调用。
• 在顶层备选方案处拆分并为每个部分递归调用。
• 如果没有其他选择，
  • 输出从左边开始到第一个非可选符号的所有符号。
  • 如果有字符组，则输出所有符号。

这个想法可能有很多错误，但这是我会尝试的。你必须去掉断言、组名和其他上千种东西。如果你发现像 [^0-9] 这样的反转字符类，你必须输出很多字符。

所以我认为这确实是一个复杂的问题。