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

Лекция в курсе АКОС ВШЭ

Общий принцип

• Последовательность строк

• Шаблон, состоящий их обычных и спецсимволов

• Подстановка [под]строки в шаблон ([searching] / matching)

• Фильтрация строк как соответствующих или не соответствующих шаблону

Шаблоны shell

• glob

  • Си: glob

• В шелле: генерация имён файлов и шаблоны в case

  • Подстановкой занимается сам shell

Довольно слабый язык

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

Mastering Regular Expressions Джеффри Фридла (ака The Owl Book).

Инструмент: grep --color

О названии grep:

george@grep:~> grep '[12]0' o
    Октябрь 2022    
10 11 12 13 14 15 16
17 18 19 20 21 22 23
george@grep:~> ed o
189
# g/re/p
g/[12]0/p
    Октябрь 2022    
10 11 12 13 14 15 16
17 18 19 20 21 22 23

• Самый строгий из формальных языков по Хомскому

  • ⇒ простой разбор и алгоритм сопоставления. В действительности их два:
    1. Основанный на выражении: NFA, с откатом разбора
    2. Основанный на строке: DFA, с хранением дерева разбора в памяти
• Ограничение: шаблон не зависит от контекста, части шаблона не зависят друг от друга
• «Птичий язык»

Определение регулярного выражения

1. Атомарное:
   • Любой неспециальный символ

   • "E" → «E»

   • Точка "." — любой один символ

   • . "." → «E»

   • "." → «:»

   • "." → «.»

   • Диапазон — любой один символ из диапазона

   • "[quack!]" → «a»

   • "[quack!]" → «!»

   • "[a-z]" → «q» (любая строчная буква)

   • "[a-z]" → «z» (любая строчная буква)

   • "[a-fA-F0-9]" → «f» (любое шестнадцатеричное число)

   • "[0-9A-Fa-f]" → «D» (любое шестнадцатеричное число)

   • "[bdefAEDFC0-9Bca]" → «4» (любое шестнадцатеричное число)

   • Выключенный диапазон — любой один символ не из диапазона

   • "[^quack!]" → «r»

   • "[^quack!]" → «#»

   • "[^quack!]" → «A»

   • Группировка: любое составное РВ в скобках "\(" и "\)" (см. далее)

2. Повторители

   • "атомарноеРВ*" — 0 или больше вхождений атомарногоРВ

   • "a*" → «aaa»

   • "a*" → «»

   • "a*" → «a»

   • "[0-9]*" → «7»

   • "[0-9]*" → «»

   • "[0-9]*" → «1231234»

   • ".*" → любая строка!

3. Составное регулярное выражение

   • Последовательность атомарных РВ. Подставляется в строку
     • которую можно разделить на подстроки
     • в каждую из которых подставляется очередное атомарное РВ

   • "boo" → «boo»

   • "r....e" → «riddle»

   • "r....e" → «r re e»

   • "[0-9][0-9]*" → неотрицательное целое

   • "[A-Za-z_][A-Za-z0-9]*" → Идентификатор (например, в Си)

   • Группировка превращает составное выражение в атомарное, так что после него можно использовать повторитель

   • "\([A-Z][a-z]\)*" → «ReGeXp»

   • "\([A-Z][a-z]\)*" → «»

   • "\([A-Z][a-z]\)*" → «Oi»

   • Жадный алгоритм: самый левый — самый длинный

4. Позиционирование

   • "^regexp" — только в начале строки

   • "regexp$" — только в конце строки

Жадный алгоритм

В успешной подстановке составного РВ первому (самому левому) атомарному РВ соответствует самая длинная из возможных подстрок. То же самое применимо к оставшейся группе атомарных РВ и оставшейся строке.

• ".*.*" → all the string leftmost, empty string next

• "[a-z]*[0-9]*[a-z0-9]*" → «123b0c0»

  • "[a-z]*" → «»

  • "[0-9]*" → «123»

  • "[a-z0-9]*" → «b0c0»

• "[a-d]*[c-f]*[d-h]*" → «abcdefgh»

  • "[a-d]*" → «abcd»

  • "[c-f]*" → «ef»

  • "[d-h]*" → «gh»

Поиск с заменой и обратные ссылки

Инструмент: sed 's/регулярное_выражение/подстановка/'

• Понятия кармана "\(…\)" и подстановки "\номер"

• TODO пример

• Правила нумерации карманов, в т. ч. вложенных

• TODO пример

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

Семинар в курсе АКОС ВШЭ

Пример на stackoverflow

Примеры:

0. Аналог cat с помощью getline (сокращённый пример)

1. Вводим второй параметр — regex — и используем regcomp/regexec

   • для простоты nmatch=0, pmatch=NULL

   • regfree()

   • TODO пример

2. Разбор карманов (там же в regexec)

   • Фиксированное количество карманов
   • Кусок кода:

       if(!regexec(&r, line, MAXGR, pm, 0)) {
               fputs(line, stdout);
               for(i=0; i<MAXGR && pm[i].rm_so>=0; i++)
                       printf("\t%d/%d\n", pm[i].rm_so, pm[i].rm_eo);
       }

   • TODO пример

Варианты синтаксиса

• Разные понятия об использовании "\\" — PoSIX, GNU, extended regex, Lisp, чёрт в ступе…

• extended regex: классы символов, "+", "?", "|"

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

• Нерегулярные выражения — PCRE / re:

  • + нежадные повторители
  • + пред/постпросмотр)

• (не успеем) libpcre

Д/З

0. Почитать про регулярные выражения

   • в документации (можно найти русский перевод)

   • в учебнике

   • в другом учебнике

   • (вообще смешного много)

   • Поискать The книгу

1. Потренироваться! (обратите внимание на то, что большинство сайтов поддерживают Python или PCRE, или Javascript, но не классические RE).

2. Написать программу esub с параметрами regexp substitution string, которая работает примерно как echo 'string' | sed -E 's/regexp/substitution/' (однократная замена). Предупреждаю: надо уметь программировать на Си.

   • Используются расширенные регулярные выражения (так меньше «\»)

   • Программа должна распознавать ошибки в регулярном выражении и выводить соответствующую диагностику с помощью regerror

   • В строке substitution программа должна распознавать ссылки на соответствующие «карманы». Также должны распознаваться и ссылки на несуществующие карманы (например, \9 если в выражении нет стольких пар скобок — это ошибка), и конструкция «\\», которая должна заменяться на «\»

     • Следите за количеством этих «\» — оно имеет тенденцию уменьшаться вдвое при каждой обработке, да ещё в разных шеллах работать по-разному, не запутайтесь!

       george@linuxprac:~> /bin/echo 123\456
       123456
       george@linuxprac:~> /bin/echo "123\456"
       123\456
       george@linuxprac:~> /bin/echo "123\\456"
       123\456
       george@linuxprac:~> /bin/echo "123\\\456"
       123\\456
       george@linuxprac:~> /bin/echo "123\\\\456"
       123\\456
       george@linuxprac:~> # а сейчас мерзкий трюк — echo, встроенный в Zsh
       george@linuxprac:~> echo "123\\\\456"
       123\456
       george@linuxprac:~> echo "123\\\\\\\\\\456"
       123\\\456

3. Написать Makefile, в который включить сборку, удаление генератов и тесты, где вывод esub сравнивается с выводом соответствующей команды sed -E s/…/…/

4. Создать в каталоге с домашними заданиями подкаталог 06_Regexps и поместить туда проект