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

Git и GitHub

Система управления версиями (CVS) - один из основных инструментов программиста. Система управления версиями позволяет хранить несколько версий одного и того же документа, при необходимости возвращаться к более ранним версиям, определять, кто и когда сделал то или иное изменение, и многое другое.

Git — одна из самых популярных систем контроля версиями (CVS). Автор git — Линус Торвальдс.

GitHub — крупнейший веб-сервис для хостинга IT-проектов и их совместной разработки.

Упражнение 0. Git

Пройдите туториал и продемонстрируйте преподавателю тестовый репозиторий на гитхабе.

1. Зарегистрируйтесь на github.com с некоторым именем пользователя, например Ivanov (тут и далее вместо Ivanov нужно подставлять имя вашего пользователя, а вместо ivanov.ivan@someuniversity.edu вашу настоящую почту).

  1. Создаем новый репозиторий https://github.com/new (или значок + в правом верхнем углу):
    • В качестве имени репозитория задаем infa_2020_ivanov
    • Доступ оставляем Public
    • Не забываем поставить галочку "Initialize this repository with a README"

3. Откройте терминал (консоль) GNU/Linux или командную строку Git-bash под M$ Windows. Теперь git clone — склонируем получившийся репозиторий на свой компьютер и зайдем в папку с репозиторием:

$ git clone https://github.com/Ivanov/infa_2020_ivanov
Cloning into 'infa_2020_ivanov'...
remote: Counting objects: 3, done.
remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (3/3), done.
$ ls
infa_2020_ivanov
$ cd infa_2020_ivanov
$ ls
README.md

Не забудем сконфигурить гит, представившись ему (это обязательно нужно сделать находясь в папке infa_2020_ivanov):

git config user.name "Ivanov Ivan"
git config user.email ivanov.ivan@someuniversity.edu

Почту указываем как при регистрации.

4. Теперь у нас локально есть полная и независимая версия нашего репозитория infa_2020_ivanov. Она никак явным образом не связана с версией на серверах github'а, однако в гите существуют инструменты для обмена данными между разными репозиториями. Иными словами, git - это распределенная система управлениями версиями.

  1. Команда git log возвращает историю нашего репозитория. В данный момент в нашей истории ровно один коммит (коммит - это некоторый набор изменений).
-> git log
commit eec733a21cerfb66973991a9357aab735fa40ba4
Author: Ivanov <ivanov.ivan@someuniversity.edu>
Date:   Wed Sep 16 12:06:08 2020 +0300

    Initial commit

6. Давайте отредактируем файл README.md и добавим в него что-нибудь. Откроем файл README.md и напишем в нем что-нибудь. После с помощью git diff посмотрим на текущие изменения. В "диффе" видно, что была добавлена строчка "it's test project".

-> git diff
diff --git a/README.md b/README.md
index 21e60f8..285eafa 100644
--- a/README.md
+++ b/README.md
@@ -1 +1,3 @@
-# infa_2020_ivanov
\ No newline at end of file
+# infa_2020_ivanov
+
+it\'s test project

7. Команда git status показывает текущий статус репозитория. Мы видим, что сейчас мы находимся в ветке master (основная ветка нашего репозитория). Ниже написано, что файл README.md был изменен. Однако он ещё не готов для коммита.

-> git status
# On branch master
# Changes not staged for commit:
#   (use "git add <file>..." to update what will be committed)
#   (use "git checkout -- <file>..." to discard changes in working directory)
#
#    modified:   README.md
#
no changes added to commit (use "git add" and/or "git commit -a")
  1. Сделаем git add, как рекомендует нам команда status.
-> git add README.md
-> git status
# On branch master
# Changes to be committed:
#   (use "git reset HEAD <file>..." to unstage)
#
#    modified:   README.md
#

Теперь git status показывает, что изменения в файле README.md готовы для коммита. Если сейчас снова измененить README.md, то нужно снова обязательно выполнить git add.

  1. git-commit — закоммитим наши изменения, то есть внесём "квант" изменений в историю развития проекта:
