Сначала проанализируйте выражение и постройте дерево, отражающее синтаксическую структуру регулярного выражения, и включите в него терминатор, который логически появляется в конце. Например, в нотации 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 был дочерним по отношению к предыдущему узлу, а дочерние узлы repeat узлов указывали на повторяющийся узел.)
Затем напишите подпрограмму (или набор подпрограмм, использующих сопоставление с образцом, или виртуальные методы, если узлы в дереве реализованы с использованием полиморфизма на объектно-ориентированном языке), которые для любого данного типа узла выдают правильный вывод и возвращаются в следующий узел или потомки соответствующим образом. Например, в псевдокоде:
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
и т.д.. Как вы можете заметить, дочерние узлы повторяющегося узла не должны входить в преемник узла repeat, поэтому это необходимо учитывать при создании потока дерева. Аналогичное внимание необходимо уделить тому, чтобы «текущий прогресс» не терялся при достижении конца дочерних узлов узла repeat; альтернативно, преемник дочерних узлов может указывать на сам повторяющийся узел (т. е. истинное замыкание на графе узлов), но для этого потребуется где-то хранить счетчик.
В общем, завершение этого может занять несколько дней, в зависимости от того, насколько гибким и эффективным он должен быть. Также обратите внимание, что некоторые конструкции, такие как звезда Клини или замыкание (* или + в расширенном регулярном выражении), приведут к бесконечному списку. Язык, который поддерживает генераторы (например, синтаксис итератора C #) или сопрограммы / продолжения (например, вызов схемы / cc) или ленивую оценку (например, Haskell), может разрешить итерацию по первым нескольким элементам списка без необходимости оценки всего списка. В качестве альтернативы, выбор случайного потенциального выхода, а не исчерпывающей итерации, может быть предпочтительным для предоставления примеров, соответствующих регулярному выражению.