Backtracking, атомарные группы, условные выражения, рекурсия
Продвинутые возможности регулярных выражений: backtracking, атомарные группы, условные выражения, рекурсия. Эти техники решают сложные задачи парсинга.
Backtracking — механизм, при котором движок regex возвращается назад для поиска альтернативных совпадений.
import re
# Шаблон ищет 'a' один или более, затем 'b'
re.search(r'a+b', 'aaaaac') # None
# Процесс:
# 1. a+ захватывает 'aaaaa' (жадно)
# 2. b несоответствует 'c' — неудача
# 3. Backtracking: a+ отдаёт одну 'a'
# 4. b несоответствует 'a' — неудача
# 5. Продолжается, пока a+ не отдаст все 'a'
# 6. b несоответствует 'a', результат NoneЭкспоненциальное время выполнения из-за неудачного backtracking:
# Опасный паттерн
pattern = r'(a+)+b'
text = 'a' * 30 + 'c'
# re.search(pattern, text) # Будет выполняться очень долго!
# Почему: (a+)+ может разбить 'aaaa' множеством способов:
# aaaa = (a)(a)(a)(a) = (aa)(a)(a) = (aa)(aa) = (aaa)(a) = ...# 1. Упростите паттерн
r'(a+)+b' # → r'a+b'
# 2. Используйте атомарные группы (в библиотеке regex)
import regex
regex.search(r'(?>a+)b', 'aaaaac') # Быстро вернёт None
# 3. Используйте possessive квантификаторы (в regex)
regex.search(r'a++b', 'aaaaac') # Быстро вернёт None
# 4. Ограничьте количество повторений
r'(a{1,100})+b' # Ограничение 100Атомарные группы не допускают backtracking внутри себя.
Примечание: В стандартном
reнет атомарных групп. Используйте библиотекуregex.
import regex
# Атомарная группа
pattern = r'(?>a+)b'
# 'a+' захватит все 'a' и не отдаст при backtracking
regex.search(pattern, 'aaab') # 'aaab'
regex.search(pattern, 'aaac') # None — быстро, без backtracking# Парсинг логов с известным форматом
pattern = r'(?>\d{4}-\d{2}-\d{2})\s+(?>\d{2}:\d{2}:\d{2})'
# Извлечение данных без backtracking
pattern = r'(?>[\w.-]+)@(?>[\w.-]+)'Possessive квантификаторы захватывают максимум и не отдают при backtracking.
Примечание: Только в библиотеке
regex.
import regex
# Possessive квантификаторы: *+ ++ ?+ {n,m}+
regex.search(r'a++b', 'aaab') # 'aaab'
regex.search(r'a++b', 'aaac') # None — быстро
# Сравнение с жадным:
re.search(r'a+b', 'aaac') # Медленно — backtracking
regex.search(r'a++b', 'aaac') # Быстро — нет backtrackingУсловные выражения выполняют разные паттерны в зависимости от условия.
(?(condition)yes-pattern|no-pattern)
(?(condition)yes-pattern) # без else
(?(1)yes|no) — если группа 1 захватила(?(name)yes|no) — если именованная группа захватила(?(?=pattern)yes|no)# Если есть первая группа, использовать один паттерн, иначе другой
pattern = r'(\()?(\d{3})(?(1)\)|-)(\d{4})'
#соответствует: (123)4567 или 123-4567
re.search(pattern, '(123)4567') # Match
re.search(pattern, '123-4567') # Match
re.search(pattern, '1234567') # Matchpattern = r'(?P<paren>\()?(?P<digits>\d{3})(?(paren)\)|-)(?P<last>\d{4})'
match = re.search(pattern, '(123)4567')
if match:
has_paren = bool(match.group('paren')) # TrueРекурсивные паттернысоответствует вложенные структуры.
Примечание: Только в библиотеке
regex.
(?R) — рекурсия всего паттерна
(?1) — рекурсия первой группы
(?P>name) — рекурсия именованной группы
import regex
#соответствует сбалансированные скобки
pattern = r'\((?:[^()]|(?R))*\)'
regex.search(pattern, '(a(b)c)') # '(a(b)c)'
regex.search(pattern, '((()))') # '((()))'
regex.search(pattern, '(()') # None — несбалансированные#соответствует вложенные HTML теги
pattern = r'<div>(?:[^<>]|(?R))*</div>'
html = '<div>outer<div>inner</div>outer</div>'
regex.search(pattern, html) #соответствует весь div# Unicode категории символов
pattern = r'\p{L}+' # Любые буквы (Letter)
pattern = r'\p{N}+' # Любые цифры (Number)
pattern = r'\p{Zs}+' # Пробельные разделители
regex.search(r'\p{L}+', 'Привет') # 'Привет'
regex.search(r'\p{Cyrillic}+', 'Привет') # 'Привет'#соответствует эмодзи
pattern = r'\p{Emoji}+'
#соответствует китайские иероглифы
pattern = r'\p{Han}+'Извлечение контекста вокруг совпадений:
# Найти слова с контекстом
text = 'The quick brown fox jumps over the lazy dog'
# Слово с 5 символами до и после
pattern = r'(.{0,5})fox(.{0,5})'
match = re.search(pattern, text)
if match:
before = match.group(1) # 'wn '
after = match.group(2) # ' jump'# С библиотекой regex
import regex
def is_balanced(s):
pattern = r'^[^()]*+(?:\((?R)\)[^()]*+)*$'
return bool(regex.fullmatch(pattern, s))
is_balanced('(a(b)c)') # True
is_balanced('(()') # False# Простое выражение: число, оператор, число
pattern = r'(\d+)\s*([+\-*/])\s*(\d+)'
match = re.search(pattern, '10 + 20')
if match:
a, op, b = match.groups()
result = eval(f'{a}{op}{b}') # 30# С библиотекой regex
pattern = r'"(?:[^"\\]|\\.)*"'
text = '"hello" and "world with \"nested\" quotes"'
regex.findall(pattern, text)# Email с комментариями в скобках
pattern = r'(?:(?:\([^)]*\))?\s*)*([\w.-]+@[\w.-]+\.[a-zA-Z]{2,})'
text = 'Contact (work) user@example.com (personal)'
match = re.search(pattern, text)
email = match.group(1) # 'user@example.com'# Плохо: вложенные квантификаторы
r'(a+)+b'
# Хорошо: упростите
r'a+b'# Плохо: backtracking
r'(\d+)+:'
# Хорошо: атомарная группа (в regex)
r'(?>\d+):'# Плохо: слишком общий
r'.*<div>.*'
# Хорошо: конкретный
r'[^<]*<div>[^<]*'# Плохо: поиск по всей строке
r'\d{4}-\d{2}-\d{2}'
# Хорошо: с якорями, если известно положение
r'^\d{4}-\d{2}-\d{2}$'# Опасно: может зациклиться
pattern = r'(?R)+'
# Безопасно: с ограничением
pattern = r'(?R){0,100}'# Ошибка: точкасоответствует любой символ
r'<div>.*</div>'
# Правильно: нежадный захват
r'<div>.*?</div>'# Ошибка: условие всегда истинно
r'(?(1)a|b)' # Группа 1 всегда "существует" в условии
# Правильно: проверка на захват
r'()(?(1)a|b)' # Группа 1 пуста, условие ложно(?>...) и possessive квантификаторы предотвращают backtracking(?(condition)yes|no) для разных паттернов(?R) для вложенных структур (в regex)\p{L}, \p{N} для работы с международным текстомregex для продвинутых возможностейВопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.