Regexp и Python: извлечение токенов из текста

  • Tutorial
imageРазбор логов и конфигурационных файлов — задача часто возникающая и многократно описанная. В этой статье я расскажу как на языке python реализовать ее классическое решение: с помощью регулярных выражений и именованных групп. По возможности постараюсь рассказать причины, по которым применяется то или иное решение, а также обрисовать подводные камни и методы их обхода.


Зачем разбирать текст и кто такие токены


В текстовых файлах, интересных нашим с Вами программам, обычно находится больше одной единицы информации. Чтобы программа могла отделить одну часть информации от другой, мы устанавливаем форматы файлов — то есть договоренность о том, как внутри файла записан текст. Самый простой формат — каждая единица информации находится на отдельной строке. Такой файл почти не требует дополнительной обработки — достаточно считать его средствами используемого языка программирования и разбить на строки. Большинство языков позволяют разбить файл на строки одной-двумя командами. К сожалению, большинство файлов, которые необходимо обработать, имеют чуть более сложный формат. Например, классический файл настроек содержит строчки вида имя=значение. В общем случае такой формат тоже достаточно легко разобрать, считав файл построчно и найдя в каждой строке '='. То что слева от него будет именем поля, а то что справа — значением. Эта логика будет работать, пока нам не понадобится разобрать файл с многостроковыми значениями полей и значениями, который содержат символ "=". Попытки обработать такой файл быстро приводят к появлению в коде многочисленных проверок, циклов и прочих сложностей. Поэтому для текстовых файлов, которые по структуре сложнее, чем список строк, давно и успешно применяется метод разбиения на токены с помощью регулярных выражений. Под словом «токен» (token) обычно понимают небольшую часть текста, находящуюся в определенном месте этого текста и имеющую определенное значение. Например, в следующем фрагменте конфигурационного файла:

можно выделить три токена: «name» как имя поля, "=" как разделитель и «Вася» как значение поля. Строго говоря, то что я в этой статье называю токенами больше подходит под определение лэксем (lexeme). Разница между ними в том, что лексема — это фрагмент текста определенного формата без учета его положения относительно других фрагментов текста. Сложные парсеры, например те которые применяются в компиляторах, в начале разбивают текста на лексемы а затем обрабатывают список лексем с помощью большого и ветвистого конечного автомата, который уже из лексем выделяет токены.
К счастью, в питоне очень хорошая библиотека для работы с регулярными выражениями, которая позволяет решать большинство задач обработки текста в один проход, без промежуточного поиска лексем и последующего преобразования их в токены.

Кто такие регулярные выражения


Регулярные выражения это такое, такое… Если совсем кратко, то это такой язык программирования, который создан для поиска текста. Очень-очень простой язык программирования. Условия а нем практически не применяются, циклов и функций нет, есть только одно выражение которое описывает какой текст мы хотим найти. Зато это единственные выражение может быть ну очень длинным :). Для успешного применения регулярных выражений вообще и на питоне в частности нужно знать несколько вещей. Во-первых, каждая уважающая себя библиотека для работы с регулярными выражениями использует свой собственный синтаксис этих самых регулярных выражений. В целом синстаксис похож, но детали и дополнительные возможности могут различаться очень сильно — поэтому перед использованием регулярных выражений в питоне необходимо ознакомиться с синтаксисом в официальной документации.
Во-вторых, регулярные выражения не разделяют синтаксис самого языка и пользовательские данные. То есть если мы хотим найти слово «вася», то регулярное выражение для его поиска так и будет выглядеть — «вася». В этой строке непосредственно язык программирования не присутствует, присутствует только заданная нами строка, которую надо искать. А вот если мы хотим найти слово «вася», после которого идет запятая или точка с запятой, то регулярное выражение обрастет нужными и важными подробностями: «вася,|вася;». Как мы видим, здесь добавилась конструкция языка «логическое или», которое представлено вертикальной чертой. При этом заданные нами строки никак не отделены от синтаксиса языка. Это приводит к важному и неприятному последствию — если мы хотим в строке для поиска задать символ, который присутствует в синтаксисе языка, то нам нужно перед ним написать "\". Так что регулярное выражение, которое ищет слово «вася» после которого идет точка или знак вопроса будет выглядить вот так: «вася\.|вася\?». И точка, и знак вопроса используются в синтаксисе языка регулярных выражений :(.
В-третьих, регулярные выражения по умолчанию жадные. То есть, если специально этого не указывать, то будет найдена строка максимальной длины, удовлетворяющая регулярному выражению. Например, если мы хотим найти в тексте строки вида «имя=значение» и напишем регулярное выражние: ".+=.+", то для текста «a=b» оно сработает правильно, вернув «a=b». А вот для текста «a=b, c=d» оно вернет «a=b, c=d» — тоесть текст целиком. Об этом свойстве регулярных выражений нужно помнить всегда и писать их таким образом, чтобы у библиотеки не возникла соблазна вернуть половину «войны и мира» как результат поиска. Например, предыдущее регулярное выражение достаточно немного модифицировать: "[^=]+=[^=]+" — такая версия будет учитывать, что в тексте перед и после символа "=" не должно быть самого символа "=".

