Порівняльний аналіз регулярних виразів в мовах Perl, Shell та C#

Аналітичний звіт

Порівняльний аналіз регулярних виразів в мовах Perl, Shell та C#

Зміст

• Регулярні вирази 3
• Історія 4
• В теорії формальних мов 4
• Представлення символів за їх кодами 5
• Керуючі символи 5
• Скорочене позначення символьних класів 6
• Скорочене позначення символьних класів: символьні класи POSIX 6
• Звичайні символи (літерали) і спеціальні символи (метасимволи) 7
• Символьні класи (набори символів) 7
• Позиція всередині рядка 8
• Квантифікація (пошук послідовностей) 8
• Жадібна і лінива квантифікація 9
• Ревнива квантифікація (наджадібна) 11
• Групування 11
• Атомарне групування 12
• Модифікатори 13
• Коментарі 14
• Перерахування 14
• Перегляд вперед і назад 14
• Пошук за умовою 15
• Різновиди регулярних виразів 15
• Реалізація 19
• Регулярні вирази у мові Perl 20
• Регулярні вирази у Shell 21
• Регулярні вирази у мові C# 21
• Посилання 24

Регулярні вирази

регулярний вираз символ квантифікація

Регулярні вирази (англ. regular expressions, або скорочено RegEx, RegExp, на жаргоні - реджекси, регекси або регекспи) — це формальна мова пошуку і виконання маніпуляцій з підрядками у тексті, що базується на використанні метасимволів (символів-джокерів, англ. wildcard characters). По суті це рядок-зразок (англ. pattern, його часто називають «шаблоном» або «маскою»), що складається з символів і метасимволів та задає правило пошуку.

Регулярні вирази зробили прорив в електронній обробці текстів у кінці XX сторіччя. Набір утиліт (включаючи редактор sed і фільтр grep), що поставляються у дистрибутивах UNIX, одні з перших почали використовувати регулярні вирази для обробки текстів, посприявши тим самим їх поширенню. Багато сучасних мов програмування мають вбудовану підтримку регулярних виразів. Серед них Perl, Java, PHP, JavaScript, мови платформи.NET Framework, Python, Tcl, Ruby та ін.

Регулярні вирази базуються на теорії автоматів та теорії формальних мов. Ці розділи теоретичної кібернетики займаються дослідженням моделей обчислення (автомати) та способами опису та класифікації формальних мов.

Регулярні вирази використовуються деякими текстовими редакторами та утилітами для пошуку та підстановки тексту. Наприклад, за допомогою регулярних виразів можна задавати шаблони, що дозволять:

· знайти всі послідовності символів «тер» у будь-якому контексті: «гелікоптер», «теракот», «Манчестер»;

· знайти окреме слово «кіт» та замінити його на «кішка»;

· знайти слово «клуб», перед яким стоїть слово «футбольний» або «бейсбольний»;

· прибрати з тексту всі речення, в яких зустрічаються слова «кіт» або «кішка».

Регулярні вирази дозволяють створити і набагато складніші шаблони для пошуку та заміни.

Історія

Регулярні вирази базуються на теорії автоматів, теорії формальних мов і класифікації формальних граматик по Хомському. Ці області вивчають обчислювальні моделі (автомати) і способи опису і класифікації формальних мов. У 1940;х рр. Уорен Маккалок і Уолтер Пітс описали нервову систему, використовуючи простий автомат в якості моделі нейрона. Математик Стівен Кліні пізніше описав ці моделі, використовуючи свою систему математичних позначень, що отримала назву «регулярні множини». Кен Томпсон вбудував їх у редактор QED, а потім в редактор ed під UNIX. З цього часу регулярні вирази почали широко застосовуватись в UNIX та UNIX-подібних утилітах, наприклад: expr, awk, Emacs, vi, lex та Perl.

Регулярні вирази в Perl і Tcl походять від реалізації, що написана Генрі Спенсером. Філіп Хейзел розробив бібліотеку PCRE (англ. Perl-compatible regular expressions - Perl-сумісні регулярні вирази), яка використовується в багатьох сучасних інструментах, як PHP та Apache.

В теорії формальних мов

