Цикл в RegEx для поиска подстрок с условием

Изобретение

Я хочу поделиться своим изобретением, которое позволяет вам использовать только одно регулярное выражение, которое будет искать подстроку в строке с определенным условием. Если хотите, называйте это циклом в RegEx, которого раньше не существовало!

Я поделюсь с вами не только разными полезными шаблонами, но и покажу различные примеры от простых до сложных.

Пожалуйста, обратите внимание, что в регулярном выражении используются пробелы для улучшения читабельности. В регулярном выражении пробелы обычно используются как символы в строке, поэтому, чтобы эти шаблоны работали, требуется флаг ^[1] (?ix).

В примерах части регулярных выражений разделены на строки, что необходимо для улучшения восприятия, но эта функция не поддерживается регулярными выражениями. В примерах используется Perl syntax ^[2].

Объяснение

Начнем с простой задачи. Если в начале строки есть c, нужно найти в ней только слова и цифры (подсвечены красным):

c word = word + key
c 12 = word + word
word & word = word + word
12 = word + word

Фактически мы должны найти только слова типа word и цифры 2 и 0 только в первых двух строках.

Казалось бы, в чем проблема? Ввел что-нибудь вроде w+ (фундаментальное выражение поиска букв вроде А-Я) и нашел что надо...

Но как же условие? Ведь нам нужно учесть букву c в начале строки. Попробуем использовать синтаксис условий в RegEx: (?(condition)|(true)(false)). Ввводим на каком-нибуль сайте вроде regex101.com ^[3] и... RegEx если что и захватит, так это некоторую часть выражения. Хотя по правде он даже не найдет эту часть, ведь перед буквами стоят символы вроде = + &, т.е. RegEx не сработает.

Но мы же видим, что в строке есть буквы и буква c в начале. Значит мы должны закончить маяться ерундой и подключить уже Python с тернарным оператором… значит надо искать другое решение!

В решении данной задачи невозможно использовать look ahead/behind (слова стоят далеко от кавычек), условия (?(condition)|(true)(false)) и подгруппы с квантификатором ( )+ потому что согласно цитате с regex101.com ^[3]

a repeated capturing group will only capture the last iteration

что на нашем прекрасном языке звучит как

повторяющаяся захватывающая группа захватит только последнюю итерацию

Проще говоря, никаких тебе циклов и тернарных операторов, может пора подключать Python?

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

condition K  # Найти условие и пропустить

|  			  # Начало цикла

(?<=G)  		# Убеждаемся что условие найдено; каждая следующая итерация идет с этой позиции RegEx и с позиции предыдущей итерации
separator*?  	# Нежадный: разделитель между словами
K  			# Пропустить все что было прежде
expression  	# Выражение: w+ или .+ или d+ ...

Идея такова: встретив condition , RegEx пропускает его K и продолжает поиск с его позиции (?<=G) . Проходит мимо нежадного ^[4] разделителя слов separator, пропускает его K и наконец захватывает нужное expression.

Дойдя до конца, все повторяется вновь с позиции последнего найденного слова (?<=G). Но, чтобы цикл шел верным путем и продолжал шагать по строке, необходимо добавить перед (?<=G) символ или |.

Обратите внимание на символ ^[5]K, суть которого важно запомнить и уметь применять самостоятельно: он означает, что все, что было найдено прежде, ныне не имеет значения и исчезает из финального варианта. Сдвиг каретки/курсора, если хотите. Позволяет найти условие, отсечь его из результата и вернуть нужное. Главное помните: K не работает в обычных захватывающих группах ( ), только в незахватывающих ^[6] и атомных группах ^[7]: (?:) и (?>). Но в примерах я вообще не стал использовать группы. И это тоже работает!

Символ K стоит после условия и разделителя. Повторю еще раз: найдя condition, мы первый раз пропускаем условие-шаблон, и пройдя через separator между словами и мы с каждой итерацией будем пропускать разделитель-шаблон. Они нам не нужны, нам нужны слова. Это лишь вспомогательные конструкции.

Теперь конструируем RegEx согласно шаблону (DEMO ^[8]):

c K  		# Условие: буква "c"

|  			# Начало цикла

(?<=G)  		# Убеждаемся что условие найдено; каждая следующая итерация идет с этой позиции RegEx и с позиции предыдущей итерации
.*?  			# Нежадный разделитель: 1 и более любых символов
K  			# Пропустить все что было прежде
w+  			# Жадное выражение: любые буквы, цифры

Как получился такой шаблон? Condition у нас буква c, дальше ничего из шаблона не менялось, потом separator у нас любой символ ^[9] .*, затем сам шаблон поиска букв w который будет циклично искать буквы до конца всей строки.

Усложним эту задачу: если в начале строки есть c, а затем любые кавычки " ', нужно найти в кавычках только слова и цифры (подсвечены зеленым):