Ищем токен в тексте


Библиотека регулярных выражений в питоне называется «re». Основная функция по сути одна — это search(). Передав первым аргументом регулярное выражение, вторым — текст в котором искать, — на выходе мы получим результат поиска. Обратите внимание — для строки с регулярным выражением лучше использовать префикс «r», чтобы символы "\" не преобразовывались в строковые escape-последовательности. Пример поиска:

import re
match = re.search( ur"Вася\.|Вася\?", u"Вася?" )
print match.group().encode( "cp1251" )

Как видно из примера, метод search() возвращает объект типа 'результат поиска', который имеет несколько методов и полей с помощью которых можно получить найденный текст, его позицию в исходном выражении и прочие нужные и полезные свойства. Рассмотрим более жизненный пример — классический конфигурационный файл, состоящий из имен секций в фигурных скобках, имен полей и их значений. Регулярное выражение для поиска имен секций будет выглядеть следующим образом:

import re
txt = '''
{number section}
num=1
{text section}
txt="2"
'
''
match = re.search( ur"{[^}]+}", txt )
print match.group()
 

Результатом выполнения этого кода будет строка "{number section}" — имя секции успешно найдено.

Ищем все экземпляры токена в тексте


Как видно из предыдущего примера, просто вызов re.search() найдет только первый токен в тексте. Для нахождения всех экземпляров токена библиотека re предлагает несколько способов. Самый, на мой взгляд, корректный — это вызов метода finditer(), который возвращает список объектов типа 'результат поиска'. Получая эти загадочные объекты вместо обычных строк (которые может вернуть, к примеру, метод findall), мы получаем возможность не только ознакомиться с фактом что текст найден, но и узнать где именно он найден — для этого у объекта типа 'результат поиска' есть специально обученный метод span(), возвращающий точное положение найденного фрагмента в исходном тексте. Измененный код для нахождения всех экземпляров токена с использованием метода finditer() будет выглядеть следующим образом:

result = re.finditer( ur"{[^}\n]+}", txt )
for match in result :
  print match.group()

Ищем в тексте разные токены


К сожалению, поиск одного токена — дело, безусловно, интересное — но практически мало полезное. Обычно в тексте, даже таком простом как конфигурационный файл, есть много интересующих нас токенов. В примере с конфигурационным файлом это будет как минимум имена секций, имена полей и значения полей. Для того, чтобы искать несколько разных токенов в языке регулярных выражений используются группы. Группы — это фрагменты регулярного выражения, заключенные в круглые скобки — соответствующие этим фрагментам части текста будут возвращены как отдельные результаты. Таким образом регулярное выражение, способное искать секции, поля и значения, будет выглядеть следующим образом:

result = re.finditer( ur"({[^}\n]+})|(?:([^=\n]+)=([^\n]+))", txt )
for match in result :
  print match.groups()
 

Обратите внимание, что этот код значительно от отличается от предыдущего. Во-первых, в регулярном выражении выделены три группы: "({[^}\n]+})" соответствует заголовку в фигурных скобках,
"([^=\n]+)" перед знаком '=' соответствует имени поля и "([^\n]+)" после знака '=' соответствует значению поля. При этом также используется странная группа "(?:)", которая объединяет группы имен и значений полей. Это специальная группа для использования с логическим оператором '|' — она позволяет объединять несколько групп одним оператором '|' без побочных эффектов. Во-вторых, для распечатки результатов использован метод groups() вместо метода group(). Это не спроста — библиотека регулярных выражений в питоне имеет свое собственное представление о том, что такое «результат поиска». Выражается эта самостийность в том, что регулярное выражение из двух групп "([^=\n]+)=([^=\n]+)", примененное к тесту «a=b» вернет ОДИН объект типа «результат», который состоит из нескольких ГРУПП.

Определяем, что именно мы нашли


Если запустить предыдущий пример, то на экран выведется примерно следующий результат:

('{number section}', None, None)
(None, 'num', '1')
('{text section}', None, None)
(None, 'txt', '«2»')

Как видим, для каждого результата метод groups() возвращает некий волшебный список из трех элементов, каждый из которых может быть либо None (пусто) либо найденным текстом. Если вдумчиво покурить документацию, то можно разобраться что библиотека нашла в нашем выражении три группы и теперь для каждого результата выводит какие именно группы в нем присутствуют. Мы видим, что первая группа соответствует имени секции, вторая имени поля и третья значению поля. Таким образом первый результат, "{number section}", это имя секции. Второй результат, «num=1» — это имя поля и значение поля, ну и так далее. Как видим, довольно запутано и неудобно — в общем случае трудно определить ЧТО ИМЕННО мы нашли.
Для ответа на этот важный вопрос группы можно именовать. Для этого в языке регулярных выражений предусмотрен специальный синтаксис: "(?P<имя_группы>выражение)". Если немного изменить наш код и дать трем группам имена, то все будет гораздо удобнее:

import re
txt = '''
{number section}
num=1
{text section}
txt="2"
'
''
object = re.compile( ur"(?P<section>{[^}\n]+})|(?:(?P<name>[^=\n]+)=(?P<value>[^\n]+))"re.M | re.S | re.U )
result = object.finditer( txt )
group_name_by_index = dict( [ (v, k) for k, v in object.groupindex.items() ] )
print group_name_by_index
for match in result :
  for group_index, group in enumerate( match.groups() ) :
    if group :
      print "text: %s" % group
      print "group: %s" % group_name_by_index[ group_index + 1 ]
      print "position: %d, %d" % match.span( group_index + 1 )

