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

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

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

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

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

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

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

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

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

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

Пример на stackoverflow

Примеры:

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

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

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

    • regfree()

    • TODO пример

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

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

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

Д/З

  1. Почитать про регулярные выражения
  2. Потренироваться! (обратите внимание на то, что большинство сайтов поддерживают Python или PCRE, или Javascript, но не классические RE).
  3. Написать программу 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
  4. Написать Makefile, в который включить сборку, удаление генератов и тесты, где вывод esub сравнивается с выводом соответствующей команды sed -E s/…/…/

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

LecturesCMC/LinuxApplicationDevelopment2022/06_Regexps (последним исправлял пользователь FrBrGeorge 2022-10-26 16:30:24)