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

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

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

有些东西很简单：

• 序列：第一（R1R2）=第一（R1）+（在第一（R1如果 ''）第一（R 2）别的空集）
• 交替：第一（R1 | R2）=第一（R1）+第一（R2）
• 迭代：第一（R *）=第一（R）+ ''
• 性状：第一（C）= C
• Characterclasses：第一（[c1-cn]）= set（c1，c2，...，cn） ...

将此扩展到正则表达式方言知道的所有原语和特殊标志，并且您可以轻松前往。

Answer 2

你可以解决它recursivly ...

• 地带包围括号和recursivly调用。
• 拆分顶层替代品并为每个部分递归调用。
• 如果没有替代品，
  • 输出从留给开始第一无可选符号的所有符号。
  • 如果有charachter组，输出所有符号。

可能有很多这种想法的错误，但是这是我想尝试。你必须去掉断言，组名和其他一千件事情。如果您发现像[^ 0-9]这样的倒排字符类，则必须输出大量字符。

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