[UNИХ] Программное обеспечение GNU/Linux - 06 - Регулярные выражения (2017-11-08)
http://uneex.org
Регулярные выражения - http://uneex.org/LecturesCMC/LinuxSof...
Принцип: сопоставление строки шаблону
Шаблоны (например, в 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')
нежадные повторители (опасность полного перебора).
пред- и пост-просмотр