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

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

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

Шаблоны 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. Принцип группирования: «самый левый, самый длинный»

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

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

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

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

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

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

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

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

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

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 }

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

      • Если кто-то выделил для тебя память, освобождать всё равно тебе!

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

    • Первое правило кода ошибок с Си:

      Всегда проверяй код ошибки

    • Доделаем на лекции

  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;

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

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

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

Д/З

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

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

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

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

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

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

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

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

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

LecturesCMC/LinuxApplicationDevelopment2023/05_Regexps (последним исправлял пользователь FrBrGeorge 2023-10-17 17:19:39)