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

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

Последовательность строк
Шаблон, состоящий из обычных и спецсимволов
Подстановка [под]строки в шаблон ([searching] / matching)
Фильтрация строк как соответствующих или не соответствующих шаблону

Шаблоны shell

glob
- Си: glob
```
   1 #include <stdio.h>
   2 #include <glob.h>
   3 
   4 int main(int argc, char *argv[]) {
   5         glob_t buffer;
   6         int i;
   7 
   8         for(i=1; i<argc; i++)
   9                 glob(argv[i], i>1? GLOB_APPEND : 0, NULL, &buffer);
  10         for(i=0; i<buffer.gl_pathc; i++)
  11                 puts(buffer.gl_pathv[i]);
  12         globfree(&buffer);
  13         return 0;
  14 }
```
В шелле: генерация имён файлов и шаблоны в 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, с хранением дерева разбора в памяти
Ограничение: шаблон не зависит от контекста, части шаблона не зависят друг от друга
«Птичий язык»

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

Атомарное:
- Любой неспециальный символ
- "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»
- Группировка: любое составное РВ в скобках "$" и "$" (см. далее)
Повторители
- "атомарноеРВ*" — 0 или больше вхождений атомарногоРВ
- "a*" → «aaa»
- "a*" → «»
- "a*" → «a»
- "[0-9]*" → «7»
- "[0-9]*" → «»
- "[0-9]*" → «1231234»
- ".*" → любая строка!
Составное регулярное выражение
- Последовательность атомарных РВ. Подставляется в строку
  - которую можно разделить на подстроки
  - в каждую из которых подставляется очередное атомарное РВ
- "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»
Позиционирование
- "^regexp" — только в начале строки
- "regexp$" — только в конце строки
Принцип группирования: «самый левый, самый длинный»
- Из всех успешных сопоставлений составного РВ строке выбираются те, в которых сопоставление первого атомарного РВ ближе всего к началу,
- Из выбранных сопоставлений выбираются те, в котором это сопоставление — самое длинное
- …то же для следующего атомарного РВ и т. д.

Алгоритм NFA (с откатом) "aabb" ? "abb*":

"aabbb" → "abb*"
нет соответствия для "b", откат на следующее соответствие для "a"
"aabbb" → "abb*"
"aabbb" → "abb*"
"aabbb" → "abb*"

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

Разные понятия об использовании "\\" — POSIX, GNU, extended regex, Lisp, чёрт в ступе…
В частности, почти всегда есть расширенные регулярные выражения (extended regex) — sed -E, grep -E, awk (свой диалект) и т. п. Отличия extended regex:
- Круглые и фигурные скобки — это спецсимволы, а "\)" … "\{" — это скобки
- Спецповторители "+", "?" и "{число}"/"{число,число}" (а "\+ и "\?" — это «+» и «?»)
- классы символов
- "[[:alnum:].]+" → «2.3e1.2dsf3e..12asdf3.e123e.»
- Альтернатива "|": хотя бы одно из выражений
- "[ab]+|[cd]+" → «ababaabab»
- "[ab]+|[cd]+" → «dcccdccdc»

А ещё в разных языках разные правила квотирования, независимо от того, РВ это или нет

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

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

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

cal | grep "Ч$.$ П\1"
cal | grep "$.$0 \11 \12

Ограничение стандартного синтаксиса: карманов всего 9, \11 — это \1 и символ 1

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

(документация, она же info sed)
Подстановка в sed 's/регулярное_выражение/подстановка/'
date | sed 's/[0-9]/#/'
date | sed 's/[0-9]/#/g'
date | sed 's/[0-9]*/#/'

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

   1 $ date | sed 's/\([0-9][0-9]*\)/<\1>/'
   2 Вт <17> окт 2023 07:29:55 UTC
   3 $ date | sed 's/\([0-9][0-9]*\)/<\1>/g'
   4 Вт <17> окт <2023> <07>:<30>:<11> UTC
   5 $ date | sed -E "s/([[:digit:]]+)(.*)([[:digit:]]+)/<1=\1><2=\2><3=\3>/"
   6 Вт <1=17><2= окт 2023 07:30:3><3=1> UTC
   7 $ date | sed -E "s/(([[:digit:]]+).*)([[:digit:]]+)/<1=\1><2=\2><3=\3>/"
   8 Вт <1=17 окт 2023 07:31:1><2=17><3=3> UTC
   9

Уже видно, что такое «птичий язык», он же «write only» синтаксис.

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

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

TODO Переписать на sed s//

".*.*" → 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»

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

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

Пример на stackoverflow

Примеры:

Аналог cat с помощью getline / puts (сокращённый пример с лишними переводами строк)

   1 #include <stdio.h>
   2 
   3 int main(int argc, char *argv[]) {
   4         char *buf;
   5         size_t len = 0;
   6         int chars;
   7 
   8         for(buf = NULL; (chars = getline(&buf, &len, stdin)) != -1; buf = NULL) {
   9                 puts(buf);
  10         }
  11         return 0;
  12 }

Это плохой код, он жрёт память!
Первое Правило Памяти в Си:
- Кто память выделяет, тот её и освобождает!
  - «You malloc — you free»

Результат:

   1   #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 int main(int argc, char *argv[]) {
   5         char *buf;
   6         size_t len = 0;
   7         int chars;
   8 
   9         for(buf = NULL; (chars = getline(&buf, &len, stdin)) != -1; buf = NULL) {
  10                 puts(buf);
  11                 free(buf);
  12         }
  13         return 0;
  14 }

