Wygeneruj wszystkie prawidłowe wartości dla wyrażenia regularnego.

Question

Wiem, że używając Xegera, możemy uzyskać losową wartość dla określonego wzorca.

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

Chcę wiedzieć, czy istnieje sposób, aby zwrócić wszystkie prawidłowe ciągi dla określonego regex. Na przykład dla wzorca: [0-9]{2}, możemy uzyskać wszystkie wartości od 00 do 99.

Dzięki

Edit:

Tutaj nie uważamy nieskończone wyjścia jak + i *; jak możemy uzyskać wszystkie wartości dla skończonego wyrażenia regularnego?

Ostatnia edycja:

Dziękuję wszystkim! Wreszcie nie biorę pod uwagę wszystkich możliwych wartości, ponieważ mogą być tysiące. Ograniczam określoną liczbę jako liczbę wartości w celu zmniejszenia kwoty.

Answer 1

Ponieważ wyrażenie regularne jest definiowane przez skończoną maszynę stanów, zastanawiałem się, czy istnieje coś takiego, co może automatycznie powodować takie maszyny i było to dobre dopasowanie do tego, aby zostać ponownie wykorzystane do tej pracy ...i clojure.core.logic delivered

Tak, patrzyłem na to definition of the regexp grammar (niestety, brakuje {} kwantyfikatorów, ale powinny one być dość łatwo dodać do mojego kodu) przystosowane go do ucieczek Java i działało to 110 linii długiej Clojure Program:

(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)))) 

jest napisane z core.logic, powinno być dość łatwe do przystosowania go do pracy również jako dopasowującego regexp

ograniczyłem znaki printables od 32 do 126 znaków ASCII, w przeciwnym razie dalszy być zbyt nieporęczne, aby radzić sobie z wyrażeń regularnych, takich jak [^c], ale możesz go przedłużyć całkiem łatwo ... także, nie zaimplementowałem jeszcze związków, wzorów opcjonalnych i \ w, \ s, itp. ucieczki dla klas postaci

To jest największa rzecz, jaką napisałem do tej pory, ale podstawy wydaje się być pokryte tylko dobrze ... kilka przykładów:

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") 

Odkąd zacząłem w ten sposób, że realizowany również nieskończone wyjść :)

Jeśli ktoś jest zainteresowany, mogę uploaded it here

i oczywiście, oto przykład, jak wywołać unfold ze zwykłej starej Javy:

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); 
     } 
    } 
} 

Answer 2

Tutaj jest w C napisanego przez język generatora open source RegLdg - generator słownika wyrazów gramatycznych wyrażenia regularnego.

Wierzę, że nie będzie bardzo trudno zrobić port Java tego programu.

Answer 3

Trywialny realizacja takiego algorytmu jest po prostu:

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 

Answer 4

Znalezienie wszystkie mecze, jest bardzo podobna do znalezienia losowego meczu. Poniżej znajduje się prosta modyfikacja logiki, która generuje losowe dopasowania na www.debuggex.com, zakładając, że masz już drzewo analizy.

Chodzi o to, że dla każdego poddrzewa zwracana jest lista wszystkich możliwych wygenerowanych ciągów, z uwzględnieniem ciągu, który został wygenerowany przez wszystkie poprzednie węzły w drzewie analizy.

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 

Resztę drzew pozostawia się jako ćwiczenia (przede wszystkim literalne drzewo).

Należy zauważyć, że celowo nie ma optymalizacji ze względu na jasność. Wywołanie myTree.all('') wygeneruje listę taką, że każdy poprawny pasujący ciąg pojawi się raz dla każdej ścieżki, która generuje ten ciąg. Prawdopodobnie będziesz chciał dodać deduplikację i pozbyć się nadmiernego kopiowania.

Należy również dodać, że działa to tylko w przypadku wyrażeń regularnych, które mają małą liczbę łączonych pasujących ciągów. Dzieje się tak dlatego, że wszystkie ciągi są przechowywane. Jeśli chcesz obejść to ograniczenie, możesz yield, jeśli ten algorytm. Będziesz musiał utrzymywać stos (myślę, że jest to ślad okruchów chleba), w którym jesteś w drzewie. Kiedy pojawi się nowy ciąg znaków, utworzysz go ze ścieżki, którą przebyłeś, a następnie zaktualizujesz ścieżkę.