Обратите внимание на ряд косметических изменений. Перед поиском используется метод re.compile(), который возвращает так называемое «скомпилированное регулярное выражение». Кроме скорости работы и удобства у него есть одно замечательное свойство — если вызвать его метод groupindex(), то мы получим словарь, содержащий имена всех найденных групп и из индексы. К сожалению, словарь почему-то инвертирован — кючем в нем является не индекс, а имя группы. страшное выражение с dict() исправляет это досадное недоразумение и словарь group_name_by_index можно использовать для получения имени группы по ее номеру. Также при компиляции используются флаги re.M (корректный поиск начала строки "^" и конца строки "$" в многостроковом тексте), re.S ("." находит совсем все, включая \n) и .U (корректный поиск в unicode тексте). В результате разбор найденного занимает два цикла — сначала мы итерируемся по результатам поиска, а затем для каждого результата по содержащимся в нем группам. Результатом является точный и полный список токенов, с указанием их типа и позиции в тексте. Этот список можно использовать для обработки текста, подсветки синтаксиса, нахождения ошибок — в общем штука нужная и полезная.

Заключение


Продемонстрированный способ нахождения лексем в тексте не является самым лучшим или самым правильным — даже в рамках языка питон и его стандартной библиотеки регулярных выражений существует как минимум десяток альтернативных способов, ничем не уступающих этому. Но я надеюсь, что приведенные примеры и объяснения помогут кому-нибудь при необходимости быстро войти в курс дела, сэкономив время на гугление и выяснения почему оно работает не совсем так, как хотелось бы. Всем удачи, жду комментариев.

