Подтвердить что ты не робот

Сгенерировать все допустимые значения для регулярного выражения

Я знаю, используя Xeger, мы можем получить случайное значение для заданного шаблона.

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

Я хочу знать, есть ли способ вернуть все допустимые строки для указанного регулярного выражения. Например, для шаблона: [0-9]{2} мы можем получить все значения от 00 до 99.

Спасибо

Edit:

Здесь мы не рассматриваем бесконечные выходы, такие как + и *; как мы можем получить все значения для конечного регулярного выражения?

Последнее редактирование:

Спасибо всем! Наконец, я не рассматриваю все возможные значения, поскольку могут быть тысячи. Я ограничиваю определенное число как количество значений, чтобы уменьшить количество.

4b9b3361

ОТВЕТЫ

Ответ 1

Так как регулярное выражение задается конечным автоматом, я задавался вопросом, есть ли что-то, что может автоматически возникнуть на таких машинах, и это было хорошо приспособлено для перепрофилирования для этой работы... и clojure.core.logic поставлен

Итак, я посмотрел на это определение грамматики 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))))

Будучи написано с помощью 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);
        }
    }
}

Ответ 2

Вот в C языке, написанном открытым исходным кодом генератора RegLdg - генератор словаря грамматики регулярного выражения.

Полагаю, не составит труда сделать Java-порт этой программы.

Ответ 3

Поиск всех совпадений очень похож на поиск случайного совпадения. Ниже приведена простая модификация логики, которая генерирует случайные совпадения на 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 ify этот алгоритм. Вам нужно будет поддерживать стопку (подумайте об этом как о том, что вы являетесь травой хлебной крошки), где вы находитесь на дереве. Когда запрашивается новая строка, вы создадите ее из пройденного вами пути, а затем обновите путь.

Ответ 4

Тривиальная реализация такого алгоритма проста:

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