Как я могу развернуть конечный шаблон во все его возможные соответствия?

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

(concat
  (repeat 2
    (concat
      (charset
        (range a z)
        (range A Z))
      (literal _)
      (charset
        (range 0 9))))
  terminator)

Затем потяните дерево, чтобы вы могли использовать рекурсию для генерации комбинаторного расширения. Под этим я подразумеваю, например, что узлы a..z в (concat a .. z) все должны иметь указатели от одного к другому, поэтому a указывает на b и так далее, а сам узел concat указывает на своего преемника. Идея состоит в том, что вы можете создать одну версию текущего элемента в раскрытии и перейти к следующему элементу, а когда следующий элемент вернется, вы можете попробовать следующую версию текущего элемента и т. Д. до тех пор, пока все версии не будут исчерпаны и вы не вернетесь к вызывающему (предшественнику или родителю). Это потоки проще всего выполнить с помощью стека и обхода дерева после заказа. Если вы осторожно проталкиваете узлы во время обхода пост-порядка, верхним элементом стека будет следующий элемент в последовательности.

(Альтернативой многопоточности является структурирование дерева так, чтобы следующий элемент в каждом concat ] узел является дочерним по отношению к предыдущему узлу, а дочерние узлы повторяют узлов указывают обратно на повторяющийся узел.)

Затем напишите подпрограмму (или набор подпрограмм с использованием сопоставления с образцом или виртуальных методов, если узлы в дереве реализуются с использованием полиморфизма на объектно-ориентированном языке), который для любого заданного типа узла производит правильный вывод и соответствующим образом рекурсирует в следующий узел или дочерние элементы. Например, в псевдокоде:

if node is of form (repeat n): # non-variable repeat
    for i in 1 to n
        recurse into child
    recurse into threaded successor

if node is of form (concat ...):
    recurse into first element # last element will recurse into successor

if node is of form (literal x):
    emit x
    recurse into successor
    remove x

if node is of form (charset ...):
    for each element in charset:
        emit element
        recurse into successor
        remove element

if node is terminator:
    add string created thus far to final output list

и т. д. Как вы можете заметить, дочерние элементы повторяющегося узла не должны рекурсивно переходить в преемника узла повторения , поэтому это необходимо учитывать при распараллеливании дерева. Аналогичным образом следует позаботиться о том, чтобы «текущий прогресс» не был потерян при достижении конца дочерних узлов узла повторения ; в качестве альтернативы, преемник дочерних узлов может указывать на сам повторяющийся узел (то есть на истинное замыкание над графом узлов), но для этого потребуется где-то хранить счетчик.

В целом, это может занять несколько дней, в зависимости от насколько он должен быть гибким и производительным. Также обратите внимание, что некоторые конструкции, такие как звезда Клини или замыкание ( * или + в расширенном регулярном выражении), приведут к бесконечному списку. Язык, поддерживающий генераторы (например, синтаксис итератора C #), сопрограммы / продолжения (например, вызов схемы / cc) или ленивое вычисление (например, Haskell), может разрешить итерацию по первым нескольким элементам списка без необходимости оценивать весь список. В качестве альтернативы, выбор случайного потенциального выхода, а не исчерпывающей итерации может быть предпочтительным для предоставления примеров, соответствующих регулярному выражению.