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

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

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

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

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

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


1. Історія

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

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


2. У теорії формальних мов

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

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

  • ( зчеплення, конкатенація) RS позначає множину {αβ | α ∈ R & β ∈ S}. Наприклад, {"boy", "girl"} {"friend", "cott"} = {"boyfriend", "girlfriend", "boycott", "girlcott"}.
  • ( диз'юнкція, чергування) R | S позначає об'єднання R і S. Наприклад, {"ab", "c"} | {"ab", "d", "ef"} = {"ab", "c", "d", "ef"}. [4]
  • ( замикання Кліні, зірка Кліні) R * позначає мінімальне надмножество безлічі R, яке містить ε і замкнуто щодо конкатенації. Це є безліч усіх рядків, отриманих конкатенації нуля або більше рядків з R. Наприклад, {"Go", "Russia"} * = {ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo ", ...}.

3. Синтаксис

3.1. Подання символів

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

Більшість символів в регулярному виразі представляють самі себе за винятком спеціальних символів [ ] \ / ^ $ . | ? * + ( ) { }, які можуть бути передуючи символом \ (зворотна коса риса) ("екрановані", "захищені") для представлення їх самих у якості символів тексту. Можна екранувати цілу послідовність символів, уклавши її між \Q і \E.

Приклад Відповідність
a\.? a. або a
a\\\\b a\\b
a\[F\] a[F]
\Q+-*/\E +-*/

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


3.1.2. Будь-який символ

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

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

Набір символів у квадратних дужках [ ] іменується символьним класом і дозволяє вказати інтерпретатору регулярних виразів, що на даному місці в рядку може стояти один з перелічених символів. Зокрема, [абв] задає можливість появи в тексті одного з трьох зазначених символів, а [1234567890] задає відповідність однією з цифр. Можливо вказівку діапазонів символів: наприклад, [А-Яа-я] відповідає всім буквам російського алфавіту, за винятком літер "Е" і "е". [5]

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

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

Деякі символьні класи можна замінити спеціальними метасимволи:

Символ Еквівалент Відповідність
\d [0-9] Цифровой символ.
\D [^0-9] Нецифровой символ.
\s [ \f\n\r\t\v] Пробельный символ.
\S [^ \f\n\r\t\v] Непробельный символ.
\w [[:word:]] Буквенный или цифровой символ или знак подчеркивания.
\W [^[:word:]] Любой символ, кроме буквенного или цифрового символа или знака подчеркивания.

3.2. Позиція усередині рядка

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

Подання Позиція Приклад Відповідність
^ Початок рядка ^a a aa aaa a aa aaa
$ Кінець рядка a$ aaa aa a aaa aa a
\b Кордон слова a\b aa a aa a aa a aa a aa a aa a aa a aa a
\ba a aa a aa a aa a aa a aa a aa a aa a aa
\B Чи не межа слова \Ba\B a a aa a a a a aa a a a a aa a a a a aa a a a a aa a a
\G Попередній успішний пошук \Ga aaa aaa aaa aaa (пошук зупинився на 4-й позиції - там, де не знайшлося a)

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

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

Подання Число повторень Приклад Відповідність
{ n } Рівне n раз colou{3}r colouuur
{ m, n } Від m до n включно colou{2,4}r colouur, colouuur, colouuuur
{ m,} Не менш m colou{2,}r colouur, colouuur, colouuuur і т. д.
{, n } Не більше n colou{,3}r color, colour, colouur, colouuur
Подання Число повторень Еквівалент Приклад Відповідність
* Нуль або більше {0,} colou*r color, colour і т. д.
+ Одне або більше {1,} colou+r colour, colouur і т. д. (Але не color)
? Нуль або одне {0,1} colou?r color, colour

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

Символьні класи в поєднанні з квантіфікаторамі дозволяють встановлювати відповідності з реальними текстами. Наприклад, стовпцями цифр, телефонами, поштовими адресами, елементами HTML -розмітки та ін

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


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

Приклад використання жадібних і ледачих виразів

Вираз (<.*>) відповідає рядку, що містить кілька тегів HTML -розмітки, цілком.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Щоб виділити окремі теги, можна застосувати ледачу версію цього виразу: (<.*?>) Їй відповідає не вся показана вище рядок, а окремі теги (виділені кольором):

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

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

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Википедия - свободная энциклопедия, в которой каждый может изменить или дополнить любую статью

.

Цю проблему можна вирішити двома способами.

  1. Враховувати символи, не відповідні бажаного зразком ( <[^>]*> для вищеописаного випадку).
  2. Визначити квантіфікатор як нежадібних (ледачий, англ. lazy ) - Більшість реалізацій дозволяють це зробити, додавши після нього знак питання.

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

Жадібний Лінивий
* *?
+ +?
{ n,} { n,}?

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


3.3.2. Ревнива квантифікація (Сверхжадная)

При пошуку виразу ( a + a +)+ a ( a + a +)+ a ( a + a +)+ a ( a + a +)+ a ( a + a +)+ a ( a + a +)+ a в рядку aaaaa інтерпретатор піде приблизно за наступним шляхом:

  1. aaaaa
  2. aaaa
  3. aaaa a aaaa a
  4. aaa
  5. aaa aa aaa aa
  6. aaa a aaa a
  7. aaa a a aaa a a aaa a a - І тільки тут, перевіривши всі точки повернення, здасться.

При використанні ревнивого квантіфікатора буде виконаний тільки перший крок алгоритму.

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

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

Жадібний Ревнивий
* *+
? ?+
+ ++
{ n,} { n,}+
Приклад Відповідність
ab(xa)*+a abxa a bxaa abxa a bxaa; але не abxa abxaa abxa abxaa , Так як буква a вже зайнята

3.4. Угрупування

3.4.1. Позначення групи

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

3.4.2. Зворотній зв'язок

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

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

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


3.4.3. Угрупування без зворотного зв'язку

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

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

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

Приклад Відповідність Створювані групи
a(bc|b|x)cc abcc axcc abcc axcc

abcc axcc abcc axcc

a b ccaxcc a b ccaxcc a b ccaxcc

abcca x cc abcca x cc abcca x cc

a(?:bc|b|x)cc немає
a(?>bc|b|x)cc abcc axcc abcc axcc

але не abcc axcc abcc axcc : варіант x знайдений, інші проігноровані

a(?>x*)xa не знайдеться axxxa : Всі x зайняті, і немає повернення всередину групи

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


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

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

Синтаксис Опис
(?i) Включає нечутливість вирази до регістру символів ( англ. case insensitivity )
(?-i) Вимикає
(?s) Включає режим відповідності точки символам переносу рядка і повернення каретки
(?-s) Вимикає
(?m) Символи ^ і $ викликають відповідність тільки після і до символів нового рядка
(?-m) з початком і кінцем рядка
(?x) Включає режим без врахування пробілів між частинами регулярного виразу і дозволяє використовувати # для коментарів
(?-x) Вимикає

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


3.4.6. Коментарі

Для додавання коментарів в регулярний вираз можна використовувати групи-коментарі виду (?# комментарий). Така група інтерпретатором повністю ігнорується і не перевіряється на входження в текст. Наприклад, вираз А(?#тут комментарий)Б відповідає рядку АБ.

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

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

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


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

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

Подання Вид перегляду Приклад Відповідність
(?= шаблон) Позитивний перегляд вперед Людовик(?=XVI) ЛюдовикXV, Людовик XVI, Людовик XVIII, ЛюдовикLXVII, ЛюдовикXXL ЛюдовикXV, Людовик XVI, Людовик XVIII, ЛюдовикLXVII, ЛюдовикXXL ЛюдовикXV, Людовик XVI, Людовик XVIII, ЛюдовикLXVII, ЛюдовикXXL ЛюдовикXV, Людовик XVI, Людовик XVIII, ЛюдовикLXVII, ЛюдовикXXL ЛюдовикXV, Людовик XVI, Людовик XVIII, ЛюдовикLXVII, ЛюдовикXXL
(?! шаблон) Негативний перегляд вперед (з запереченням) Людовик(?!XVI) Людовик XV, ЛюдовикXVI, ЛюдовикXVIII, Людовик LXVII, Людовик XXL Людовик XV, ЛюдовикXVI, ЛюдовикXVIII, Людовик LXVII, Людовик XXL Людовик XV, ЛюдовикXVI, ЛюдовикXVIII, Людовик LXVII, Людовик XXL Людовик XV, ЛюдовикXVI, ЛюдовикXVIII, Людовик LXVII, Людовик XXL Людовик XV, ЛюдовикXVI, ЛюдовикXVIII, Людовик LXVII, Людовик XXL Людовик XV, ЛюдовикXVI, ЛюдовикXVIII, Людовик LXVII, Людовик XXL
(?<= шаблон) Позитивний перегляд назад (?<=Сергей )Иванов Сергей Иванов , Игорь Иванов Сергей Иванов , Игорь Иванов Сергей Иванов , Игорь Иванов
(?шаблон) Негативний перегляд назад (з запереченням) (? Сергей Иванов, Игорь Иванов Сергей Иванов, Игорь Иванов

3.7. Пошук по умові

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

Подання Пояснення Приклад Відповідність
(?(?= если) то | иначе) Якщо операція перегляду успішна, то далі виконується частина то, інакше виконується частина иначе. У виразі може використовуватися будь-яка з чотирьох операцій перегляду. Слід враховувати, що операція перегляду нульовою ширини, тому частини то в разі позитивного або иначе в разі негативного перегляду повинні включати в себе опис шаблону з операції перегляду. (?(?<=а)м|п) ма м , п ап ма м , п ап ма м , п ап ма м , п ап ма м , п ап
(?( n) то | иначе) Якщо n-я група повернула значення, то пошук по умові виконується за шаблоном то, інакше за шаблоном иначе. (а)?(?(1)м|п) м ам , п а п м ам , п а п м ам , п а п м ам , п а п м ам , п а п м ам , п а п

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

4.1. Базові регулярні вирази POSIX

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

У дану версію включені метасимволи:

  • .
  • [ ]
  • [^ ]
  • ^ (діє тільки на початку виразу)
  • $ (діє тільки в кінці виразу)
  • *
  • \{ \} - початковий варіант для { }
  • \( \) - первинний варіант для ( )
  • \ n, де n - номер від 1 до 9

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

  • Зірочка повинна слідувати після вирази, відповідного одиничного символу. Приклад: [xyz]*.
  • Вираз \( блок \)* слід вважати неправильним. У деяких випадках воно відповідає нулю або більше повторень рядки блок. В інших воно відповідає рядку блок *.
  • Усередині символьного класу спеціальні значення символів, в основному, ігноруються. Особливі випадки:
    • Щоб додати символ ^ в набір, його слід помістити туди не першим.
    • Щоб додати символ - в набір, його слід помістити туди першим або останнім. Наприклад:
      • шаблон DNS-імені, куди можуть входити літери, цифри, мінус і точка-роздільник: [-0-9a-zA-Z.];
      • будь-який символ, крім мінуса і цифри: [^-0-9].
    • Щоб додати символ [ або ] в набір, його слід помістити туди першим. Наприклад:
      • [][ab] відповідає ], [, a або b.

4.2. Розширені регулярні вирази POSIX

( англ. extended regular expressions (ERE)). Синтаксис в основному аналогічний традиційному.

  • Скасовано використання зворотної косої межі для метасимволів { } і ( ).
  • Зворотна коса риса перед метасимволом скасовує його спеціальне значення (див. Подання спеціальних символів).
  • Відкинута теоретично нерегулярна конструкція \ n.
  • Додані метасимволи +, ?, |.

4.3. Регулярні вирази, сумісні з Perl

Perl-сумісні регулярні вирази ( англ. Perl-compatible regular expressions (PCRE)) мають більш багатий і в той же час передбачуваний синтаксис, ніж навіть POSIX ERE. З цієї причини дуже багато додатків використовують саме Perl-сумісний синтаксис регулярних виразів.

5. Нечіткі регулярні вирази

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

  • Невський
  • Несвк. просп.
  • Нев. порсект
  • наб. Конала Гребеедова ("Канал Грибоєдова" це назва другого виходу ст.м. Невський Проспект)

Тут звичайні регулярні вирази незастосовні, в першу чергу через те що входять до зразки слова можуть збігатися не дуже точно (нечітко), але тим не менше було б зручно описувати регулярними виразами структурні залежності між елементами зразка, наприклад, в нашому випадку, вказати , що збіг може бути зі зразком "Невський проспект" АБО "Канал Грибоєдова", притому "проспект" може бути скорочено до "пр" або відсутнім, а перед "Канал" може знаходитися скорочення "наб."

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

Існує невелика кількість бібліотек реалізують механізм регулярних виразів з можливістю нечіткого порівняння:

  • TRE - безкоштовна бібліотека на С, що використовує синтаксис регулярних виразів схожий на POSIX (стабільний проект);
  • FREJ - open-source бібліотека на Java, що використовує Lisp-подібний синтаксис і позбавлена ​​багатьох можливостей звичайних регулярних виразів, але зосереджена на різного роду автоматичних замінах фрагментів тексту (бета-версія).

6. Реалізації

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

Примітки

  1. java.sun.com - java.sun.com / docs / books / tutorial / essential / regex /
  2. MSDN - msdn.microsoft.com/ru-ru/library/az24scfc (v = VS.100). aspx
  3. Ахо А., Ульман Дж. Теорія синтаксичного аналізу, перекладу і компіляції. Синтаксичний аналіз. - Світ. - М ., 1978. - Т. 2.
  4. У багатьох книгах використовуються символи , + або замість | .
  5. Для використання послідовностей літер необхідно встановити правильну кодову сторінку, в якій ці послідовності будуть йти в порядку від і до вказаних символів. Для російської мови це Windows-1251, ISO 8859-5 і Юнікод, так як в DOS-855, DOS-866 і KOI8-R російські букви не йдуть однією цілою групою або не впорядковані за алфавітом. Окрему увагу слід приділяти буквах з діакритичними знаками, на зразок російських Е / е, які, як правило, розкидані поза основних діапазонів символів.

Література

  • Фрідл, Дж. Регулярні вирази. - СПб. : "Пітер", 2001. - 352 с. - (Бібліотека програміста). - ISBN 5-318-00056-8
  • Сміт, Білл. Методи та алгоритми обчислень на рядках (regexp) = Computing Patterns in Strings. - М .: "Вильямс", 2006. - 496 с. - ISBN 0-201-39839-7
  • Форту, Бен. Освой самостійно регулярні вирази. 10 хвилин на урок = Sams Teach Yourself Regular Expressions in 10 Minutes. - М .: "Вильямс", 2005. - 184 с. - ISBN 5-8459-0713-6
  • Ян Гойвертс, Стівен Левітан Регулярні вирази. Збірник рецептів. - СПб. : "Символ-Плюс", 2010. - 608 с. - ISBN 978-5-93286-181-3
  • Мельников С. В. Perl для професійних програмістів. Регулярні вирази. - М .: "Біном", 2007. - 190 с. - (Основи інформаційних технологій). - ISBN 978-5-94774-797-3