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

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

Шаблоны 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. Атомарное:
    • Любой неспециальный символ

    • "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$" — только в конце строки

  5. Принцип группирования: «самый левый, самый длинный»

    • Из всех успешных сопоставлений составного РВ строке выбираются те, в которых сопоставление первого атомарного РВ ближе всего к началу,

    • Из выбранных сопоставлений выбираются те, в котором это сопоставление — самое длинное
    • …то же для следующего атомарного РВ и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример на stackoverflow

Примеры:

  1. Аналог 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 }

    • <!> Это плохой код, он жрёт память!

    • Первое Правило Памяти в Си:

      • Кто память выделяет, тот её и освобождвет!
    • Результат: 
         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 }

  2. Вводим второй параметр — 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)

  3. Разбор карманов (там же в 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 }

      • <!> Это плохой код, в нём ни одна ошибка не проверяется, ну уж ладно

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

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

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

Д/З

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

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

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

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

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

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

  4. <!> Необязательное усложнение: реализовать режим раскрашивания (как в grep, только лучше), в котором подстановка из каждого кармана окрашивается в свой цвет

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

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

<!> Решение от 2024-10-17

esub.mp4

LecturesCMC/LinuxApplicationDevelopment2024/05_Regexps (последним исправлял пользователь FrBrGeorge 2024-10-17 18:37:59)