Лекція 6. Регулярні вирази

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

​Лекція 7

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

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

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

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

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

У 1951 році математик Стівен Коул Клін описав концепцію регулярної мови - мови, яка розпізнається скінченним автоматом і формально виражається за допомогою регулярних виразів.

Stephen Cole Kleene

У середині 1960-х піонер комп'ютерних наук Кен Томпсон, один з перших розробників Unix, реалізував зіставлення патернів у текстовому редакторі QED, використовуючи позначення Кліна.

Ken Thompson

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

(скорочено regex або regexp; іноді його називають раціональним виразом) - це послідовність символів, яка задає шаблон співпадіння в тексті.

Використовуються з 1968 року у двох випадках:

• зіставлення патернів у текстовому редакторі

• лексичний аналіз у компіляторі.

Python

Модуль re стандартної біблiотеки Python дозволяє здійснювати пошук за шаблоном в рядках символів та 8 бітних рядках (байтах).

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

Співставлення символів

Кожен окремий символ (наприклад, літера чи цифра) вважається регулярним виразом і за його допомогою можна знайти те, що йому віповідає – такий самий символ. Окремі символи в регулярному виразі можуть поєднуватися.

Наприклад, рядок “dog” буде регулярним виразом і він може використовуватися як шаблон у функціях модуля re . Цьому шаблону будуть відповідати всі рядки, які містять “dog.

Метасимволи

Деякі символи є особливими метасимволами і не співпадають самі з собою. Натомість вони сигналізують про те, що слід зіставити щось незвичайне, або впливають на інші частини RE, повторюючи їх або змінюючи їхнє значення.

Повний список метасимволів: . ^ $ * + ? { } [ ] \ | ( )

Регулярний вираз це рядок, який складається із звичайних та спеціальних символів

​re.match(pattern, string, flags=0)

Якщо нуль або більше символів на початку рядка збігаються з шаблоном регулярного виразу, повертається відповідний об'єкт збігу. Повертається значення None, якщо рядок не збігається з шаблоном.

Зауважте, що навіть у режимі MULTILINE re.match() шукатиме збіги лише на початку рядка, а не на початку кожного рядка.

​re.findall(pattern, string, flags=0)

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

Multiple Choice

• ['Anna']

• ['anna']

• []

• ['Anna', 'anna']

​Метасимволи []

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

Символи можна перерахувати окремо або вказати діапазон символів, ввівши два символи і розділивши їх знаком "-".

Наприклад, [abc] буде відповідати будь-якому з символів a, b або c; це те ж саме, що і [a-c], який використовує діапазон для вираження того ж набору символів.

Якщо ви хочете зіставити лише малі літери, ваш RE буде [a-z].

​Метасимволи [] та інші

Метасимволи (окрім \) не активні всередині класів.

Наприклад, [akm+] буде відповідати будь-якому з символів 'a', 'k', 'm' або '+'; '+' зазвичай є метасимволом, але всередині класу символів він позбавлений своєї особливої природи.

​Метасимволи [] та інші

Ви можете зіставити символи, не перелічені у класі, доповнивши набір. Це позначається додаванням символу '^' як першого символу класу. Наприклад, [^5] буде відповідати будь-якому символу, крім '5'. Якщо каретка з'являється деінде у класі символів, вона не має особливого значення. Наприклад: [5^] буде відповідати або '5', або '^'.

Multiple Choice

• ['Anna']

• ['anna']

• []

• [']nna']

​Метасимвол \