c"word & word" = word + word
c"12 = word" + word
c word & word = word + word
c 12 = word + word

Задача вроде похожа, а значит и шаблон будет не сильно отличаться от предыдущего. Но появилось существенное НО: мы больше не должны жадно хватать все слова из строки. Мы должны остановиться именно тогда, когда первый луч света освободит нас от работы с RegEx когда после слов появится кавычка. Т.е. "bla bla bla" STOOOP. Еще раз: встретили кавычку, подхватили все слова после нее, встретили кавычку вновь и остановились.

Значит теперь у нас есть условие остановки цикла. Шаблон для подобной задачи выглядит следующим образом:

condition K  # Найти условие и пропустить

|  			  # Начало цикла

(?<=G)  	# Убеждаемся что условие найдено; каждая следующая итерация идет с этой позиции RegEx и с позиции предыдущей итерации
stop*?  		# Символ остановки всего выражения: формат [^exclude]
K  			# Пропустить все что было прежде
expression  	# Выражение: w+ или .+ или d+ ...

Теперь конструируем RegEx согласно шаблону. Шаблон аналогичен предыдущему, но к условию добавлены кавычки ["']: c ["']

Появляется условие остановки регулярного выражения: [^"'](здесь символ ^[10]^ означает, что нужно найти любые символы, кроме кавычек.). После этого поиск завершается. Теперь мы создаем конструируем в соответствии с шаблоном (DEMO ^[11]):

c ["'] K  # Условие: c" или c'            

|  		   # Начало цикла

(?<=G)  		# Убеждаемся что условие найдено
[^"']*?  		# Кавычки после которых завершается поиск
K  			# Пропустить все что было прежде
w+  			# Жадное выражение: любые буквы, цифры

Попробуйте решить эти задачи не используя данные шаблоны. Я буду очень рад, если вы найдете иное оптимальное решение без Python!

Другая задача: нужно найти в кавычках ` только слова, которые не заключены в скобки { }. Проще говоря, мы должны шагать по строке, обходя стороной все, что заключено в { } или не является словом (подсвечены красным):

`{string} with {exluded} words 12 nums`
`string {with} {exluded} words 12 nums`
"quoted {string} with {exluded} words and 12 nums"
"quoted string {with} exluded {words} and {12} nums"

Значит мы должны изменить шаблон так, чтобы у него было условие остановки, условие обхода и наконец само захватывающее выражение. В данном случае должно быть два разных условия остановки: условие остановки и повтора цикла если обнаружены скобки { }; условие остановки выражения если обнаружены кавычки `:

# Условие после которого запускается 2 часть выражения
^condition # символ ^ означает начало строки

|  		   # Начало цикла

(?<=G)  	# Убеждаемся что условие найдено

(?>      	# Атомная группа
    skip 		# условие обхода: например {.*}
 	|  			# ИЛИ
    stop    	# условие остановки: например [^"']
) K      	# Пропустить все что было прежде

expression  # Выражение: w+ или .+ или d+ ...

Тут надо сразу рядом показать результат (DEMO ^[12]) и объяснить его идею:

^[`]K # Находит одиночные/двойные кавычки, убирает их из результата

|  		# Начало цикла

(?<=G)  	# Убеждаемся что условие найдено

(?>      	# Атомная группа
    {.*?}   	# Пропускает содержимое скобок { }
 	|			# ИЛИ
    [^`]    	# Останавливается после вторых кавычек
) K      	# Пропускает все что было прежде
[^{}`]+  	# Ищет 1 и более символов КРОМЕ { } `

Идея такова: встретив condition RegEx начинает с его позиции (?<=G), идет дальше, останавливается если обнаружена кавычка, обходит мимо группу, сбрасывает текущую позицию и наконец захватывает нужное expression. Дойдя до конца, все RegEx повторяется вновь с позиции последнего найденного слова (?<=G). И так до тех пор, пока не встретит главное условие остановки.

Атомная группа ^[7] (?>...) здесь важна для скорости поиска. Дело в том, что RegEx часто перебирает все варианты поиска подстрок по шаблону. Но как только эта группа найдет содержимое скобок, RegEx не будет искать 100500 вариантов как бы получше ухватить строку и все ее слова в скобках. Проще говоря: нашли, остановились на этом этапе и поехали дальше. Без лишних циклов и поисков.

Ограничения

Я буду очень рад, если вы найдете другое оптимальное решение! Пожалуйста, помогите мне улучшить данные шаблоны. У них есть существенные проблемы с оптимизацией: если не найдено condition, для каждого символа проверяется alternation (?<=G); нет пропуска неподходящих строк; не работают флаги (*SKIP)(*F). Не смотря на быструю скорость работы, количество шагов стремится к 100.000.