$ git commit -m "Added something to README"
[master 274f6d5] Added something to README
 Committer: Ivanov Ivan <ivanov.ivan@someuniversity.edu>

 1 file changed, 3 insertions(+), 1 deletion(-)
  1. Снова посмотрим (git log) на историю нашего репозитория:
$ git log
commit 8e2642d512b11ae43a97b0b4ac68e802d2626f14
Author: Ivanov Ivan <ivanov.ivan@someuniversity.edu>
Date:   Wed Nov 9 14:47:40 2016 +0300

    Added something to README

commit eec733a21cerfb66973998a9327aab735fa40ba4
Author: Ivanov Ivan <ivanov.ivan@someuniversity.edu>
Date:   Wed Nov 9 13:36:38 2016 +0300

    Initial commit

Теперь в нашем репозитории два коммита.

  1. Давайте сделаем git push — отправим ("запушим" на сленге программистов) наши изменения в оригинальный репозиторий на github.com.
$ git push
Username for 'https://github.com': <username>
Password for 'https://ivanov@github.com': <password>
To https://github.com/Ivanov/infa_2020_ivanov
   eec733a..8e2642d  master -> master

При git push необходимо будет ввести логин и пароль на GitHub (если, конечно, вы не настроили ssh-аутентификацию :-)). Теперь изменения будут доступны для всех.

  1. Существует парная команда git pull — которая забирает изменения с оригинального репозитория на сервере.
$ git pull
Already up-to-date.

Сопоставление с образцом

Очень часто при обработке текстовых данных возникает задача о сопоставлении строки с образцом. Самый простой пример — проверка корректности вводимых пользователем данных. Допустим, у нас имеются следующие требования к паролю, используемому в системе:

  • пароль должен иметь длину не меньше 6 символов, но не больше 15;
  • пароль может содержать как строчные, так и прописные буквы, а также цифры;
  • пароль должен начинаться с заглавной буквы, а заканчиваться строчной буквой.

В принципе, можно написать функцию, которая будет проверять, соответствует ли строка предъявляемым требованиям:

def check_password(s):
    if not 6 <= len(s) <= 15:
        return False
    if not 'A' <= s[0] <= 'Z':
        return False
    if not 'a' <= s[-1] <= 'z':
        return False
    for c in s[1:-1]:
        if not ('a' <= c <= 'z' or 'A' <= c <= 'Z' or '0' <= c <= '9'):
            return False
    return True

А можно пойти другим путём и воспользоваться специально предназначенным для этого инструментом — регулярными выражениями:

import re

def check_password_with_regexp(s):
    return re.match(r'^[A-Z]{1}[a-zA-Z0-9]{4,13}[a-z]{1}$', s)

Как видно из примера, вид функции check_password сильно изменился. Мы не будем на данном этапе пытаться разобраться в том, как именно работает новая версия функции, а лишь отметим одно важное отличие: первая версия функции выполняла ряд проверок, пытаясь найти символ, не соответствующий предъявляемым требованиям, вторая же версия функции вместо этого выясняет, соответствует ли переданная строка заранее заданному образцу. Именно в этом и заключается основное предназначение регулярных выражений — они позволяют описать, как должна выглядеть строка, если она удовлетворяет определённым критериям.

Где используются регулярные выражения?

Регулярные выражения получили весьма широкое распространение благодаря тому, что являются достаточно мощным инструментом работы с текстовыми данными. Так, их поддержка есть в большинстве языков программирования (Python, Ruby, Perl, Java и т.д.), они используются во многих утилитах командой строки UNIX-подобных операционных систем (grep, sed, awk и т.д.). Помимо этого поддержку регулярных выражений можно встретить во многих текстовых редакторах (Vim, Emacs, Sublime Text, Notepad++ и т.д.), поскольку этот механизм позволяет достаточно просто выполнять замены символов в тексте.

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

Модуль re