Регулярні вирази складаються з констант і операторів, які визначають множини рядків і множини операцій над ними відповідно. На даному скінченному алфавіті У визначені наступні константи:

· (порожня множина) ?.

· (порожній рядок) е означає рядок, що не містить жодного символу, еквівалентно до ««.

· (символьний літерал) «a», де a — символ алфавіту У.

та наступні операції:

· (зчеплення, конкатенація) RS означає множину б? R & в? S.

· Наприклад, {" boy", «girl» }{" friend", «cott» } = {" boyfriend", «girlfriend», «boycott», «girlcott» }.

· (диз'юнкція) R|S означає об'єднання R і S. Наприклад, {" ab", «c» }|{" ab", «d», «ef» } = {" ab", «c», «d», «ef» }.

· (замикання Кліні, зірка Кліні) R* означає мінімальну надмножину множини R, яка містить е і замкнене відносно конкатенації. Це є множиною всіх рядків, у отримано конкатенацією нуля або більше рядків з R. Наприклад, {" Go", «RegExp» }* = {е, «Go», «RegExp», «GoGo», «GoRegExp», «RegExpGo», «RegExpRegExp», «GoGoGo», «GoGoRegExp», «GoRegExp», …}.

Представлення символів за їх кодами

Інколи доцільним є використання представлення символу за його кодом.

Керуючі символи

Скорочене позначення символьних класів

Для символьних класів, які часто використовуються, існують скорочені позначення.

Скорочене позначення символьних класів: символьні класи POSIX

Багато діапазонів символів залежать від обраних налаштувань локалізації. POSIX стандартизував оголошення деяких класів і категорій символів.

Використання класу можливе лише всередині квадратних дужок.

Наприклад: ^[[:upper:]]+$

Звичайні символи (літерали) і спеціальні символи (метасимволи)

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

[ ] ^ $. |? * + () { }

які мають бути «екрановані» символом оберненої косої риски для того, щоб представляти самі себе у якості символів тексту. Можна екранувати цілу послідовність символів, включивши їх між Q та E.

Аналогічно можуть бути представлені інші спеціальні символи (набір символів, що вимагають екранування, можуть різнитися в залежності від конкретної реалізації). Частина символів, які в тій чи іншій реалізації не потребують екранування, можуть бути екрановані для покращення читаності регулярного виразу, що стає в нагоді у випадку складного виразу.

Метасимвол. (крапка) означає один будь-який символ, але в певних реалізаціях він може не включати символ нового рядка.

Символьні класи (набори символів)

Набір символів в квадратних дужках [ ] називається символьним класом і дозволяє вказати інтерпретатору регулярних виразів, що на даному місці в рядку може стояти один з перелічених символів. Наприклад, [abc] задає можливість появи в тексті одного з трьох вказаних символів, а задає відповідність одній з цифр. В символьних класах існує можливість вказування діапазонів символів: наприклад, [A-Za-z] відповідає всім літерам англійського алфавіту.

Якщо потрібно, можна вказати символи, які не входять у вказаний символьний клас, тоді використовують символ ^ всередині квадратних дужок, наприклад [^0−9] означає будь-який символ, окрім цифр.

Позиція всередині рядка

Наступні символи дозволяють позиціонувати регулярний вираз відносно елементів тексту: початку і кінця рядка, меж слів.

Квантифікація (пошук послідовностей)

Квантифікатор після символу, символьного класу чи групи визначає, скільки разів попередній вираз може зустрічатися. Слід враховувати, що квантифікатор може відноситися до більш, ніж одного символу в регулярному виразі, тільки тоді, коли це символьний клас чи група.

Для найчастіше застосовуваних квантифікаторів існують скорочені позначення.

Часто використовується послідовність.* для позначення будь-якої кількості символів між двома частинами регулярного виразу.

Символьні класи разом з квантифікаторами в регулярних виразах дозволяють встановлювати відповідність з реальними текстами, наприклад: стовпчиками цифр, телефонами, поштовими адресами, елементами HTML або XML розмітки.

Якщо символи { } не утворюють квантифікатор, то їх спеціальне значення ігнорується.

Жадібна і лінива квантифікація

В деяких реалізаціях квантифікаторам в регулярних виразах відповідає максимально довгий рядок з усіх можливих. Такі квантифікатори називаються жадібними (англ. greedy). Це може виявитися значною проблемою. Наприклад, часто очікують, що вираз <.*> знайде в тексті всі HTML-теги. Однак, якщо в тексті є більше одного HTML-тегу, то цьому виразу буде відповідати увесь рядок, що буде містити багато тегів.

Розглянемо HTML-код, який би дозволив розмітити речення нижченаведеним чином.

Quick brown fox jumps over the lazy dog.

Цей код має вигляд:

Quick brown fox jumps over the lazy dog.

У цьому випадку вираз <.*> буде відповідати усьому рядку з багатьма тегами.

Вирішити цю проблему можна двома шляхами:

1. Враховувати символи, які не відповідають бажаному зразку. Для нашого випадку це буде вираз <[^>]*>

2. Визначити квантифікатор, як нежадібний (лінивий, англ. lazy) — більшість реалізацій дозволяють це зробити, додавши до нього знак запитання.

Лінивій версії виразу <.*>, а саме <.*?>, буде відповідати не весь рядок цілком, а окремі теги:

Використання лінивих квантифікаторів може призвести до зворотної проблеми, коли виразу відповідає занадто короткий, зокрема, порожній рядок.

Також загальною проблемою як жадібних, так і лінивих квантифікаторів є точки повернення для перебору варіантів виразу. Точки ставляться після кожної ітерації квантифікатора. Якщо інтерпретатор не знайшов відповідності після квантифікатора, то він починає повертатися по всіх встановлених точках, перераховуючи вираз по-іншому.

Ревнива квантифікація (наджадібна)

На відміну від звичайної (жадібної) квантифікації, ревнива квантифікація не лише намагається знайти максимально довгий варіант, а ще й не дозволяє алгоритму повертатися до попередніх кроків пошуку для того, щоб знайти можливі відповідності для частини регулярного виразу, що лишилась.

Використання ревнивих квантифікаторів збільшує швидкість пошуку, особливо в тих випадках, коли рядок не відповідає регулярному виразу. До того ж, ревниві квантифікатори можуть бути використані для виключення небажаних збігів.

Групування

Круглі дужки використовуються для визначення області дії і пріоритету операцій. Шаблон всередині групи обробляється як єдине ціле і може бути квантифікований. Наприклад, вираз (b[ae]d-?)* знайде послідовність вигляду bad-bad-bedbad-bed.

Один з прикладів застосування групування — це повторне використання груп символів (підрядків, блоків, відмічених виразів), що знайдені раніше. Таке застосування називається групуванням із зворотнім зв’язком. При обробці виразу підрядки, які були знайдені за шаблоном всередині групи, зберігаються в окремій області пам’яті і отримують номер, починаючи з одиниці. Кожному підрядку відповідає пара дужок в регулярному виразі. Квантифікація групи не впливає на збережений результат, тобто зберігається лише перше входження. Зазвичай підтримується до дев’яти нумерованих підрядків, але деякі інтерпретатори дозволяють працювати і з більшою їх кількістю. Згодом в межах даного регулярного виразу можна використовувати позначення від 1 до 9 для перевірки на збіг з підрядком, який було знайдено раніше.

Наприклад, регулярний вираз (this|that)-1 знайде рядок this-this або that-that, але пропустить рядок this-that.

Регулярний вираз <([A-Z][A-Z0−9]*)b[^>]*>(.*?)</1> знайде будь-яку пару HTML-тегів, що відкриваються та закриваються.

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

Якщо група використовується лише для групування і її результат не буде використовуватись пізніше, то можна використовувати групування без зворотного зв’язку, що має вигляд (?:шаблон). Під результат такого групування не буде виділятися окрема пам’ять і, відповідно, йому не буде призначатися номер. Це добре впливає на швидкість виконання виразу, але погіршує зручність його читання.

Атомарне групування

Атомарне групування вигляду (?>шаблон), так само як і групування без зворотного зв’язку, не створює зворотних зв’язків. На відміну від нього, таке групування забороняє повертатися назад по рядку, якщо частина шаблону вже знайдена.

Атомарне групування виконується ще швидше, ніж групування без зворотного зв’язку, і зберігає процесорний час при виконанні решти виразу, оскільки забороняє перевірку будь-яких інших варіантів всередині групи, коли один варіант вже знайдений. Це дуже корисно при оптимізації груп із багатьма різноманітними варіантами.

Модифікатори

Модифікатори діють з моменту входження і до кінця регулярного виразу чи протилежного модифікатора. Деякі інтерпретатори можуть застосувати модифікатор до всього виразу, а не з моменту входження.

Групи-модифікатори можна об'єднати в одну групу: (?i-sm). Така група включає режим i та виключає режими s і m. Якщо використання модифікаторів необхідне лише в межах групи, то потрібний шаблон вказується після модифікаторів і двокрапок. Наприклад, регулярний вираз (?-i)(?i:tv)set знайде TVset, але не TVSET.

Коментарі

Для додавання коментарів в регулярний вираз можна використовувати групи-команди вигляду (?#коментар). Така група буде інтерпретатором повністю проігнорована і не буде перевірятися її входження до тексту. Наприклад, вираз A (?#comment)B відповідає рядку AB.

Перерахування

Вертикальна риска розділяє допустимі варіанти. Наприклад, grey|gray відповідає grey або gray. Слід пам’ятати, що перебір варіантів виконується зліва направо, як вони вказані.

Якщо потрібно вказати перелік варіантів всередині більш складного регулярного виразу, то його потрібно включати у групу. Наприклад, grey|gray або gr (a|e)y описують рядки gray або grey. У випадку з односимвольними альтернативами переважним є варіант gr[ae]y, бо порівняння із символьним класом виконується простіше, ніж обробка групи з перевіркою на всі її можливі модифікатори і генерацією оберненого зв’язку.

Перегляд вперед і назад

У більшості реалізацій регулярних виразів є можливість проводити пошук фрагменту тексту, «проглядаючи» (але не включаючи у знайдене) оточуючий текст, який розташований до чи після шуканого фрагменту тексту. Наприклад, таким чином можна легко знайти ім'я HTML тегу, не включаючи в результат кутові дужки, що його оточують, або інші знаки, але не упускаючи їх при пошуку потрібного контексту. Перегляд з запереченням використовується рідше і «стежить» за тим, щоб вказані відповідності, навпаки, не зустрічалися до чи після шуканого текстового фрагменту.

Пошук за умовою

У багатьох реалізаціях регулярних виразів існує можливість обирати, яким шляхом піде перевірка у тому чи іншому місці регулярного виразу, базуючись на значеннях, які було знайдено раніше.

Різновиди регулярних виразів

Базові регулярні вирази POSIX (англ. basic regular expressions) — це традиційні регулярні вирази UNIX. Синтаксис базових регулярних виразів на даний момент визначений POSIX як застарілий, але він до теперішнього часу широко розповсюджений із міркувань зворотної сумісності. Багато UNIX-утиліт використовують такі регулярні вирази за замовчуванням.

В цю версію включені наступні мета символи:

· .

· [ ]

· [^ ]

· ^ (діє лише на початку виразу)

· $ (діє лише в кінці виразу)

· *

· { } — початковий варіант для { }

· () — початковий варіант для ()

· n, де n — номер від 1 до 9

Особливості:

· Зірочка повинна стояти після виразу, що відповідає одиничному символу.

· Приклад: [xyz]*.

· Вираз (блок)* слід вважати неправильним. В деяких випадках він відповідає нулю чи більшій кількості повторень рядка блок. В інших випадках він відповідає рядку блок*.

· Всередині символьного класу спеціальні значення символів в основному ігноруються. Особливі випадки:

o Щоб додати символ ^ в набір, його слід розмістити там не першим.

o Щоб додати символ — в набір, його слід розмістити там першим, або останнім. Наприклад:

§ Шаблон DNS-імені, куди можуть входити букви, цифри, мінус і точка:

§ [-0−9a-zA-Z.];

§ Будь-який символ, крім мінуса і цифри: [^-0−9].

o Щоб додати символ [ або ] в набір, його слід розмістити там першим. Наприклад: [][ab] відповідає ], [, a або b.

Розширені регулярні вирази POSIX (англ. extended regular expressions). Синтаксис тут в основному є аналогічним до традиційного.

Особливості:

· Відмінено використання зворотної косої риски для метасимволів { } та ().

· Обернена коса риска перед мета символом відміняє його спеціальне значення — екранування.

· Відмінена теоретично нерегулярна конструкція n.

· Додані мета символи +, ?, |.

Регулярні вирази, що є сумісними з Perl (англ. Perl-compatible regular expressions (PCRE)) — це бібліотека, що реалізує роботу регулярних виразів в стилі Perl. Синтаксис регулярних виразів PCRE значно потужніший і гнучкіший, ніж у стандартних регулярних виразів POSIX. В PHP є частиною ядра. Бібліотека написана на Сі та поширюється під вільною бібліотекою BSD.

Наведу простий приклад програми на C++, що використовує цю бібліотеку.

# include

# include

using namespace std;

int main (){

char pattern[] = «[es]»; // шаблон (регулярний вираз)

char str[] = «test»; // початковий рядок

// створення таблиці перекодування для локалі uk

const unsigned char *tables = NULL;

setlocale (LC_CTYPE, (const char *) «uk.»);

tables = pcre_maketables ();

// компілювання регулярного виразу у внутрішнє представлення

pcre *re;

int options = 0;

const char *error;

int erroffset;

re = pcre_compile ((char *) pattern, options, &error, &erroffset, NULL);

if (!re){ // у випадку помилки компіляції

cout << «Failedn» ;

}

else{

int count = 0;

int ovector[30];

count = pcre_exec (re, NULL, (char *) str, strlen (str), 0, null, ovector, 30);

// виконання зіставлення з образом

if (!count){ // якщо нема співпадінь

cout << «No matchn» ;

}

else{

//вивід пар {початок, кінець} співпадіння

for (int c = 0; c < 2 * count; c += 2){

if (ovector[c] < 0){ // або для підвиразів, що не зіставилися

cout << «n» ;

}

else{

cout << ovector[c] << ovector[c + 1] << «n» ;

}

}

}

}

return 0;

}

Реалізація

· NFA (англ. nondeterministic finite-state automata) — не детерміновані скінченні автомати, використовують жадібний алгоритм відкату, перевіряючи всі можливі розширення регулярного виразу у визначеному порядку і обираючи перше задовільне значення. NFA може обробляти підвирази і обернені посилання. Але через алгоритм відкату традиційний NFA може перевіряти одне і те ж місце декілька разів, що негативно впливає на швидкість роботи. Оскільки традиційний NFA приймає першу знайдену відповідність, він може і не знайти найдовше із входжень (цього вимагає стандарт POSIX, і існують модифікації NFA, що виконують цю вимогу — GNU sed). Саме такий механізм регулярних виразів використовується, наприклад у Perl, Tcl та.NET.

· DFA (англ. deterministic finite-state automata) — детерміновані скінченні автомати, працюють лінійно по часу, оскільки не використовують відкати і ніколи не перевіряють яку-небудь частину тексту двічі. Вони можуть гарантовано знайти найдовше співпадіння з усіх можливих. DFA містить тільки кінцевий стан, відповідно, не обробляє обернених посилань, а також не підтримує конструкцій з явним розширенням, тобто не здатен обробити і підвирази. DFA використовується, наприклад в awk, lex та egrep.

Регулярні вирази у мові Perl

Регулярні вирази є важливою частиною мови програмування Perl. Завдяки цьому Perl добре підходить для обробки текстів. Більша частина роботи з регулярними виразами виконується за допомогою операторів =~, m// та s///.

Оператор m// використовується для перевірки на співпадіння. В простішому випадку результат виразу $x =~ m/abc/ буде істинним, якщо і тільки якщо рядок $x буде відповідати регулярному виразу abc.

Наприклад:

Пошук і заміна виконуються за допомогою оператора s///. Конструкція

$x =~ s/abc/def/ замінить перше входження регулярного виразу abc на рядок def.

Регулярні вирази у Shell

Шаблони у shell використовуються для порівняння імен файлів, частин імен чи шляхів із шаблоном.

Для зняття з метасимволу спеціального значення використовують лапки (одинарні і подвійні) та обернену похилу риску .

У порівнянні з регулярними виразами, shell-шаблони мають простішу структуру:

· * — відповідає нульовій чи будь-якій кількості довільних символів;

· ? — відповідає будь-якому одному символу;

· [набір] — відповідає будь-якому одному символу з набору. Це теж називається символьним класом. Аналогічно до регулярних виразів, набір може містити діапазони. Наприклад, символьний клас [a-z0−9] відповідає маленькій літері чи цифрі. Можна інвертувати клас, поставивши «!» чи «^» на початку класу;

· - відміняє спеціальне значення наступного символу.

У UNIX-подібних операційних системах існує багато утиліт, що розширюють можливості операційної системи щодо обробки текстів. Наприклад: vi, sed, grep, csplit, dbx, dbxtool, more, ed, expr, lex, pg, nl та rdist використовують базові регулярні вирази POSIX, а такі як awk, nawk та egrep — розширені регулярні вирази POSIX.

Регулярні вирази у мові C#

Основа обробки тексту за допомогою регулярних виразів — це підсистема обробки регулярних виразів, що представлена у платформі.NET Framework об'єктом System.Text.RegularExpressions.Regex. Мінімальний набір інформації, який потрібно надати підсистемі обробки регулярних виразів для обробки тексту за допомогою регулярних виразів, зводиться до двох речей:

· Шаблон регулярного виразу, який потрібно знайти в тексті;

· Текст, який потрібно проаналізувати за допомогою шаблону регулярного виразу.

В платформі.NET Framework шаблони регулярних виразів визначаються за допомогою спеціального синтаксису, що сумісний з регулярними виразами Perl 5 та має деякі додаткові можливості (наприклад, він підтримує зіставлення справа наліво, чи створення іменованих виразів).

Методи класу Regex дозволяють виконувати наступні дії:

· Визначити, чи зустрічається у вхідному тексті шаблон регулярного виразу, можна шляхом виклику методу isMatch;

· Витягти з тексту одне чи всі входження, що відповідають шаблону регулярного виразу, можна шляхом виклику методу Match чи Matches. Перший метод повертає об'єкт Match, що надає відомості про збіги у тексті. Другий метод повертає колекцію MatchCollection, в яку входять об'єкти Match для всіх збігів, що були знайдені у проаналізованому тексті.

· Замінити текст, що відповідає шаблону регулярного виразу, можна шляхом виклику методу Replace.

Приклад застосування: нехай список розсилки містить записи, в яких, окрім імені та прізвища, може вказуватися звернення («Mr.», «Mrs.», «Miss» чи «Ms.»). Нижчезазначений приклад можна використовувати для прибирання звернень.

using System;

using System.Text.RegularExpressions;

public class Example

{

public static void Main ()

{

string pattern = «(Mr\.? |Mrs\.? |Miss |Ms\.?)» ;

string[] names = { «Mr. Henry Hunt», «Ms. Sara Samuels» ,

" Abraham Adams", «Ms. Nicole Norris» };

foreach (string name in names)

Console.WriteLine (Regex.Replace (name, pattern, String. Empty));

}

}

// Наведена програма виведе наступне:

// Henry Hunt

// Sara Samuels

// Abraham Adams

// Nicole Norris

Посилання

1. http://uk.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%B8%D0%B9_%D0%B2%D0%B8%D1%80%D0%B0%D0%B7

2. http://www.regular-expressions.info

3. http://expressions.org.ua

4. http://en.wikipedia.org/wiki/Regular_expression

5. http://www.zytrax.com/tech/web/regex.htm

6. http://regexpstudio.com/ru/TRegExpr/Help/regexp_syntax.html

7. http://www.troubleshooters.com/codecorn/littperl/perlreg.htm

8. http://ru.wikipedia.org/wiki/Perl

9. http://perldoc.perl.org/perlre.html

10. http://www.gnu.org/software/findutils/manual/html_node/find_html/Shell-Pattern-Matching.html

11. http://b62.tripod.com/doc/docksh.htm

12. http://www.faqs.org/docs/bashman/bashref₃₅.html

13. http://msdn.microsoft.com/en-us/library/hs600312.aspx

14. http://www.rsdn.ru/article/alg/regular.xml