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

Материалы

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

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

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

Утилиты

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

У Фридла чётко разделяются движки, которые только ищут и которые ищут и заменяют. У обычного алг. сопост. и послед. отката, вместо такого алг., исп. базирующ. на самом регэкспе, можно исп. алг., который пытается впихнуть строку в регэксп, и эти алгоритмы быстрее, чем классич., который требуется для запоминания частей. Это нам понадобится, если эти части потреб. нам для замены. Поэтому можно ождиать, что 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: ...

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

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

 sed 'a\
      text'

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

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

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

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

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

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

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

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

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

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

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

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

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

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

awk

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

awk --- Aho, Weinberger, Kernigan.

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

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

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

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

Совсем немного ... . Представим себе такое рег. выр.:  (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)

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

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


CategoryLectures CategoryCmc CategoryUneex

LecturesCMC/LinuxShell2008/10 (last edited 2008-07-24 22:25:19 by eSyr)