为一个正则表达式生成所有的有效值

Question

我知道通过使用Xeger，我们可以获得指定模式的随机值。

String regex = "[0-9]{2}"; 
Xeger generator = new Xeger(regex);
String result = generator.generate();

我想知道有没有办法返回指定正则表达式的所有有效字符串。例如，对于模式：[0-9]{2}，我们可以获取从00到99的所有值。

谢谢

编辑：

这里我们不考虑像和*这样的无限输出；如何获得有限正则表达式的所有值？

上次编辑：

谢谢大家！最后，我没有考虑所有可能的值，因为可能有数千个。我限制一个特定的数字作为值的数量，以减少数量。

Answer 1

查找所有匹配项与查找随机匹配项非常相似。下面是对在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（“”）将生成一个列表，以便每个有效的匹配字符串对于生成该字符串的每个路径显示一次。您可能希望添加重复数据消除并消除过度复制。

我还应该补充一点，这只适用于具有少量总匹配字符串的正则表达式。这是因为所有字符串都被存储了。如果你想绕过这个限制，你可以产生ify这个算法。你需要维护一个你在树中的位置的堆栈（把它想象成一个面包屑痕迹）。当要求一个新字符串时，你将从你走过的路径创建它，然后更新路径。

Answer 2

这里是在C语言中编写的开源生成器RegLdg-正则表达式语法语言字典生成器。

我相信，制作这个程序的Java端口不会很困难。

Answer 3

由于regexp是由一个有限状态机定义的，我想知道是否有什么东西能够在这样的机器上自动推理，这很适合重新调整此工作的用途。。。和clojure。果心交付的逻辑

因此，我查看了regexp语法的这个定义（不幸的是，它缺少{}量词，但它们应该很容易添加到我的代码中），将其改编为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))))

用核心编写。从逻辑上讲，它应该很容易适应它，也可以用作regexp匹配器

我将可打印字符限制在32到126个ascii之间，否则处理regexp（如[^c]）会太麻烦，但您可以很容易地扩展它。。。此外，我还没有实现字符类的联合、可选模式和转义等

到目前为止，这是我在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")

自从我以这种方式开始，我也实现了无限输出：）

如果有人感兴趣，我上传到这里

显然，下面是一个如何从普通的旧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);
        }
    }
}