我如何通过一个正则表达式生成与另一个正则表达式匹配的文本？

Question

没错，你没有看错。我需要一个能够从正则表达式中 生成 随机文本的工具。因此，这个文本应该是随机的，但要与正则表达式匹配。目前似乎不存在这样的工具，但我可能是错的。

这里有一个例子：如果输入'[ab]*c'，那么这个工具就可以生成以下样本：

abc
abbbc
bac

等等。

更新：我自己创建了一个工具：Xeger。请查看http://code.google.com/p/xeger/。

- Wilfred Springer

---

很酷的想法 - 很感兴趣听到结果。 - Ryall

这确实会非常有用！ - p3t0r

我认为任何“...或更多”选择器都必须受到限制，否则你可能会得到100万个字符的单词:S - Ryall

你知道那句关于猴子可以写出莎士比亚的话（无限猴子定理）...好吧，快速且不太优雅的解决方案是：生成随机字符串直到找到一个匹配的为止。这可能需要一段时间 :-）。但我希望能看到一个真正的回复。 - vdr

这听起来可能是一个有趣的小项目。 - Herms

Answer 1

我刚刚创建了一个库，可以用来做这件事。它托管在这里：http://code.google.com/p/xeger/。使用前请仔细阅读说明（特别是下载另一个必需的库的部分）。;-)

以下是使用方法：

String regex = "[ab]{4,6}c";
Xeger generator = new Xeger(regex);
String result = generator.generate();
assert result.matches(regex);

- Wilfred Springer

Answer 2

我不知道有这样的库。如果你想自己编写一个，那么以下可能是你需要采取的步骤：

1. 编写正则表达式解析器（您可能希望从受限制的正则表达式类开始）。

2. 使用结果构建NFA。

3. （可选）将NFA转换为DFA。

4. 随机遍历从起始状态到任何接受状态的结果自动机，同时存储每个转换输出的字符。

结果是一个由原始正则表达式接受的单词。更多信息请参见例如将正则表达式转换为确定性有限自动机。

- Stephan202

---

我一直在寻找一个能够在Java中从正则表达式创建NFA的库。我知道上面的方法可以工作，因为很久以前我曾经在Javascript中这样做过。 - Wilfred Springer

我想这值得一看：http://www.brics.dk/~amoeller/automaton/ - Wilfred Springer

我基于上述库实现了Xeger。 - Wilfred Springer

Answer 3

基于Wilfred Springer的解决方案和http://www.brics.dk/~amoeller/automaton/，我构建了另一个生成器。

它不使用递归。它以模式/正则表达式最小字符串长度和最大字符串长度作为输入。结果是在最小和最大长度之间的接受字符串。它还允许一些XML“简写字符类”。我用它来生成有效的字符串以便于XML样本生成器构建限制条件。

public static final String generate(final String pattern, final int minLength, final int maxLength) {
    final String regex = pattern
            .replace("\\d", "[0-9]")        // Used d=Digit
            .replace("\\w", "[A-Za-z0-9_]") // Used d=Word
            .replace("\\s", "[ \t\r\n]");   // Used s="White"Space
    final Automaton automaton = new RegExp(regex).toAutomaton();
    final Random random = new Random(System.nanoTime());
    final List<String> validLength = new LinkedList<>();
    int len = 0;
    final StringBuilder builder = new StringBuilder();
    State state = automaton.getInitialState();
    Transition[] transitions;
    while(len <= maxLength && (transitions = state.getSortedTransitionArray(true)).length != 0) {
        final int option = random.nextInt(transitions.length);
        if (state.isAccept() && len >= minLength && len <= maxLength) validLength.add(builder.toString());
        final Transition t = transitions[option]; // random transition
        builder.append((char) (t.getMin()+random.nextInt(t.getMax()-t.getMin()+1))); len ++;
        state = t.getDest();
    }
    if(validLength.size() == 0) throw new IllegalArgumentException(automaton.toString()+" , "+minLength+" , "+maxLength);
    return validLength.get(random.nextInt(validLength.size()));
}

- SkateScout

Answer 4

这里有一些实现这种技术的例子，这里有一个，这里还有一个，这里也有一个，但没有一个是用Java编写的（除了闭源的Microsoft，其他都在正则表达式功能支持方面非常有限）。

- Michael Borgwardt

Answer 5

这是一个类似的模块的Python实现：http://www.mail-archive.com/[e-mail]/msg125198.html 它应该可以移植到Java。

- Björn Lindqvist