Регулярные выражения
Сегодняшняя лекция самая интересная, как мне кажется: сегодняшний разговор пойдет про регулярные выражения.
Вспоминаем нечто похожее на регулярные выражения, точнее, нечто выполняющее функции сопоставления шаблонов. В прошлый раз мы говорили о генерации имен файлов и шаблонах. Язык шаблонов очень простой, он содержал звездочку в качестве подстановки любой строки, вопросительного знака, который заменяет один символ, соответственно два символа - ?? - заменяют два знака и так далее, диапазона, который заменяет собой, скажем так, все файлы, начинающиеся на буквы из диапазона. (кстати, в русской локали большие и маленькие буквы не отличаются при сопоставлении шаблонов) отрицаний диапазонов, то есть всех слов, которые не содержат соответствующие буквы и, кажется, все. Вообще говоря, язык шаблонов не полноценный. Он был рассчитан на применение к спискам файлов. Шаблоны еще используются при программировании в шелле при программировании оператора выбора case of, но там они тоже не очень часто нужны.
Зная, что большая часть информации, которая отвечает за настройку системы и рабочего стола - текстовая, нам бы хотелось, конечно, иметь более гибкий инструмент, который бы соответствовал тому же принципу: задаем шаблон, инструмент получает на вход набор текст данных, из него он выбирает соответствующие шаблону строки. То есть было бы неплохо придумать какой-то инструмент, который бы позволял это реализовывать. Эту теорию придумали очень давно, например, можно вспомнить Ноама Хомского и его теорию формальных языков и грамматик. В его классификации есть наиболее узкий класс - автоматные или регулярные грамматики, который отличается простым алгоритмом сопоставления шаблонов, в отличии от такого же алгоритма контекстно-зависимой грамматики. Этот алгоритм обладает псевдополиномиальной сложностью - то есть, если мы не будем злоупотреблять точками ветвления, то распознавание произойдет быстро. Причем язык, порождаемый регулярными грамматиками более мощный, чем язык шаблонов.
Начну с примеров, а потом мы разберемся с подробностями.
Вы наверняка видели как я пользуюсь утилитой grep, которая выбирает из текстового потока шаблоны, например
$ cal $ cal | grep 23
- из строковой выдачи grep вынет строку, в которой содержится подстрока 23. На самом деле, здесь (вместо 23) может быть шаблон регулярного выражения.
Но пока приведем пару примеров инструментов которые пользуются регулярными выражениями.
grep можно рассматривать как фильтрацию текста на нахождение подстроки, но на самом деле этим занимается $ fgrep - ищет подстроку в строке.
grep ищет регулярные выражения.
Это первое, что я хотел показать
Второй пример: регулярные выражения, используемые для поиска с заменой, что гораздо более интересно и предлагает нам всяких волшебных штук по преобразованию структурированных текстов
Поиск с заменой реализован во многих текстовых редакторах, во всех языках программирования, но в самом беспардонном виде он реализован в потоковом текстовом редакторе sed, который мы учить не будем, потому что времени нет, выучим мы только одну команду.
Что же такое потоковый текстовый редактор sed? Работает он по тому же принципу, по которому работают все линуксовые фильтры: читает входной текст построчно, к каждой строчке применяет команды, которые преобразовывают входной текст, выводит результат на вывод. при этом таким образом получается преобразование текстов, написанное на специфическом языке преобразования текстов. В числе прочего там есть команда поиска с заменой:
$ cal | sed ’s/1/Q/’
/ - ограничители
К sed еще вернемся, когда я буду пояснять особенности работы сопоставления шаблонов в строке.
Вернемся к команде grep, поскольку она самая простая. Как не трудно заметить из сложения двух утверждений, что grep - это поиск регулярного выражения в текстовой выдаче и что сопоставление происходит с символом, любой символ - это регулярное выражение. Только некоторые символы имеют специальное назначение: спец символы.
Есть такой спец. символ точка - метасимвол, который соответствует любому символу вообще в выходном потоке. Как можно видеть из примера:
$ grep . <<@@@ (это называется hear document) > sdasd > sdsfsfesf > >awdad >@@@ - последовательность конца файла sdasd sdsfsfesf awdad
grep . покажет строки, где есть хоть один символ (любой).
Более тонкая настройка состоит в том, что мы зададим диапазон, например:
$ grep ‘[a-f]\ <<< erwqwert erwqwert
Либо отрицание дапазона:
grep ‘[^a-f]\ <<< erwqwerte erwqwerte
Это не отличается от генерации имен файлов, если бы не конструкция, которая называется повторитель, и когда мы работаем с повторителями мощность регулярного языка увеличивается. Повторитель - знак звездочки, которая ставится после регулярного выражения, указывает, что символ может быть повторен один или более раз.
grep ‘w[a-f]*d’ <<< dwdfeefdegd
Правило, используемое при раскрытии повторителей, очень простое: самый левый, самый длинный. В получившейся подстановке мы выбираем самую удобную подстановку, которая находится левее всех.
Мы начали с буквы w - нашли ее, потом должны быть любые подстановки [a-f] один или больше раз, а потом должна идти буква d. Повторитель - механизм который, делает регулярную грамматику достаточно мощным средством порождения в различных языках.
Нам не хватает умения прилаживать повторитель к неатомарным регулярным выражениям. Например, мы хотим, чтобы наше слово состояло из букв ab или cd один или больше раз:
$ egrep --color ‘([ab][cd])*’ <<< asdasabcadfacbas
-она нашла две последовательности
asdasabcadfacbas
egrep пользуется немного другим синтаксисом: это расширенное регулярное выражение.
Составим сложное регулярное выражение. Допустим:
$ egrep --color ‘T([ab][cd])*P’ <<< asdasaTbcadPfacbas asdasaTbcadPfacbas egrep --color ‘T([ab][cd])*P’ <<< asdasaTPfacbas asdasaTРfacbas
Это операция группировки. Используется также при поиске и замене. Вспомним наш сед:
$ sed -E ’s/T([ab][cd])*P/@@@/‘ <<< asdasdTPfacbas asdasd@@@facbas $ sed -E ’s/T([ab][cd])*P/@@@/‘ <<< asdasdTacbdadbcPfacbas asdasd@@@facbas $ sed -E ’s/T([ab][cd])*P/@\1@/‘ <<< asdasdTacbdadbcPfacbas asdasd@bc@facbas
- первые скобочки подставились между двумя собачками, а Т и П пропали.
Регулярные выражения проще писать, чем читать:
$ sed -E ’s/a(.)b(.)c/-‘2-\1-/‘ <<< a5b6c -6-5-
Еще раз о нумерации скобочек: номер, который мы указываем - номер скобочек по порядку следования. Содержимое группы - то, что туда заматчивалось в последний раз.
Регулярные выражения используются в обработке текстов.
$ grep ‘[a-f]*’ << esdwdfeefdegd
Были найдены все последовательности символов, содержащие [a-f]
Если подставим крышку - поиск в начале строки:
$ grep ‘^[a-f]*[st]’ << esdwdfeefdegd esdwdfeefdegd
- поиск только в начале строки
Знак $ - поиск ТОЛЬКО в конце строки
$ grep ‘^[a-f]*[st]$’ << esdwdfeefdegdtt esdwdfeefdegdtt
В отличии от других метасимволов регулярных выражений - диапазонов, точек - символ $ и ^ не сопоставляются никакому символу. Просто сопоставляют выражение в начале или в конце строки. Вот это - любой символ, точка, диапазон, повторитель, конкатенация выражений, группировка, позиционирование, дают мощный механизм сопоставления шаблонов.
Если мы скажем что-то вроде "Поищите во входном потоке данных следующие файлы "о", любой символ, "о", любое кол-во точек от нуля до бесконечности":
$ ls -1 | grep ‘0.0\.*’ ooo ooo1.py ooo2.py ooo.py
A теперь "o", символ, "о" и точка:
$ ls -1 | grep ‘0.0\.’ ooo.py
Мы можем либо лишить символ метасущности и превратить его в обычный, как в этом случае, либо наоборот по договоренности считать, что скобка "(" является символом.
$ sed \a/a\(.\)b/(.\)c/-\2-\1-/\ <<<< a5b6c -6-5-
Я предпочитаю использовать расширенные регулярные выражения, где есть всякие крутые штуки, в частности, можно сделать повторитель, который не матчится на пустую строку. Потому что повторитель, который матчится на пустую строку - это зло, это не удобно: он матчится везде, любая строка матчится на что-нибудь звездочка
$ egrep ‘(sdfs sdf fds)*’ <<< sdsadasdasdf sdsadasdasdf
- матчится везде!!
Есть повторитель, который не матчится на любую строку: в расширенных регулярных выражениях есть символ +
$ egrep ‘(ab)+’ <<< asdfabsdfasdfas asdfabsdfasdfas
Очень удобный повторитель ? - матчится 0 или 1 раз.
Как работает сед, если подстановка не произошла? Подстановка не происходит. Довольно очевидно, я считаю. Есть 2 синтаксиса стандартизованных регулярных выражений, есть куча остальных нестандартизованных, и эти два - базовый и расширенный.
Базовый: в нем требуется рядом со скобочками писать \
Расширенный: там есть +, ?, альтернатива, что очень удобно альтернатива - простая штука
$ grep ‘(ab|cd)’ <<< asdfabsdfbaasdf asdfabsdfbaasdf $ grep ‘(ab|cd)’ <<< asdfcdsdfbaasdf asdfcdsdfbaasdf
оба они матчатся, что очень удобно
$ grep ‘(ab|cd)+’ <<< asdfcdababcdasdfas asdfcdababcdasdfas
Еще есть повторитель, где вы явно указываете количество:
$ grep ‘(ab|cd){2,5}’ <<< asdfcdabcdcdcdabasdfas
asdfcdabcdcdcdabasdfas - ab уже не влезло
Вы можете указывать четкое количество повторителей, например, {4}, или оставлять один или другой конец открытым {,4} - от 0 до 4, ну и в обратную сторону.
И последняя важная штука, про которую я не буду долго говорить - классы эквивалентости - помогает, когда вы работаете с реальными текстами, например, хотите взять из текста только цифры:
$ egrep ‘[[‘’digit’’]]+’ << ‘asdf234’ asdf234
["digit"] выделит только цифры, [‘’alnum’’] - все символы - буквы и цифры
Можете начать сомневаться, но расширенные регулярные выражения порождают тот же класс языков, что и обычные. Мы можем несколько скрепя сердцем смоделировать то, что мы делали с помощью расширенных, с помощью обычных регулярных выражений, Расширенные регулярные выражения обрабатываются так же быстро и хорошо, как и обычные, но предоставляют некоторое количество плюшек, которыми удобно пользоваться. Например скобочки: они тут менее мозговыносящие.
Немножко отсылка к теории: как работает алгоритм матчинга - самый левый самый длинный. Проиллюстрирую на довольно сложном примере.
(cd|ab)+$ - регулярное выражение
sabcadababcd - строка
так как выражение расширенное, то придется подключать воображение.
пытаемся заматчить сначала (-0
результат:
ababcd
Бектрекинг: если в данном предположении "самый левый, самый длинный" заматчить регулярное выражение - немножко ужать регулярное выражение и его попробовать. Если не получилось - переключиться на предыдущий матчинг и идем дальше. Этот способ разбора называется "сопоставление с возвратом", слегка неудобен тем, что если встречаются конструкции рода
(a(b(c(d)*)*)*)*
то не смотря на кажущуюся простоту, ее придется довольно долго проверять. Вложенные пусто-бесконечные повторители могут привести к долгой работе алгоритма. Слава богу, только эти, потому используйте где угодно +.
В общем, не нужно делать вложенных повторителей, особенно звездочек. Но! Это только в том случае, если мы используем сопостановку с бектрекингом - с возвратом. Поиск с возвратом хорош тогда, когда нам нужно воспроизводить не только поиск, но и последующую замену: чтобы мы могли разметить куски строки - какое регулярное выражение и где нам заматчивать.
Подойдем с другой стороны: будем брать строку посимвольно и попытаемся понять, каким из выражений она соответствует, при этом на каждом шаге будут добавляться варианты разбора, а некоторые варианты разбора будут пропадать
*A*AB* ? AAB
1. А:
1. А - «А*»
2. А - «А*А», т.к. «A*», A - «A»
два вар-та разобрать А: а-а*, либо а-пустота
2. АА:
1. АА - «А*»
2. АА != «А*АВ»: А != «В»
3. АА - «А*А»: первый шаг: А - «А*», второй шаг: А - А (первая A - A*, вторая A - обычная A)
3. ААВ:
1. ААВ != «А*А»: В != «А»
2. !=
3. ААВ сопоставимо с «А*АВ» , чтд.Этот разбор, в отличии от разбора с бектрекингом, бектрекинга не имеет, зато может вести несколько параллельных анализов и требует больше памяти. Главное, в отличии от разбора с бектрекингом, он известно когда закончится, поскольку он сводится к детерминированному конечному автомату.
Проблема состоит в том, что если у вас только поиск, то эта штука работает хорошо. Если поиск с заменой - не во всех случаях можно правильно отметить группы, на которые будем ссылаться. И это переводит нас к теме а какие регулярные выражения существуют кроме описанных?!.
Помимо грепа и седа есть утилита tr - это маленький сед для бедных: заменить все символы или удалить все символы.
$ cal | tr -d 0 - удалил все нули
Текcтовый редактор vim, про который мы не будем говорить, с возможностью поиска с заменой регулярного выражения.
$ vim o
там же можно написать вот так:
/\<o - файлы с буквой о в начале слова \< - начало слова
В разных языках программирования могут использоваться разные диалекты регулярных выражений. В линуксе есть движок gnu regexp.
Самое главное, что я хотел сказать: в толстых языка программирования типа перла, питона, джавасрипта, используются регулярные выражения, которые таковыми не являются. Они выводят нас за пределы класса регулярных грамматик.
Покажу документацию к питону.
Что мы не можем заматчить регулярным выражением? Нельзя поискать что-то в тексте, а потом сказать "Вот этого три таких же штуки пожалста": в грепе написать, грубо говоря, сначала объединить что-то в группу, а потом там же поискать.
$ cal | egrep ‘\(.)2.*\1\
Произвольный символ, двойка, какие-то символы, потом такое же еще раз - это уже контекстно свободные выражения, выводит нас за рамки регулярных выражений.
Наиболее популярный движок - перловый движок PCRE, который используется довольно часто.
Бекреференс - выход за пределы регулярных выражений, еще один выход - нематчащие шаблоны: искать строчку, которая находится перед строкой ААА, а ААА отправить в буфер - это называется look ahead.
(?=…)
- производит поиск строки
Isaac (?=Asimov) -> Isaac
но дальше поиск продолжится со слова Asimov.
Нежадный повторитель (самая страшная вещь) - выдает самый короткий варинт из возможных. Например, *? -выдаст нулевой вариант, если он возможен.
Последняя вещь. Есть классический труд - Mastering regular expressions, Friedl, также так называемый owl book. Там есть пример регулярного выражения, которое с виду выглядит очень просто, но зависает навсегда. В первом издании этой книжки было регулярное выражение для перла, которое матчит почтовый адрес, и оно было на 16 страниц.
Домашнее задание к сегодняшней лекции: если вам интересно, прочесть Mastering regular expressions, потому что, в принципе, эту книжку найти очень легко. И я нашел такой довольно легендарный сборник задач на регулярные выражения, только не выполняйте задание номер 7, это как раз заматчить почтовый адрес - то же самое, что у Фридла занимает 16 страниц в книжке.
Тогда мы это дело заканчиваем и возвращаемся к намеченному ранее плану, в общем, нам есть еще о чем поговорить. Всем спасибо!