Регулярные выражения: продолжение

Материалы

• Диктофонная запись: http://esyr.org/lections/audio/uneex_2008_summer/uneex_08_04_23.ogg

Мы продолжаем про рег. выр.

Инструмент регэкспов весьма мощный. Если вы собираетесь работать с линуксом не на уровне бытового прибора, то придётся им пользоваться достаточно часто. Например, редакторы vi-inspired имеют встроенную работы с регулярными выражениями, котрые позволяют творить такие чудеса, которые нельзя творить больше ничем. Именно такое знание рег. выр. открывает одно из основных достоинств вима. Если ваша задача --- не редактирование, а автоматическое преобр. текста, преобр. структ. текстов на базе рег. выр.

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

Утилиты

Всякая утилита, которая работает с текстом, и в которой может осущ. поиск/замена, поиск там обычно идёт по регэкспу

• vim.

• less. Если у вас основной объект, с которым придётся работать --- текстовый файл, то придётся его просматривать. Можно использовать cat, но это крайне неудобно. Удобно было бы просматривать текст постранично. Раньше была утилита more, которая выводила его постранично. Естественно, этого было недостаточно, поэтому ребята из GNU написали утилиту, которую естественно назвали less. Это почти текстовый редактор, едлинственного, чего не умеет --- редактировать. В частности, там есть поиск (команда такая же, как и vim ) --- /<regexp>. При этом будет перейдено на первую строку, которая заматчится. Для поиска назад --- ?<regexp>. То же в mutt и в чёртовой прорве утилит по работе с текстом.

• Если задача не просто поискать строчки в файле, а ещё и их отфильтровать, тто для этого существует программа grep. Это программа поиска рег. выр. в тексте, которая по умолчанию имеет первым параметром рег. выр., и вторым необяз. параметром --- файл (по умолчанию чтение из консоли). Крайне удобная штука для ограничения контекста просмотра. По умолчанию утилита grep работает с базовыми рег. выр. Для того, чтобы работать с расшир., есть ключик -e или вызвать egrep.

У Фридла чётко разделяются движки, которые только ищут и которые ищут и заменяют. У обычного алг. сопост. и послед. отката, вместо такого алг., исп. базирующ. на самом регэкспе, можно исп. алг., который пытается впихнуть строку в регэксп, и эти алгоритмы быстрее, чем классич., который требуется для запоминания частей. Это нам понадобится, если эти части потреб. нам для замены. Поэтому можно ождиать, что egrep будет работать на глупых выраж. достаточно хорошо, а от седа/вима такого мы не можем ожидать.

Алгоритм бэктрекинга

Этот алгоритм имеет отношение к правилу самый левый самый длинный и факт. явл. его реализацией.

Пример:

 Рег. выр: (xy)+z
 Строка: xyxz1xyxyzabxyxyxyz

Берём первый атом (xy)+, и ищем самую левую самую длинную подстроку. Этот шаблон сложный, но история там та же самая.

 xyxz1xyxyzabxyxyxyz matching (xy)+
 ..                  match
 
 xyxz1xyxyzabxyxyxyz matching z
   do not match
 
 yxz1xyxyzabxyxyxyz matching (xy)+
 do not match
 
 xz1xyxyzabxyxyxyz matching (xy)+
 do not match
 
 1xyxyzabxyxyxyz matching (xy)+
 do not match
 
 xyxyzabxyxyxyz matching (xy)+
 ....                    match
 
 xyxyzabxyxyxyz matching z
     .                   match

Это простой пример, в котором мы не увидели отката, был только прямой поиск. Давайте его слегка усложним таким способом:

Пример:

 Рег. выр: (xy)+x
 Строка: axyxyxyb

 axyxyxyb matching (xy)+
  ......  match
  
 axyxyxyb matching x
        . do not match
  
 axyxyxyb matching (xy)+
  ....    backtracking
 
 axyxyxyb matching x
      .   do not match

Понтно, что в первый раз было быстрее.

Именно этот алгоритм обычно имп., поскольку гарантирует, что мы будем точно знать, какому куску рег. выр. соответствует какая часть строки

