Материал из eSyr's wiki.

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

[править] Регэкспы

До этого упоминались вилдкарды, но они могут не всё, например, не могут отслеживать повторы или делать матчинг.

С точки зрения теории, шабон не описывает никакого класса языков. Между тем, возвращаясь к калссиф. Хомского, там не очень много --- автоматные, КС, КНС и любые. Из этого за реальное время работают только автоматы. Поскольку надо ещё учитывать, что соотв. класс регекспов придумывался лет 30 назад, то мы можем понять, что дальше, чем на регулярные грамматики, авторы и не замахивались.

[править] Регулярные выражения

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

Как и шаблони, регэкспы используются для поиска и для поиска с заменой. Соответственно, это и порождает два места для исп. регэкспов: процедура, которая фильтрует текст (банальный поиск по тексту, в манах или текстовых редакторах, или внутри сценариев), и поиск с заменой. Совершенно необязательно текстовые редакторы интерактивны. Неисключено, что текстовым редактором является некая программа, которая какую-то фильтрацию производдит. В случае регэкспа, можно довольно мощную фильтрацию проводить.

[править] Базовые регулярные выражения

Главным отличием того, что наз. регэкспами от шаблонов, является вот что: сами специальные символы ничего не значат, они являются модификатором. Например, в шаблонах звёздочка что-то значила --- любое количество символов, а в ренэкспах это специальный символ --- повторитель.

• a → a

Процедура поиска по регэкспу --- поиск подстроки в строке.

• . → ∀1 — любой один символ, как вопр. знак в шаблонах. Соответственно, точка является спецсимволом. Если, например, ищется имя файла с точкой, то точку надо закавычить.
• \ξ → ξ
• [a-d0-9_.] → f ∈ [...]. В квадратных скобках опр. диапазоны, если нужно найти минус, то надо поставить его либо первым, либо последним.

Это что касается рег. выр., сопост. с одиним символом. Но главное, что позволяет превратить это в распознователь рег. выр --- звёздочка:

• РВ* → РВ...РВ. Пример: a* → ε, a, aa, ...; [a-z]* → ε, f, c, abc, aaa, uu, ...

Есть более мощный модификатор, который лектор запишет фигурными скобочками:

• РВ{N1,N2} (N1, N2 опциональны) → РВ...РВ от N1 до N2 раз
• РВ{N} → РВ{N,N}

Примеры:

• a{3} → aaa
• [0-9]{1,5} → 0...99999
• [ab]{,3} → ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb

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

• (РВ1...РВN) &rar; РВ1...РВN

На самом деле, мы занимались довольно странной вещью, пытались по регэкспу построить допустимые слова. В реальности всё происходит в точности в обратном направлении: сначала берём строку, а потом в ней что-то ищем. И тут возн. вопрос, от понимания которого зависит эффект. исп. регэкспов. Конкретно, как происходит подстановка, что чему соотв.

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

• ^ --- начало строки
• $ --- конец строки
• В диапазонах [^...] сопоставляется ∀ ∉ [...]

Итак, по каким правилам производится матчинг: правило очень простое --- самый левый самый длинный. Пример: как aaa заматчится a*a*: .aaa. .ε. . Это важно будет при поиске с заменой. Точно также правило левый длинный работает тогда, когда пытаемся найти подстроку в строке, а она там гже-то в середине и не одна. Пример: 12aa34aaa5. Будет найдено 12 .aa. .ε. 34aaa5. Из этого сразу следует, что повторитель звёздочка --- опасная штука, потому что он может быть подстановлен где угодно всегда. Потому что он может быть сопоставлен пустой строке. Пример: b* → .ε. aaa. Поэтому в прошлом примере правильная подстановка --- .ε. .ε. 12aa34aaa5.

[править] Расширенные регэкспы

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

• a{1,} --- довольно частый вид повторителя, поэтому в расширенных регэкспах (и в том, что вошло в посих) для этоого изобретён знак +: a+. Понятно, что это введено искл. для удобства
• a{0,1} --- a?
• Ещё одно отличие --- в базовых регэкспах специальными являются \(, \), \{, \}, в расширенных наоборот
• Ещё одно --- | --- или. РВ1|РВ2 → РВ1, РВ2
• Ещё --- в POSIX введён класс символов, например alpha:. Таких диапазонов в посихе много.

[править] Нерегулярные грамматики

• \< --- начало слова
• \> --- конец слова

[править] Примеры

[править] Число с плавающей точкой

[+-]?([0-9]+(\.[0-9]*)?|\.[0-9]+)([eE][+-]?[0-9]+)?

[править] Два св-ва регэкспов

Есть очень много задач частного вида.

Лектор обращает внимание на то, что тяжело понять, как будет работать регэксп. Потому что много пустышек.

Регэксп хорош тогда, когда достаточно узок класс задач. В первом варианте книги MRE был регэксп на 16 страниц, который разбирает почтовый адрес.

Ещё одна тема: поиск с заменой. Сейчас будет теор. часть, а практ. в след. раз.

Существует несколько flavors, поэтому совет: использовать posix.

http://www.regular-expressions.info/examplesprogrammer.html