我知道通过使用 Xeger，我们可以获得指定模式的随机值。
String regex = "[0-9]{2}";
Xeger generator = new Xeger(regex);
String result = generator.generate();
我想知道有没有办法返回指定正则表达式的所有有效字符串。例如，对于 pattern: ，我们可以从to[0-9]{2}获取所有值。0099
谢谢
编辑：
这里我们不考虑像 + 和 * 这样的无限输出；我们如何获得有限正则表达式的所有值？
最后编辑：
感谢大家！最后我不考虑所有可能的值，因为可能有数千个。我限制一个特定的数字作为值的数量来减少数量。
由于正则表达式是由有限状态机定义的，我想知道是否有一些东西能够在这些机器上自动推理，并且非常适合重新用于这项工作......并且clojure.core.logic 交付
因此，我查看了正则表达式语法的定义（不幸的是，它缺少 {} 量词，但它们应该很容易添加到我的代码中）使其适应 java 转义，并制定了这个 110 行长的 clojure 程序：
(ns regexp-unfolder.core
(:require [instaparse.core :as insta])
(:require [clojure.core.logic :as l])
(:require [clojure.set :refer [union difference]])
(:gen-class :methods [#^{:static true} [unfold [String] clojure.lang.LazySeq]])
)
(def parse-regexp (insta/parser
"re = union | simple-re?
union = re '|' simple-re
simple-re = concat | base-re
concat = simple-re base-re
base-re = elementary-re | star | plus
star = elementary-re '*'
plus = elementary-re '+'
elementary-re = group | char | '$' | any | set
any = '.'
group = '(' re ')'
set = positive-set | negative-set
positive-set = '[' set-items ']'
negative-set = '[^' set-items ']'
set-items = set-item*
set-item = range | char
range = char '-' char
char = #'[^\\\\\\-\\[\\]]|\\.'" ))
(def printables (set (map char (range 32 127))))
(declare fns handle-first)
(defn handle-tree [q qto [ type & nodes]]
(if (nil? nodes)
[[q [""] qto]]
((fns type handle-first) q qto nodes)))
(defn star [q qto node &]
(cons [q [""] qto]
(handle-tree q q (first node))))
(defn plus [q qto node &]
(concat (handle-tree q qto (first node))
(handle-tree qto qto (first node))))
(defn any-char [q qto & _] [[q (vec printables) qto]] )
(defn char-range [[c1 _ c2]]
(let [extract-char (comp int first seq second)]
(set (map char (range (extract-char c1) (inc (extract-char c2)))))))
(defn items [nodes]
(union (mapcat
(fn [[_ [type & ns]]]
(if (= type :char)
#{(first ns)}
(char-range ns)))
(rest (second nodes)))))
(defn handle-set [q qto node &] [[q (vec (items node)) qto]])
(defn handle-negset [q qto node &] [[q (vec (difference printables (items node))) qto]])
(defn handle-range [q qto & nodes] [[q (vec (char-range nodes)) qto]])
(defn handle-char [q qto node &] [[q (vec node) qto]] )
(defn handle-concat [q qto nodes]
(let [syms (for [x (rest nodes)] (gensym q))]
(mapcat handle-tree (cons q syms) (concat syms [qto] ) nodes)
))
(defn handle-first [q qto [node & _]] (handle-tree q qto node))
(def fns {:concat handle-concat, :star star, :plus plus, :any any-char, :positive-set handle-set, :negative-set handle-negset, :char handle-char})
(l/defne transition-membero
[state trans newstate otransition]
([_ _ _ [state trans-set newstate]]
(l/membero trans trans-set)))
(defn transitiono [state trans newstate transitions]
(l/conde
[(l/fresh [f]
(l/firsto transitions f)
(transition-membero state trans newstate f))]
[(l/fresh [r]
(l/resto transitions r)
(transitiono state trans newstate r))])
)
(declare transitions)
;; Recognize a regexp finite state machine encoded in triplets [state, transition, next-state], adapted from a snippet made by Peteris Erins
(defn recognizeo
([input]
(recognizeo 'q0 input))
([q input]
(l/matche [input] ; start pattern matching on the input
(['("")]
(l/== q 'ok)) ; accept the empty string if we are in an accepting state
([[i . nput]]
(l/fresh [qto]
(transitiono q i qto transitions) ; assert it must be what we transition to qto from q with input symbol i
(recognizeo qto nput)))))) ; recognize the remainder
(defn -unfold [regex]
(def transitions
(handle-tree 'q0 'ok (parse-regexp regex)))
(map (partial apply str) (l/run* [q] (recognizeo q))))
使用 core.logic 编写，它应该很容易适应它也可以用作正则表达式匹配器
我将可打印字符限制为 32 到 126 个 ascii，否则处理[^c]诸如\w、\s 等字符类的转义
到目前为止，这是我在 clojure 中写的最重要的东西，但基础知识似乎已经涵盖得很好......一些例子：
regexp-unfolder.core=> (-unfold "ba[rz]")
("bar" "baz")
regexp-unfolder.core=> (-unfold "[a-z3-7]")
("a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o" "p" "q" "r" "s" "t" "u" "v" "w" "x" "y" "z" "3" "4" "5" "6" "7")
regexp-unfolder.core=> (-unfold "[a-z3-7][01]")
("a0" "a1" "b0" "b1" "c0" "c1" "d0" "d1" "e0" "e1" "f0" "f1" "g0" "g1" "h0" "h1" "i0" "i1" "j0" "j1" "k0" "k1" "l0" "l1" "m0" "m1" "n0" "n1" "o0" "o1" "p0" "p1" "q0" "q1" "r0" "r1" "s0" "s1" "t0" "t1" "u0" "u1" "v0" "v1" "w0" "w1" "x0" "x1" "y0" "y1" "z0" "z1" "30" "31" "40" "41" "50" "51" "60" "70" "61" "71")
regexp-unfolder.core=> (-unfold "[^A-z]")
(" " "@" "!" "\"" "#" "$" "%" "&" "'" "(" ")" "*" "+" "," "-" "." "/" "0" "1" "2" "3" "4" "5" "6" "7" "8" "9" ":" ";" "{" "<" "|" "=" "}" ">" "~" "?")
regexp-unfolder.core=> (take 20 (-unfold "[abc]*"))
("" "a" "b" "c" "aa" "ab" "ac" "ba" "ca" "aaa" "bb" "cb" "aab" "bc" "cc" "aac" "aba" "aca" "baa" "caa")
regexp-unfolder.core=> (take 20 (-unfold "a+b+"))
("ab" "aab" "abb" "abbb" "aaab" "abbbb" "aabb" "abbbbb" "abbbbbb" "aabbb" "abbbbbbb" "abbbbbbbb" "aaaab" "aabbbb" "aaabb" "abbbbbbbbb" "abbbbbbbbbb" "aabbbbb" "abbbbbbbbbbb" "abbbbbbbbbbbb")
由于我以这种方式开始，我还实现了无限输出:)
如果有人有兴趣，我在这里上传
显然，这是一个如何unfold从普通的旧 Java 调用的示例：
import static regexp_unfolder.core.unfold;
public class UnfolderExample{
public static void main(String[] args){
@SuppressWarnings("unchecked")
Iterable<String> strings = unfold("a+b+");
for (String s : strings){
System.out.println(s);
}
}
}
Here is in C language written open-source generator RegLdg - regular expression grammar language dictionary generator.
I believe, it will be not very difficult to make Java port of this program.
查找所有匹配项与查找随机匹配项非常相似。下面是在www.debuggex.com上生成随机匹配的逻辑的简单修改，假设您已经有一个解析树。
这个想法是，对于每个子树，您返回一个所有可能生成的字符串的列表，给定一个由解析树中所有先前节点生成的字符串。
AltTree.all = (prefix) ->
rets = []
for child in children
rets.extend(child.all(prefix))
ConcatTree.all = (prefix) ->
prefixes = [prefix]
for child in children
newPrefixes = []
for p in prefixes
newPrefixes.extend(child.all(p))
prefixes = newPrefixes
return prefixes
RepeatTree.all = (prefix) ->
prefixes = [prefix]
rets = []
for i up to max
newPrefixes = []
for p in prefixes
newPrefixes.extend(onlyChild.all(p))
prefixes = newPrefixes
if i >= min
rets.extend(prefixes)
return rets
CharsetTree.all = (prefix) ->
rets = []
for char in allValidChars():
rets.push(prefix + char)
return rets
其余的树留作练习（最值得注意的是文字树）。
请注意，为了清楚起见，故意没有优化。调用myTree.all('')将生成一个列表，这样每个有效匹配字符串对于生成此字符串的每个路径都会出现一次。您可能希望添加重复数据删除并摆脱过度复制。
我还应该补充一点，这仅适用于具有少量总匹配字符串的正则表达式。这是因为正在存储所有字符串。如果你想绕过这个限制，你可以yield验证这个算法。您将需要维护您在树中的位置的堆栈（将其视为面包屑路径）。当请求一个新字符串时，您将从您走过的路径创建它，然后更新路径。
这种算法的简单实现很简单：
def generate_matching(pattern):
alphabets = [...]
l = 1
while True:
# generate all Cartesian product of the alphabets of length `l`
for s in itertools.product(alphabets, repeat=l):
s = "".join(s)
if pattern.match(s):
print s
l += 1