Метки:
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 43
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Порты есть. Но, во-первых, их надо отдельно ставить. А во-вторых, использование BNF-грамматики это ни разу не пять строчек кода, что во многих случаях является излишним усложнением проекта.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Как это не пять? У меня в последнем примере аккурат пять :). Просто для удобочитаемости развернуто по вертикали.

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

          Способ, на мой взгляд, занимает нишу аккурат между ConfigParser и PLY :). Не силвер баллет, конечно, но на мой взгляд для многих задач самое то. У меня ЭТИМ в текстовом редакторе ряд леворезьбовых внутренних синтаксисов подсвечивается — оч удобно.
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Да, пожалуй разбор конфига в качестве примера — не очень удачное решение :). Но любой другой пример был бы, мягко говоря, объемнее. И так в статье слишком много букв получилось.
              • 0
                Это смотря каких логов. Есть некоторые логи, типа сквидового access.log, в которых все чётко по полям раскидано и простой split вполне справляется.
          • +1
            Зато PLY преобразует заданную грамматику в конченый автомат и позволяет его даже скомпилировать, хранить и загружать уже в виде конечного автомата. Один результирущий автомат содержит все регулярные выражения соотвествующие указанным в его определении токенам, в результате он оптимальнее чем пачка регулярок.

            Вощем велосипед вы напиали, товарищ.

            Уверен, что раньше вы программировали на PHP и поэтому не привыкли к философии Python «battaries-included».
          • 0
            Ага, я как раз этот PLY использую. И плююсь. Какой-то не python way у этой библиотеки, но ничего лучше нет.
            • 0
              Можно попытаться выдернуть кусочек из PyPy, лексер например.
              • 0
                Поздно уже :) Я уже много написал.
              • 0
                У этой библиотеки flex way. Поскольку она являтся портом flex на Python.
                • 0
                  Вас, пайтонистов не понять. Вот посмотрите на siasia habrahabr.ru/blogs/python/60369/#comment_1695404 Кому верить?
                  • 0
                    Мне. О разных вещах коллеги говорят. PLY и pyparsing — это серьезные библиотеки для парсинга всего. Но они требуют времени на изучение, их надо ставить, кода писать не мало. Показанный мной способ — это промежуточное между split() и указанными библиотеками. Для своего ряда задач :).
                    • 0
                      Верю :)
                      • 0
                        Я так, подзадорить :) ведь полярно разные мнения, грех не обратить внимание высказавшихся :)
                        • +1
                          Одну и ту же задачу как правило можно решить десятком разных способов :). Как показывает практика, разные библиотеки и подходы заточены под разные задачи — скорость, универсальность, количество кода, встроенность в язык и так далее. Чем больше разных способов человек знает тем лучше он, ИМХО, может выбрать инструмент для решения конкретной задачи. Как правило, решения «лучше» не существует просто потому, что многие характеристики взаимоисключающие — split() требует минимума кода, но не парсит ничего сложнее ini файлов. На PLY можно написать синтаксический анализатор PHP, но это обойдется в изучение технологии и сотни строк кода :)
                          • 0
                            Да я поверил уже на пару комментариев выше :) говорю же :)
                            Спасибо :)
                      • 0
                        Зря вы так. Ничего сложного в PLY нет. За пару вечеров она осваивается до уровня достаточного для написания простеньких лексических анализаторов размером с описанный в статье. По-моему сложно сть flex, ply и прочих генераторов лексических анализаторов приувеличена, а может сказывается мой один семестр университета по курсу «Теория компиляторов». :)
                      • 0
                        Библиотека хорошая. Просто в Python она встроена, как чужеродное тело.
                  • +1
                    • 0
                      Да, штука хорошая. Но те же минусы что и у PLY — нужно ставить (это я не к тому что сложно, а к тому что затрудняет разворачивание на машины конечных пользователей), нужно писать больше кода, нужно учить грамматику.
                      • 0
                        Это не минусы, это придирки: )

                        Регулярки это всё таки бомбометание по площадям, а уж чтобы конкретно их изучить надо в разы больше времени — ничего простого в них нет, а есть в них куча подводных камней о которых надо знать.
                  • +3
                    >> Если совсем кратко, то это такой язык программирования, который создан для поиска текста. Очень-очень простой язык программирования. Условий, циклов и функций у него нет…

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

                    Вот что говорит документация про условие поиска:
                    (?(id/name)yes-pattern|no-pattern)
                    Will try to match with yes-pattern if the group with given id or name exists, and with no-pattern if it doesn’t. no-pattern is optional and can be omitted.

                    С чисто академической целью ваш последний паттерн можно было бы привратить во что-то подобное:
                    r'({)?(?(1)(?P<section>[^}\n]+])}|(?P<name>[^\n=]+)=(?P<value>[^\n=+]))'

                    Конечно, в такой реализации (если сначала найдена фигурная скобка искать section, в противном случае пару name=value) от него толку мало, но вот если понадобится обработать специфическим образом «number section», например, такая конструкция может помочь. Жаль только, что для условия обязательно нужно его захватывать и потом ссылаться по id или имени. В других реализациях можно писать что угодно, вплоть до заглядываний.
                    • +1
                      Сильно. Спасибо. Не знал :). Статью подправил.
                      • 0
                        А вы почитайте Python re: docs.python.org/library/re.html от начала и до конца.
                        • 0
                          Так одно дело прочитать, а другое запомнить. Если я буду детально помнить все доки по всем технологиям которые я когда-либо встречал… Вообщем, не могу похвастаться настолько хорошей памятью :).
                          • 0
                            Все и не надо. Но регулярки надо знать от и до.
                            • 0
                              Для .net, java, python, lua, perl, php, ruby, boost, qt, gtk? Для большинства реализаций есть много мелких различий :).
                              • 0
                                А вы на всём этом программируете? Я программирую на Perl, PHP, Python и Javascript. Для этих языков регулярки я знаю.
                                • 0
                                  Нет, в основном я на С++ :(. А остальное все эпизодически ровным слоем.
                            • 0
                              А помнить не надо, просто если не прочитать, можно не знать о сущствовании нужной функции и пытаться самомстоятельно изобретать велосипеды.
                              • +1
                                Это да. Я стараюсь по мере сил, но иногда в списке из сотни одинаковых пунктов пара ускальзывает от внимания. Но я над этим работаю.
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • 0
                            Это философский вопрос — что называть циклом в языке программирования :). «text» * 10 в питоне — это цикл или не цикл? :).
                            • НЛО прилетело и опубликовало эту надпись здесь
                            • 0
                              Строго говоря вы скорее всего правы. Хотя можно конечно ещё поговорить относительно того, насколько вообще пременимо слово «цикл» к конечным автоматам.

                              Ну а в данном случае под циклом я подразумевал именно человеко-очевидный цикл. Рекурсия в регулярках под него лучше всего подходит, как мне кажется.

                              Впрочем, верно написано выше — вопрос филосовский. )
                              • НЛО прилетело и опубликовало эту надпись здесь
                          • 0
                            А вы на больших логах, мегабайт так по 60, эти способы проверяли?
                            • 0
                              Yep. Замечательно парсит. Там ~O(n*m) где m не очень велико.
                            • 0
                              какой же это язык программирования, вы что?!!!
                              ну-ка напишите машину тьюринга.

                              это способ задания шаблонов.

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