Використовується для усунення всіх метасимволів; наприклад, якщо вам потрібно зіставити [ або \, ви можете поставити перед ними \, щоб прибрати їхнє спеціальне значення: \[ або \\.

Деякі спеціальні послідовності, що починаються з '\', представляють собою заздалегідь визначені набори символів, які часто бувають корисними, наприклад, набір цифр, набір літер або набір усього, що не є пробілами.

Multiple Choice

• ['A', 'n', 'n', 'a', 'a', 'n', 'd', 'H', 'a', 'n', 'n', 'a']

• ['A', 'n', 'n', 'a', 'a', 'n', 'd', 'H', 'a', ']', 'n', 'n', 'a']

• [ 'a', ']']

• []

Здатність зіставляти різні набори символів - це перше, що можуть робити регулярні вирази, чого не можна зробити методами, доступними для рядків. Однак, якби це була єдина додаткова можливість реджексів, вони не були б значним кроком уперед. Інша можливість полягає в тому, що ви можете вказати, що частини RE повинні повторюватися певну кількість разів.

​Метасимвол *

* не відповідає буквальному символу; натомість він вказує, що попередній символ може збігатися з ним нуль або більше разів, а не рівно один раз.

Наприклад, ca*t буде відповідати "ct" (0 символів "a"), "cat" (1 символ "a"), "caaat" (3 символи "a") і так далі.

Як це працює?

Повторення, такі як *, є жадібними; при повторенні RE механізм підбору намагатиметься повторити його якомога більше разів. Якщо наступні частини шаблону не збігаються, механізм підбору зробить резервну копію і спробує повторити з меншою кількістю повторень.

Приклад,

pattern = a[bcd]*b

string = 'abcbd'.

пошук a[bcd]*b в 'abcbd'

​Метасимвол +

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

Наприклад, ca+t збігатиметься з "cat" (1 "a"), "caaat" (3 "a"), але не збігатиметься з "ct".

​Метасимвол ?

Знак питання, ?, вказує на збіг або один раз, або нуль разів; можна вважати, що він позначає щось необов'язкове.

Наприклад, home-?brew збігається з "homebrew" або "home-brew".

Multiple Choice

• ['Anna', 'and', 'H', 'a', 'nna', 'eating', 'cookies']

• ['Anna', '', 'and', '', 'H', '', 'a', '', 'nna', '', 'eating', '', 'cookies', '', '']

• [' ', ' ', '[', ']', ' ', ' ', '.']

• []

Multiple Choice

• []

• ['nna', 'nna']

• ['nna', 'nna', 'nana']

• ['nana']

​Метасимвол {m, n}

Цей квантор означає, що повинно бути щонайменше m повторень і щонайбільше n.

Наприклад, a/{1,3}b буде відповідати 'a/b', 'a//b' і 'a///b'. Він не збігається з 'ab', який не має скісних рисок, або з 'a////b', який має чотири риски.

Ви можете опустити m або n; у цьому випадку замість пропущеного значення буде використано прийнятне значення. Пропуск m інтерпретується як нижня межа 0, тоді як пропуск n призводить до верхньої межі нескінченності.

​Метасимвол {m, n}

Можна помітити, що три інші квантори можуть бути виражені за допомогою цієї нотації.

{0,} дорівнює *,

{1,} еквівалентний +,

{0,1} дорівнює ?.

Краще використовувати , + або ?, коли це можливо, просто тому, що вони коротші і їх легше читати.

​Метасимволи $, ^, .

$

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

^

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

.

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

Multiple Choice

• []

• ['nna', 'nna', 'nny']

• ['Anna ', ']nna ', 'unny.']

• ['unny.']

Групування ()

Групи позначаються метасимволами '(', ')'. Символи '(' і ')' мають те саме значення, що й у математичних виразах: вони об'єднують вирази, що містяться всередині групи, і ви можете повторити вміст групи за допомогою кванторів таких як *, +, ? або {m,n}.

Наприклад, (ab)* буде відповідати нулю або більшій кількості повторень ab.

Групування ()

Групи, позначені символами '(', ')', також фіксують початковий і кінцевий індекс тексту, якому вони відповідають; їх можна отримати, передавши аргумент методам group(), start(), end() і span(). Групи нумеруються, починаючи з 0. Група 0 присутня завжди; це весь RE, тому всі методи об'єктів зіставлення мають групу 0 як аргумент за замовчуванням.

Multiple Choice

• ['cookies']

• ['cookies.']

• ['co']

• ['c']

Multiple Choice

• ['cookies']

• ['cookies.']

• ['co']

• []

Multiple Choice

• Any line containing 'From'

• Any line that starts with 'From'

• Any line that starts with 'From:'

• Any line containing 'From:'

Multiple Choice

Which of these lines will be NOT matched when the following code is run?

• It will cost you $1.00

• From: [e-mail] $a

• $2.50 is your change

• You owe three dollars.

Multiple Choice

Which of the following options will the regular expression ^X-.*: [0-9.]+ match?

• X-DSPAM-Probability: Accurate

• X-DSPAM-Confidence: 0.8475

• S-Wolverine-Confidence: 1

• X Wolverine-Confidence: 0.53