代码之家 › 专栏 › 技术社区 › Daniel Spiewak

我可以确定与regex模式匹配的第一个字符集吗?

dfa automata scala regex java

4

Daniel Spiewak · 技术社区 · 15 年前

我想能够计算所有可以匹配的字符集第一字符串中给定实例的字符 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(为了它的价值)。

2 回复 | 直到 15 年前

1

4

Tetha 15 年前

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

有些事情很简单:

把它扩展到正则表达式方言知道的所有原语和特殊标志,这样你就可以走了。

2

1

Daniel Brückner Pradip 15 年前

你可以递归地解决它…

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

所以我认为这是一个非常复杂的问题。