Модуль re (Regular Expressions) стандартной библиотеки языка Python предоставляет набор функций и классов для работы с регулярными выражениями. Вот список наиболее часто используемых из них:

Функция Описание
re.match Ищет соответствие заданному шаблону в начале строки
re.search Ищет соответствие заданному шаблону в произвольном месте строки и возвращает первое найденное совпадение
re.findall Находит и возвращает список всех непересекающихся подстрок исходной строки, соответствующих шаблону
re.split Разбивает строку на набор подстрок с использованием шаблона для поиска разделителей
re.sub Заменяет подстроку, соответствующую шаблону, указанным значением
re.compile «Компилирует» регулярное выражение для дальнейшего использования

Теперь рассмотрим несколько примеров работы с регулярными выражениями. Пока что мы не знаем синтаксиса, используемого для описания регулярных выражений, поэтому рассмотрим самый простой случай: когда в качестве регулярного выражения выступает непосредственно искомая строка.

>>> import re
>>>
>>> s = 'с самого начала у меня была какая-то тактика, и я её придерживался'
>>>
>>> re.match('с самого', s)
<_sre.SRE_Match object; span=(0, 8), match='с самого'>
>>>
>>> re.match('была', s)
>>> re.search('была', s)
<_sre.SRE_Match object; span=(23, 27), match='была'>
>>>
>>> re.findall('и', s)
['и', 'и', 'и', 'и']
>>>
>>> re.split(' ', s)
['с', 'самого', 'начала', 'у', 'меня', 'была', 'какая-то', 'тактика,', 'и', 'я', 'её', 'придерживался']
>>> re.split(',', s)
['с самого начала у меня была какая-то тактика', ' и я её придерживался']
>>>
>>> re.sub('придерживался', 'использовал', s)
'с самого начала у меня была какая-то тактика, и я её использовал'
>>>
>>> regexp = re.compile('с самого')
>>> regexp.match(s)
<_sre.SRE_Match object; span=(0, 8), match='с самого'>

Как видно из примера, функции re.match и re.search возвращают в случает совпадения экземпляр класса SRE_Match или None, если совпадение не найдено, в то время как функции re.findall, re.split возвращают список, состоящий из строк, функция re.sub возвращает строку, получающуюся после выполнения замены.

Синтаксис регулярных выражений

Базовый синтаксис

В предыдущих примерах мы использовали искомую строку в качестве регулярного выражения. Теперь настало время познакомиться более подробно с синтаксисом описания регулярных выражений.

Помимо непосредственно искомых символов регулярное выражение может содержать специальные символы, которые позволяют задать шаблон. Вот краткий список основных из них:

Специальные символы Описание
. Любой символ, кроме символа новой строки
^ Начало строки
$ Конец строки
? 0 или 1 соответствие шаблона слева
* 0 или больше соответствий шаблона слева
+ 1 или более соответствий шаблона слева
{m} Ровно m соответствий шаблона слева
{m,n} Не меньше m, но и не больше n соответствий шаблона слева
\ Экранирование служебных символов
[abc] Любой из символов a, b, c
[^abc] Любой символ, кроме a, b, c
[0-5] Любой из символов 0, 1, 2, 3, 4, 5
[a-d] Любой из символов a, b, c, d
a|b a или b

Примеры использования:

>>> import re
>>> re.match('.', 'a')
<_sre.SRE_Match object; span=(0, 1), match='a'>
>>> re.match('.', 'b')
<_sre.SRE_Match object; span=(0, 1), match='b'>
>>> re.match('.', '.')
<_sre.SRE_Match object; span=(0, 1), match='.'>
>>> re.search('a', 'bab')
<_sre.SRE_Match object; span=(1, 2), match='a'>
>>> re.search('^a', 'bab')
>>> re.search('^a$', 'bab')
>>> re.search('a$', 'bab')
>>> re.search('^.a.$', 'bab')
<_sre.SRE_Match object; span=(0, 3), match='bab'>
>>> re.search('a?', 'bbb')
<_sre.SRE_Match object; span=(0, 0), match=''>
>>> re.search('a?', 'bab')
<_sre.SRE_Match object; span=(0, 0), match=''>
>>> re.search('a+', 'bab')
<_sre.SRE_Match object; span=(1, 2), match='a'>
>>> re.search('a+', 'baaab')
<_sre.SRE_Match object; span=(1, 4), match='aaa'>
>>> re.search('a*', 'baaab')
<_sre.SRE_Match object; span=(0, 0), match=''>
>>> re.search('ba*b', 'baaab')
<_sre.SRE_Match object; span=(0, 5), match='baaab'>
>>> re.search('ba+b', 'baaab')
<_sre.SRE_Match object; span=(0, 5), match='baaab'>
>>> re.search('ba?b', 'baaab')
>>> re.search('a{2}', 'baaab')
<_sre.SRE_Match object; span=(1, 3), match='aa'>
>>> re.search('a{3}', 'baaab')
<_sre.SRE_Match object; span=(1, 4), match='aaa'>
>>> re.search('a{4}', 'baaab')
>>> re.search('a{1}', 'baaab')
<_sre.SRE_Match object; span=(1, 2), match='a'>
>>> re.search('a{1,2}', 'baaab')
<_sre.SRE_Match object; span=(1, 3), match='aa'>
>>> re.search('a{1,3}', 'baaab')
<_sre.SRE_Match object; span=(1, 4), match='aaa'>
>>> re.search(r'\*', r'*')
<_sre.SRE_Match object; span=(0, 1), match='*'>
>>> re.search(r'[abc]', r'0123ccaabb275')
<_sre.SRE_Match object; span=(4, 5), match='c'>
>>> re.search(r'[abc]?', r'0123ccaabb275')
<_sre.SRE_Match object; span=(0, 0), match=''>
>>> re.search(r'[abc]+', r'0123ccaabb275')
<_sre.SRE_Match object; span=(4, 10), match='ccaabb'>
>>> re.search(r'[0-9]{4}[abc]+[0-9]{3}', r'0123ccaabb275')
<_sre.SRE_Match object; span=(0, 13), match='0123ccaabb275'>
>>> re.search(r'[0-9]{4}[^0-9]+[0-9]{3}', r'0123ccaabb275')
<_sre.SRE_Match object; span=(0, 13), match='0123ccaabb275'>
>>> re.search(r'a|b', r'ccadd')
<_sre.SRE_Match object; span=(2, 3), match='a'>
>>> re.search(r'a|b', r'ccbdd')
<_sre.SRE_Match object; span=(2, 3), match='b'>

Упражнение №1

Сделайте форк репозитория (локальный МФТИ), в котором содержатся заготовки программ для работы.

В файл simple_match.py впишите требуемые регулярные выражения REGEXP_1, REGEXP_2 и т.д., после чего запустите на выполнение тесты из файла simple_match_test.py. Добейтесь прохождения всех тестов.

Обратите внимание, что в файле указано ожидаемое поведение программы для конкретного набора строк, а не чёткая формулировка задания наподобие «напишите регулярное выражение, соответствующее строке, состоящей только из прописных букв». Это сделано сознательно: дело в том, что при помощи регулярных выражений обычно решают некую вполне конкретную задачу, а не какую-то абстрактную общую задачу. И поэтому во многих задачах из этой работы возможно более одного правильного решения. Например, строка ABabAB соответствует как регулярному выражению [ABab]+, так и выражению ^A.*B$, да и ещё достаточно большому количеству других выражений.

Больше специальных символов

Теперь перейдём к рассмотрению более сложных специальных символов, поддержка которых присутствует в библиотеке re. Эти символы нужны как для написания сложных, так и для сокращения длинных регулярных выражений. Неполный список специальных символов приведён в таблице ниже:

