Поток или итератор для генерации всех строк, которые соответствуют регулярному выражению? - PullRequest
Новая
       17

Поток или итератор для генерации всех строк, которые соответствуют регулярному выражению?

0 голосов
/ 04 января 2012

Это продолжение моего предыдущего вопроса .

Предположим, я хочу сгенерировать всех строк, соответствующих данному (упрощенному) регулярному выражению.

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

Я думал об использовании Stream, но после прочтения этот вопрос Я думаю о Iterator.Что бы вы использовали?

1 Ответ

4 голосов
/ 04 января 2012

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

Во-первых, вы хотите проанализировать свое регулярное выражение - вы можете посмотреть впарсер комбинаторы для этого, например.Затем у вас будет дерево оценки, которое выглядит, например, как 

List(
  Constant("abc"),
  ZeroOrOne(Constant("d")),
  Constant("efg"),
  OneOf(Constant("h"),List(Constant("ij"),ZeroOrOne(Constant("klmnop")))),
  Constant("qrs"),
  AnyChar()
)

Вместо того, чтобы запускать это дерево выражений как matcher , вы можете запустить его как генератор путем определения метода генерации для каждого термина.Для некоторых терминов (например, ZeroOrOne(Constant("d"))) будет несколько вариантов, поэтому вы можете определить итератор.Одним из способов сделать это является сохранение внутреннего состояния в каждом члене и передача либо флага «продвижение», либо флага «сброс».При «сбросе» генератор возвращает первое возможное совпадение (например, "");при авансировании он переходит к следующему и возвращает его (например, "d") при использовании флага опережения (оставляя остальное для оценки без флагов).Если элементов больше нет, вместо этого он производит сброс для всего внутри себя и оставляет флаг продвижения для следующего элемента нетронутым.Вы начинаете с работы со сбросом;на каждой итерации вы вводите аванс и останавливаетесь, когда получаете его снова.

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

В любом случае, это, хотя и отнимает много времени, приведет к работающему генератору.Кроме того, у вас также будет работающее сопоставление регулярных выражений, если вы напишите процедуру сопоставления для каждого фрагмента анализируемого дерева.

...