[UNИХ] Программное обеспечение GNU/Linux - 06 - Регулярные выражения (2017-11-08)
uneex.org
Регулярные выражения — uneex.org/LecturesCMC/LinuxSoftware2017/06_Regexp
Принцип: сопоставление строки шаблону
Шаблоны (например, в flename generation) и их недостатки.
Язык: *? [a-z] [^a-z]
⇒ целое число? :(
… (ещё антипримеры?)
Задание и принцип работы РВ
⇒ Более общий механизм? (Хомский: формальный грамматики)
автоматные (регулярные) грамматики — имеют (относительно) низкую вычислительную сложность сопоставления
Примеры:
grep,
поиск с заменой: sed, нумерация и подстановка карманов
Синтаксис:
«просто_символ» → просто символ
"." → один любой символ
"[символы]" или "[диапазон-символов]" или "[и то и то]" → один символ из диапазона
(повторитель) «атомарное_РВ*» → строка, сопоставимая атомарному_РВ, повторенному 0 или более раз (в частности, пустая)
«РВ1РВ2…РВN» → строка, которую можно разбить на последовательные части, сопоставимые РВ1…РВN соответственно
Принцип однозначности: самое левое сопоставление — самое длинное
(группа) "(РВ1РВ2…РВN)" → атомарное регулярное выражение (можно помечать повторителем)
группа == карман (так вышло)
(позиционирование) "^" и "$" → начало и конец строки (не сопоставляются символам строки, только отмечают позицию)
Регулярные выражения и конечные автоматы
NFA — «поиск с возвратом»
«A.*B.*A»? wAtBlABlAs по правилу «самый левый самый длинный»
DFA — «сопоставление»
«A*AB? AAB
A:
A ← „A*“ или
A ← „A*A“, потому что ← „A*“ и для третьего символа РВ A ← „A“, т. е.
AA:
AA ← „A*“
AA ≠ „A*AB“, потому что для четвёртого символа РВ A ≠ „B“
AA ← „A*A“, где A ← „A*“ и A ← „A“
AAB:
AAB ≠ „A*A“, потому что B ≠ „A“
уже ≠
AAB ← „A*AB“, потому что AA ← „A*A“ и B ← „B“
Расширенные РВ
Альтернатива „РВ1|РВ2“ → строка, сопоставимая или с РВ1 или с РВ2
Повторители » " (1 и более раз) и "?" (0 или 1 раз)
Повторитель «количество}» и "{[миниум],[максимум]}"
Классы эквивалентности в диапазонах
Эквивалентность базовым РВ
Утилиты: tr, grep / egrep / fgrep, awk, less, vi / vim, …
Flavours
Закавычивание с помощью \
Именование карманов
Незапоминаемые группы
Базовые или расширенные
Полезности: индикаторы начал/концов слов и т. п.
многострочные РВ
…
Нерегулярные выражения
Perl/PCRE, Python, иное
обратные ссылки на группы (есть в egrep: cal | egrep ([0-9])4.*\1)
нежадные повторители (опасность полного перебора).
пред- и пост-просмотр