Генерация строк с регулярными выражениями

Ответ 1

Я сделаю это, построив минимальный дефинитивный конечный автомат для языка. Если вы начинаете с регулярного выражения, это можно сделать автоматически Thompson Construction, за которым следует построение подмножества и минимизация. См. Это описание, например.

С DFA в руке вы можете использовать что-то вроде этого алгоритма:

Let P = { < START, [""] > } be a set of pairs <State, list of strings>
for n = 0, 1, ... Max
  Let P' = {} be a new set 
  while P is not empty 
    Remove the pair <s, L> from P 
    For each transition s -- c --> t in alpha order of c
      if t is an accepting state,
          output l + c for each string l in L
      put <t, L + c> in P' (** i.e. append c to each string in L)
  end
  Set P = P'
end

Обратите внимание, что шаг, обозначенный ** должен быть истинной установкой вставки, так как дубликаты могут легко возникать.

Это основной алгоритм. P может экспоненциально расти с выходной длиной, но это всего лишь цена отслеживания всех возможностей для будущей строки вывода. Ограничения порядка/размера/пространства, о которых вы упомянули, могут быть обеспечены путем сохранения упорядоченного порядка в списках L и путем отсечения поиска при достижении пределов ресурсов.

редактировать

Вот пример Java-игры, в котором я жестко закодировал DFA для простых двоичных литералов с плавающей запятой с дополнительным знаком "минус". Это использует немного другую схему, чем псевдокод выше, чтобы получить строгий порядок сортировки вывода и разместить диапазоны символов.

import java.util.Comparator;
import java.util.TreeSet;

public class Test{

    public static class DFA {

        public static class Transition  {

            final int to;
            final char lo, hi; // Character range.

            public Transition(int to, char lo, char hi) {
                this.to = to;
                this.lo = lo;
                this.hi = hi;
            }

            public Transition(int to, char ch) {
                this(to, ch, ch);
            }
        }

        // transitions[i] is a vector of transitions from state i.
        final Transition [] [] transitions;

        // accepting[i] is true iff state i is accepting
        final boolean [] accepting;

        // Make a fresh immutable DFA.
        public DFA(Transition [] [] transitions, boolean [] accepting) {
            this.transitions = transitions;
            this.accepting = accepting;
        }

        // A pair is a DFA state number and the input string read to get there.
        private static class Pair {
            final int at;
            final String s;

            Pair(int at, String s) {
                this.at = at;
                this.s = s;
            }
        }

        // Compare pairs ignoring 'at' states, since 
        // they are equal iff the strings are equal.
        private Comparator<Pair> emitOrder = new Comparator<Pair>() {
            @Override
            public int compare(Pair a, Pair b) {
                return a.s.compareTo(b.s);
            }
        };

        // Emit all strings accepted by the DFA of given max length.
        // Output is in sorted order.
        void emit(int maxLength) {
            TreeSet<Pair> pairs = new TreeSet<Pair>(emitOrder);
            pairs.add(new Pair(0, ""));
            for (int len = 0; len <= maxLength; ++len) {
                TreeSet<Pair> newPairs = new TreeSet<Pair>(emitOrder);
                while (!pairs.isEmpty()) {
                    Pair pair = pairs.pollFirst();
                    for (Transition x : transitions[pair.at]) {
                        for (char ch = x.lo; ch <= x.hi; ch++) {
                            String s = pair.s + ch;
                            if (newPairs.add(new Pair(x.to, s)) && accepting[x.to]) {
                                System.out.println(s);
                            }
                        }
                    }
                }
                pairs = newPairs;
            }
        }
    }

    // Emit with a little DFA for floating point numbers.
    public void run() {
        DFA.Transition [] [] transitions = {
            {   // From 0
                new DFA.Transition(1, '-'),
                new DFA.Transition(2, '.'),
                new DFA.Transition(3, '0', '1'),
            },
            {   // From 1
                new DFA.Transition(2, '.'),
                new DFA.Transition(3, '0', '1'),
            },
            {   // From 2
                new DFA.Transition(4, '0', '1'),
            },
            {   // From 3
                new DFA.Transition(3, '0', '1'),
                new DFA.Transition(4, '.'),
            },
            {   // From 4
                new DFA.Transition(4, '0', '1'),
            }  
        };
        boolean [] accepting = { false, false, false, true, true };
        new DFA(transitions, accepting).emit(4);
    }

    public static void main (String [] args) {
        new Test().run();
    }
}

Ответ 2

Старый вопрос, но никто не ответил на это, щедрость все еще активна, и у меня уже есть готовый раствор, так что вот возможный ответ:

Я как-то написал небольшую программу, которая делает это. Однако в C++/Qt (хотя я пишу почти все мои программы в Delphi, это один из C++), не поддерживает Unicode и не делает никаких гарантий заказа

Он работает следующим образом:

1. Все? {} + * | () расширяются (до максимального предела), так что остаются только классы символов и обратные ссылки.

   например, [ac]+|t*|([xz]){2}foo\1|(a|b)(t|u) становится [ac]|[ac][ac]|[ac][ac][ac]|[ac][ac][ac][ac]||t|tt|tt|ttt|ttt|([xz][xz])foo\1|at|au|bt|bu

   (| в последнем выражении - только обозначение, программа сохраняет каждый альтернативный подрегрех в списке)

2. Обратные ссылки на несколько символов заменяются обратными ссылками на отдельные символы.

   например, выражение выше становится [ac]|[ac][ac]|[ac][ac][ac]|[ac][ac][ac][ac]||t|tt|tt|ttt|ttt|([xz])([xz])foo\1\2|at|au|bt|bu

   Теперь каждый альтернативный подрегрев соответствует строке фиксированной длины.

3. Для каждой из альтернатив печатаются все комбинации символов выбора из классов:

   например, выражение выше становится a|b|c|aa|ba|..|cc|aaa|baa|...|ccc|aaaa|...|cccc||t|tt|tt|ttt|ttt|xxfooxx|yxfooyx|...|zzfoozz|at|au|bt|bu

Вероятно, вы можете добавить гарантии порядка shortlex следующим образом:

1. Сортировка символов в классах по алфавиту

2. Сортируйте альтернативы, полученные на этапе 2. выше для длины

   (есть экспоненциально много альтернатив, но обычно их счет пренебрежимо мал по сравнению с количеством полученных строк)

3. Сортировка/обмен символьными классами и обратными ссылками, чтобы все опорные точки назад

4. Перечислите возможные строки для одной альтернативы с фиксированной длиной, как и раньше, но начинайте с последнего класса символов, вместо этого сначала набирайте алфавитный порядок.

   (это не сработало бы, если бы были какие-то обратные ссылки, указывающие вперед)

5. Если имеется несколько альтернатив одинаковой длины, перечислите их в "параллельном", сравните их текущие строки и напечатайте алфавитно-низкие значения. (т.е. объединить уже отсортированные списки для каждой альтернативы).

   Это может быть оптимизировано, например, путем обнаружения различных префиксов и классов безопасного символа в суффиксе, который можно перечислить, не влияя на порядок. (например, [az] | b [az] имеет различные префиксы, а [az] можно перечислить без каких-либо сравнений)