Вводим второй параметр — regex — и используем regcomp/regexec
- для простоты nmatch=0, pmatch=NULL
- Не забываем про regfree()
```
   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <regex.h>
   4 
   5 int main(int argc, char *argv[]) {
   6         char *buf;
   7         size_t len = 0;
   8         int chars;
   9         regex_t regex;
  10 
  11         regcomp(&regex, argv[1], 0);
  12 
  13         for (buf = NULL; (chars = getline(&buf, &len, stdin)) != -1; buf = NULL) {
  14                 buf[chars - 1] = 0;
  15                 if (regexec(&regex, buf, 0, NULL, 0) == 0)
  16                         puts(buf);
  17                 free(buf);
  18         }
  19         regfree(&regex)
  20         return 0;
  21 }
```
- Второе Правило Памяти в Си:
  - Если кто-то выделил для тебя память, освобождать всё равно тебе!
- Это всё ещё плохой код, в нём ни одна ошибка не проверяется
- Первое Правило Кода Ошибок с Си:
  Всегда проверяй код ошибки
- Допишем просто проверку regcomp() на 0, но надо использовать regerror)

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

Фиксированное количество карманов (нулевой — это вся подстрока)

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <regex.h>
   4 
   5 #define MAXGR 10
   6 
   7 int main(int argc, char *argv[]) {
   8         char *buf;
   9         size_t len = 0;
  10         int chars;
  11         regex_t regex;
  12         regmatch_t bags[MAXGR];
  13 
  14 
  15         regcomp(&regex, argv[1], 0);
  16 
  17         for (buf = NULL; (chars = getline(&buf, &len, stdin)) != -1; buf = NULL) {
  18                 buf[chars - 1] = 0;
  19                 if (regexec(&regex, buf, MAXGR, bags, 0) == 0) {
  20                         puts(buf);
  21                         for(int i=0; i<MAXGR && bags[i].rm_so>=0; i++) {
  22                                 int b = bags[i].rm_so, e = bags[i].rm_eo;
  23                                 printf("%d %d/%d\t%.*s\n", i, b, e, e - b, buf + b);
  24                         }
  25                 }
  26                 free(buf);
  27         }
  28         regfree(&regex);
  29         return 0;
  30 }

FYKI: библиотечные вызовы, в которых мне не проверили код ошибки:
- regcomp()
- regexec()
- puts()
- printf()

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

Нерегулярные выражения — PCRE / re:
- + нежадные повторители
- + пред/постпросмотр)
(не успеем) libpcre
- Документация: pcre и далее по ссылкам ещё десятка четыре руководств
- В частности, pcresyntax и pcrepattern

См. соответствующую лекцию «допглав» по курсу Python этого семестра (запланирована через три дня)

Если вы хотите использовать многобайтовую кодировку (например, UTF8), классические POSIX регулярные выражения не подойдут. Хорошая альтернатива — это как раз pcre.

Д/З

Почитать про регулярные выражения
- в документации (можно найти русский перевод)
- в учебнике
- в другом учебнике
- (вообще смешного много)
- Поискать The книгу
Потренироваться! (обратите внимание на то, что большинство сайтов поддерживают Python или PCRE, или Javascript, но не классические RE).
Написать программу esub с параметрами regexp substitution string, которая работает примерно как echo 'string' | sed -E 's/regexp/substitution/' (однократная замена). Предупреждаю: надо уметь программировать на Си.
- Используются расширенные регулярные выражения (так меньше «\»)
- Программа должна распознавать ошибки в регулярном выражении и выводить соответствующую диагностику с помощью regerror
- В строке substitution программа должна распознавать ссылки на соответствующие «карманы» (самих карманов 9, ссылок может быть не более 100). Также должны распознаваться и ссылки на несуществующие карманы (например, \9 если в выражении нет стольких пар скобок — это ошибка), и конструкция «\\», которая должна заменяться на «\»
  - Следите за количеством этих «\» — оно имеет тенденцию уменьшаться вдвое при каждой обработке, да ещё в разных шеллах работать по-разному, не запутайтесь!
Необязательное усложнение: реализовать режим раскрашивания (как в grep, только лучше), в котором подстановка из каждого кармана окрашивается в свой цвет
Написать Makefile, в который включить сборку, удаление генератов и тесты, где вывод esub сравнивается с выводом соответствующей команды sed -E s/…/…/
Создать в каталоге с домашними заданиями подкаталог 05_Regexps и поместить туда проект

Решение от 2024-10-17

Чётные карманы отмечены подчёркиванием, нечётные — полужирным
Есть сравнение с аналогичной командой sed
Исходное видео

LecturesCMC/LinuxApplicationDevelopment2025/05_Regexps (последним исправлял пользователь FrBrGeorge 2025-10-14 18:28:38)