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

Принцип: сопоставление строки шаблону

Шаблоны (например, в 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:

      1. A ← "A*" или

      2. A ← "A*A", потому что ← "A*" и для третьего символа РВ A ← "A", т. е.

    • AA:

      1. AA ← "A*"

      2. AA ≠ "A*AB", потому что для четвёртого символа РВ A ≠ "B"

      3. AA ← "A*A", где A ← "A*" и A ← "A"

    • AAB:

      1. AAB ≠ "A*A", потому что B ≠ "A"

      2. уже ≠

      3. 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')

• нежадные повторители (опасность полного перебора).
• пред- и пост-просмотр

Д/З

• MRE — можно и не осилить, да

• Знаменитые «10 задач по регулярным выражениям» (да, задачу № 7 делать не надо, это толстый троллинг)