我可以确定由Regex模式匹配的第一张字符集吗？

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 libs（值得它的价值）。

Answer 1

我认为您可以解析正则表达式，并定义一些递归功能，这些功能在从左到右的曼纳（Light-Might-Manner）中以解析的正则表达式运行，建立了这样的第一组。

有些事情很简单：

• 序列：first（r1r2）= first（r1） +（如果''在第一个（r1）first（r2）else空集）
• 替代：第一（r1 | r2）= first（r1） + first（r2）
• 迭代：第一（r*）= first（r） +'''
• 字符：第一（c）= c
• 字符类：第一（[C1-CN]）= Set（C1，C2，...，CN）...

将其扩展到所有原语和特殊标志，您的正则表达方言知道，您很高兴。

Answer 2

您可以递归解决...

• 围绕括号的条带并递归地致电。
• 在高级替代方案中分开，并为每个部分递归致电。
• 如果没有其他选择，
  • 输出从左开始到第一个符号的所有符号。
  • 如果有charachter组，请输出所有符号。

这个想法可能有很多错误，但这是我尝试的。您必须剥离断言，团体名称和其他千件东西。而且，如果您找到像[^0-9]这样的倒数字符类，则必须输出很多字符。

因此，我认为这确实是一个复杂的问题。