Специальный символ Описание
\A Начало строки; эквивалент ^
\b Начало слова
\B Не начало слова
\d Цифра; расширенный вариант [0-9]
\D Не цифра; «отрицание» \d
\s Пробельный символ; расширенный вариант [ \t\n\r\f\v]
\S Не пробельный символ; «отрицание» \s
\w «Буква» в слове расширенный вариант [a-zA-Z0-9_]
\W Не «буква»; «отрицание» \w
\Z Конец строки; эквивалент $

Ниже приведено несколько примеров использования этих специальных символов:

>>> import re
>>> re.match(r'\Aab', 'abcd')
<_sre.SRE_Match object; span=(0, 2), match='ab'>
>>> re.match(r'\Aab', 'dabcd')
>>> re.search(r'\bbbb', 'abbba bbb ccc')
<_sre.SRE_Match object; span=(6, 9), match='bbb'>
>>> re.search(r'\Bbbb', 'abbba bbb ccc')
<_sre.SRE_Match object; span=(1, 4), match='bbb'>
>>> re.search(r'\d+', 'ab123cd')
<_sre.SRE_Match object; span=(2, 5), match='123'>
>>> re.search(r'\D+', 'ab123cd')
<_sre.SRE_Match object; span=(0, 2), match='ab'>
>>> re.sub(r'\s+', '_', 'aa bb cc dd')
'aa_bb_cc_dd'
>>> re.findall(r'\S+', 'aa bb cc dd')
['aa', 'bb', 'cc', 'dd']
>>> re.search(r'\w+', 'ab123cd')
<_sre.SRE_Match object; span=(0, 7), match='ab123cd'>
>>> re.search(r'\W+', 'ab123cd')
>>> re.search(r'\w+', 'ab123cd  aaa')
<_sre.SRE_Match object; span=(0, 7), match='ab123cd'>
>>> re.search(r'\W+', 'ab123cd  aaa')
<_sre.SRE_Match object; span=(7, 9), match='  '>
>>> re.search(r'aa\Z', 'bbaa')
<_sre.SRE_Match object; span=(2, 4), match='aa'>
>>> re.search(r'aa\Z', 'bbaab')

Упражнение №2

В файл simple_search.py впишите требуемые регулярные выражения REGEXP_1, REGEXP_2 и т.д., после чего запустите на выполнение тесты из файла simple_search_test.py. Добейтесь прохождения всех тестов.

Упражнение №3

В файл simple_findall.py впишите требуемые регулярные выражения REGEXP_1, REGEXP_2 и т.д., после чего запустите на выполнение тесты из файла simple_findall_test.py. Добейтесь прохождения всех тестов.

Упражнение №4

В файл simple_sub.py впишите требуемые регулярные выражения и строки замены REGEXP_1 / REGEXP_1_REPL, REGEXP_2 / REGEXP_2_REPL и т.д., после чего запустите на выполнение тесты из файла simple_sub_test.py. Добейтесь прохождения всех тестов.

Группы

Зачастую бывает необходимо, чтобы специальный символ (+, * и т.д.) применялся не к одному символу слева, а определённой группе символов. Для этого нужно заключить интересующую часть шаблона в круглые скобки (…):

>>> import re
>>> re.search('(ab){3}', 'ab ab ababab ab ab')
<_sre.SRE_Match object; span=(6, 12), match='ababab'>
>>> re.search('(ab){3}', 'ab ab abab ab ab') is None
True

В некоторых случаях при обработке строковых данных при помощи регулярных выражений возникает необходимость выделить определённую часть подстроки, соответствующей шаблону. Например, рассмотрим следующую задачу: извлечь из строки 'какой-то текст, <b>текст жирным шрифтом</b>, и снова какой-то текст' подстроку, заключённую внутри тега <b>..</b>. Для этого также удобно использовать группы:

>>> import re
>>> s = 'какой-то текст, <b>текст жирным шрифтом</b>, и снова какой-то текст'
>>> m = re.search(r'<b>([\w\s]+)</b>', s)
>>> m
<_sre.SRE_Match object; span=(16, 43), match='<b>текст жирным шрифтом</b>'>
>>> m.group(1)
'текст жирным шрифтом'

