Гуманный аналитик

💣 Регулярные выражения нерегулярны

Заголовок сегодняшнего поста звучит парадоксально, но, если копнуть вглубь (я сам это недавно сделал, а теперь хочу поделиться с вами), то всё встаёт на свои места. Он отражает историческую и теоретическую эволюцию термина "регулярные выражения".

В формальной теории языков и автоматов регулярные языки — это класс языков, распознаваемых конечными автоматами. Они описываются регулярными выражениями в классическом смысле, то есть выражениями, которые поддерживают только:
✔ конкатенацию (ab);
✔ объединение (a|b);
✔ звезду Клини (a*).

Однако со временем различные реализации (например, на JavaScript, Python и пр.) регулярных выражений вышли за эти рамки и стали Тьюринг-полными, то есть получили способность распознавать языки, не являющиеся регулярными в теоретическом смысле.

🤔 А если конкретнее?
Рассмотрим пример с так называемыми обратными ссылками (\1, \2,...). Это механизм, позволяющий ссылаться на группы символов, которые были найдены ранее, при поиске совпадений.

import re

text = 'Kappa'
pattern = r'(\w)\1'
result = re.search(pattern, text)
print(result.group(0)) # Output: pp

Данный код выведет на экран "pp". Следующий же позволит найти уже повтор слов.

import re

text = 'scary scary movie'
pattern = r'\b(\w+)\s\1\b'
result = re.search(pattern, text)
print(result.group(0)) # Output: scary scary

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

💬 Другой пример
Существуют конструкции lookahead и lookbehind, позволяющие проверять условия, не двигаясь по строке. Так, если мы хотим найти слово "cat", но только при условии, что после него следует пробел или знак препинания, то это можно реализовать следующим образом:

import re

text = "I have a cat. My friend has two cats!"
pattern = r"\bcat\b(?=[\W\s])"
matches = re.findall(pattern, text)
print(matches)  # Output: ['cat']

В данном случае результат будет содержать единственное слово "cat", так как второе вхождение не отвечает нашим условиям.

💡 Заключение
Современные реализации регулярных выражений содержат возможности, делающие их значительно более мощными инструментами, чем предполагалось изначально. И это же делает "регулярки" нерегулярными.

P.S. Осознаю, что приведённые рассуждения и примеры могут выглядеть сложными, а я фактически никак не прокомментировал, как работают конструкции из примеров. Это было сделано осознанно, так как целью было сжато проиллюстрировать справедливость тезиса из заголовка. При необходимости вы сможете найти более детальное описание интересующих вас аспектов в открытых источниках.

#любопытное #программирование

🔥3👍1

258 views04:11