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

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''infirst（r1）first（r2）else空集）
• 交替：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] 这样的倒置字符类，你就必须输出很多字符。

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