Обратите внимание, что всему шаблону соответствует подстрока '<b>текст жирным шрифтом</b>', в то время как в группу попадает только нужная нам строка 'текст жирным шрифтом'.

Группы нумеруются в том порядке, в котором они перечислены в шаблоне:

>>> import re
>>> re.match('(a|b)(c|d)', 'ac').groups()
('a', 'c')
>>> re.match('(a|b)(c|d)', 'ac').group(1)
'a'
>>> re.match('(a|b)(c|d)', 'ac').group(2)
'c'
>>> re.match('(a|b)(c|d)', 'bd').groups()
('b', 'd')
>>> re.match('(a|b)(c|d)', 'bd').group(1)
'b'
>>> re.match('(a|b)(c|d)', 'bd').group(2)
'd'

Группы можно использовать внутри выражения, например, для поиска повторяющихся букв:

>>> import re
>>> re.search(r'(a|b|c)\1', 'aabc')
<_sre.SRE_Match object; span=(0, 2), match='aa'>
>>> re.search(r'(a|b|c)\1', 'abbc')
<_sre.SRE_Match object; span=(1, 3), match='bb'>
>>> re.search(r'(a|b|c)\1', 'abcc')
<_sre.SRE_Match object; span=(2, 4), match='cc'>

Группы можно использовать внутри строки замены в функции re.sub:

>>> import re
>>> re.sub('(a|b|c)', r'*\1*', 'a')
'*a*'
>>> re.sub('(a|b|c)', r'*\1*', 'abc')
'*a**b**c*'
>>> re.sub('(a|b|c)', r'*\1*', 'axbxc')
'*a*x*b*x*c*'

Если групп в выражении достаточно много, их можно именовать при помощи конструкции (?P<имя>), а затем обращаться к ним при помощи (?P=имя) внутри выражения, при помощи \g<имя> внутри строки замены или непосредственно по имени при работе с объектом SRE_match:

>>> import re
>>> re.match('(?P<group1>a|b)(?P<group2>c|d)', 'ac').groups()
('a', 'c')
>>> re.match('(?P<group1>a|b)(?P<group2>c|d)', 'ac').group('group1')
'a'
>>> re.match('(?P<group1>a|b)(?P<group2>c|d)', 'ac').group('group2')
'c'
>>> re.match('(?P<group1>a|b)(?P<group2>c|d)', 'ac').group(1)
'a'
>>> re.match('(?P<group1>a|b)(?P<group2>c|d)', 'ac').group(2)
'c'
>>> re.sub('(?P<group1>a|b)(?P<group2>c|d)', r'!\1!*\g<group2>*', 'xxacxx')
'xx!a!*c*xx'

Упражнение №5

В файл advanced_sub.py впишите требуемые регулярные выражения и строки замены REGEXP_1 / REGEXP_1_REPL, REGEXP_2 / REGEXP_2_REPL и т.д., после чего запустите на выполнение тесты из файла advanced_sub_test.py. Добейтесь прохождения всех тестов.

Стоит ли пользоваться регулярными выражениями?

Регулярные выражения, как и любой другой инструмент, стоит использовать там, где они действительно уместны. Во многих случаях использование альтернативного подхода может существенно упростить процесс решения задачи, а также сделать текст программы более понятным. В качестве примера плохого регулярного выражения можно привести вот этот модуль для языка Perl, который проверяет корректность введённого адреса электронной почты. Мало того, что это выражение огромно, так ещё и потребуется не один час, чтоб разобраться, как именно оно устроено.

В остальных случаях, особенно когда регулярное выражение получается понятным и лаконичным, его использование оказывается более предпочтительным. Однако не стоит забывать о том, что зачастую на написание корректно работающего регулярного выражения может потребоваться больше времени, чем на решение задачи альтернативным способом.