Вернёмся к утилитам

Утилиты (продолжение)

sed

Лектор не знает, как в ист. перспективе (говорят, что сначала был ед, а потом сед), но лектор начнёт с sed. Потоковый текстовый редактор (stream editor). То есть, программа-фильтр. При этом всякое упр. этой программой выполняется в виде ппередачи параметров. Изначально именно sed предполагался таким обработчиком файлов, и если не удавалось им решить задачу, то это значилло, что надо былописать программу.

Что делает sed: ...

Основные команды седа

Что можно делать со строчками?

• Их можно добавлять (a)

 sed 'a\
      text'

• Вставить перед --- i
• Удалить --- d
• Заменить (аналог tr) --- y
• В sed есть hold space, где могут храниться строчки, команды работы с ним:
  • h --- поместить в HS
  • H --- добавить в HS
  • g --- заменить строку содержимым HS
  • G --- добавить содержимое HS
  • x --- обменять содержимое HS и текущую строку
• Основная команда, ради которой sed используют --- s/regexp/replace_regexp/[g]. Замена делается в рамках текущей строки
  • N --- добавить очередную строку в pattern space

Пример исп.: sed 's/еж/ёж/g' file > newfile

Есть ключик -i, который делает inplace. Но это опасная операция, посколько операция чтения/записи неатомарная.

Условные операторы в седе

Что делает sed интересным инструментом --- смешной условный оператор

• t <label> --- делает переход на метку, если в последний раз произошла успешная замена

• b <label> --- оператор условного перехода

Контекстный адрес

Второе, что есть --- контекстный адрес. Что такое кон. адр. --- перед командой седа можно поставить один или два адреса, к которым эта команда применяется.

 <a> <command>
 <a1,a2> <command>

В рез-те команда применяется к строке или строкам. Почему или: есть два вида адресов:

• 0, 1, 2, ..., $
• /regexp/

Как копать отсюда до обеда:

• /сюда/,/обед/ s/курить/копать/g

Выполняется это для всех встречаний. То есть, если встречается слово "сюда", то становится matching states, встречается "обед" --- unmatching state.

Никто не мешает смешивать адреса.

Что касается конт. адреса 0 --- правило сразу входит в matching state.

Как сделать, чтобы выполнялось несколько команд над одной строкой --- { ... }

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

awk

sed не явл. алг. полным языком (sed, обрабатывающий скрипт на седе и скармливающий его седу, явл. алг. полным). А вот awk уже явл. алг. полным.

awk --- Aho, Weinberger, Kernigan.

Иерархия: sed → awk → gawk

Это уже более сложный язык, там не 10 команд.

Утилиты (продолжение)

• perl

Для задачи обработки текстов такого рода организация написания скриптов существенно упрощает сам код и понимание.

• ed. Интерактивный невизуальный редактор. Существует с незапамятных времён.
  • Есть команда g, которая применяет команду ко всем строкам. Есть команда p, которая выводит строки. Соответственно, g/re/p --- вывести все матчащиеся строки. А теперь прочитайте это.

Совсем немного ... . Представим себе такое рег. выр.:  (x+x+)+y Есть некая избыточность --- x+. Какую оно можетсыграть с нами шутку. Попробуем заматчить:  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy Заматчит, один раз откатит, заматчит. А как будет работать на этой строке:  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Хуже, чем n^2.

Карманы

Допустим, нам надо переставить два слова в тексте.  s/[a-z]+ [a-z]+/ Что дальше делать? Нужен механизм, который позволит запомнить заматченные полстроки и потом их использовать. Делается это очень просто: Каждая открывающая скобочка запоминается в соотв. карман:  s/([a-z]+) ([a-z]+)/\2 \1/g

PCRE (Perl Compatible Regular Expression)

Лектор будет говорить про них мало, ибо отн. к ним с некоторой неприязнью.

• Look-ahead. <regexp>(?=<lookahead>). При этом матчится только <regexp>.

• Negative look-ahead. <regexp>(?!<lookahead>).

• Look-behind. (?<=<lookbefore>)<regexp>

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

CategoryLectures CategoryCmc CategoryUneex