Алгоритм регулярных выражений

Question

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

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

Answer 1

По сути, это то же самое, что задавать вопрос «учитывая некоторые требования времени выполнения, есть ли способ генерировать все возможные программы (наиболее эффективные или наименее эффективные), которые бы соответствовали этим требованиям для данного ввода?» Ответ: да , есть способ сделать это, но число результатов бесконечно, ограничено только пределами разумных ограничений памяти и реализации языка, так что вы ' Вам нужно будет наложить ограничения на то, что составляет действительную «программу» для ваших целей, чтобы сократить ее до конечного набора.

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

Regex       ::= StartAnchor? Anything? (Substring | Anything) Anything? EndAnchor?

StartAnchor ::= "^"

Anything    ::= ".*"
              | "(.*)"

Substring   ::= "orange"
              | "(orange)"

EndAnchor   ::= "$"

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