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

В информатиката регулярен израз (на английски: regular expression, съкращавано понякога като regex или regexp) е последователност от знаци, която дефинира шаблон за търсене. Обикновено този шаблон се използва от алгоритми за претърсване на низове за операции от типа „търсене“ или „търсене и заместване“ върху низове или за проверка на валидността на въведени данни. Това е техника, разработена в рамките на теоретичната информатика и теорията на формалните езици.

Стивън Коул Клийни, спомогнал за разработването на техниката

Понятието възниква през 50-те години, когато американският математик Стивън Коул Клийни формализира описанието на регулярните езици. То влиза в широка употреба във връзка със средствата за текстообработка на Unix. От 80-те години съществуват различни синтаксиси за писане на регулярни изрази. Един от тях е на POSIX, а друг, широко използван – на Perl.

Регулярните изрази се използват в търсачките, диалозите за търсене и заместване в текстообработващите програми и текстовите редактори, в текстообработващи инструменти като sed и AWK и при лексикален анализ. Много езици за програмиране предоставят възможности за работа с регулярни изрази, вградени или достъпни чрез библиотеки.

Шаблони редактиране

Под регулярни изрази често се има предвид конкретният стандартен текстов синтаксис (различен от математическото изписване, описано по-долу) на шаблони за разпознаване на текст. Всеки знак от даден регулярен израз (т.е. всеки знак от низа, описващ шаблона му) представлява или метазнак със специално значение, или обикновен знак с буквално значение (литерал). Например в израза a. a е знаков литерал, който съвпада само с буквата 'a', докато '.' е метазнак, който съвпада с произволен знак, различен от нов ред. И така, този регулярен израз съвпада например с низовете "a ", "ax" и "a0". Използвани заедно, метазнаците и литералите могат да описват текста на даден шаблон или да дефинират допустимия брой повторения на шаблон. В зависимост от метазнаците разпознаването по съответния шаблон може да варира от точно равенство до много свободно подобие. Например . е много общ шаблон, [a-z] (съответства на малките букви от a до z) е по-конкретен, а a е съвсем прецизен (съвпада само с буквата a). Синтаксисът на метазнаците е проектиран специално за сбито и гъвкаво представяне на търсените низове, което да позволява автоматизирана обработка на широк набор от текстове и да може лесно да се въвежда със стандартна компютърна клавиатура по стандарт ASCII.

Едно много просто приложение на регулярни изрази с този синтаксис е търсенето на дума, изписана по два различни начина, в текстов редактор. Например с регулярния израз seriali[sz]e се открива както "serialise", така и "serialize". Това може да се постигне и чрез заместващи знаци (wildcards), но техните възможности и синтаксис са доста по-ограничени.

Чрез заместващите знаци най-често се пресяват сходни имена в списък от файлове, докато регулярните изрази обикновено се използват за претърсване на произволни текстове. Например регулярният израз ^[ \t]+|[ \t]+$ разпознава излишните интервали в началото или края на ред. По-сложният израз [+-]?(\d+(\.\d+)?|\.\d+)([eE][+-]?\d+)? може да послужи за разпознаване на произволно число.

Транслиране на звездата на Клийни с алгоритъма на Томпсън
(s* означава „нула или повече пъти s“)

Процесорите на регулярни изрази транслират регулярни изрази с горния синтаксис до изпълнимо вътрешно представяне, което може да бъде проверявано за съответствие с низ, представящ претърсвания текст. Един от възможните подходи е с алгоритъма на Томпсън да се конструира недетерминиран краен автомат (НКА), който се детерминира и полученият детерминиран краен автомат (ДКА) се изпълнява върху претърсвания текстов низ, за да се разпознаят поднизове, които съответстват на регулярния израз. На илюстрацията е показана схемата на НКА N(s*), получен от регулярния израз s*, където по-простият регулярен израз s вече е бил рекурсивно транслиран до НКА N(s).

История редактиране

Регулярните изрази са създадени през 1951 г., когато математикът Стивън Коул Клийни описва регулярни езици чрез свои собствени математически означения, наречени регулярни множества.^[1] Те възникват в теоретичната информатика, в подобластите теория на автоматите (модели на изчислителни процеси) и описание и класификация на формални езици. Други ранни реализации на търсене по шаблон включват езика SNOBOL, който не използва регулярни изрази, а свои собствени конструкции.

Регулярните изрази влизат в широка употреба през 1968 г. с две предназначения: търсене по шаблон в текстов редактор^[2] и лексичен анализ в компилатор.^[3] Една от първите появи на регулярни изрази в програма е когато Кен Томпсън вгражда означенията на Клийни в редактора QED като средство за търсене по шаблон в текстови файлове.^[2]^[4]^[5]^[6] За повишаване на бързодействието Томпсън реализира сравняването по регулярен израз чрез компилация „на момента“ (JIT, just-in-time compilation) към код за IBM 7094 с операционна система CTSS, което е важен ранен пример за този тип компилация.^[7] По-късно той добавя тази възможност към редактора на Unix ed, което впоследствие довежда до употребата на регулярни изрази в популярния инструмент за търсене grep (думата "grep" идва от командата за търсене с регулярен израз в редактора ed: g/re/p, което означава "Global search for Regular Expression and Print matching lines" – глобално търсене с регулярен израз и отпечатване на съответстващите редове^[8]). Приблизително по времето, когато Томпсън разработва QED, изследователска група, включваща Дъглас Т. Рос, реализира инструмент, базиран на регулярни изрази, който се използва за лексичен анализ при проектиране на компилатори.^[3]

През 70-те години много вариации на тези оригинални видове регулярни изрази се използват в програмите за Unix^[6] в Бел Лабс, включително vi, lex, sed, AWK и expr, както и в други програми като Emacs. Впоследствие регулярните изрази са внедрени в широк набор от програми, като тези ранни техни форми са стандартизирани в стандарта POSIX.2 през 1992 г.

През 80-те години в Perl се появяват по-сложни регулярни изрази, базирани отначало върху библиотека от Хенри Спенсър (1986 г.), който по-късно написва реализация на „усъвършенствани регулярни изрази“ (Advanced Regular Expressions) за Tcl.^[9] Библиотеката на Tcl е хибридна реализация НКА/ДКА с подобрена производитеност. Сред софтуерните проекти, внедрили реализацията на регулярни изрази за Tcl от Спенсър, е PostgreSQL.^[10] По-късно в Perl оригиналната библиотека на Спенсър е разширена с добавянето на много нови възможности,^[11] но все още не е настигнала неговата реализация ARE по отношение на производителността и работата с Уникод.^[12]^[13] Част от усилията по проектирането на Perl 6 е насочена към подобряване на интеграцията на регулярните изрази и увеличаване на обхвата и възможностите им, за да се позволи дефинирането на граматики за синтактичен анализ.^[14] Резултатът е миниезик, наречен Perl 6 rules (Правила на Perl 6), с който е дефинирана граматиката на Perl 6 и който може да се използва от програмистите на езика. Тези правила запазват съществуващите възможности на регулярните изрази от Perl 5.x, но също така позволяват дефиниране на рекурсивен синтактичен анализатор чрез вложени правила, подобни на формата на Бекус-Наур.

Употребата на регулярни изрази в стандартите за структурирана информация, използвани за моделиране на документи и бази от данни, започва през 60-те и се разширява през 80-те години, когато се консолидират индустриални стандарти от рода на SGML (предшестван от "GCA 101 – 1983" на ANSI). Стандартите за езици за дефиниране на структури са базирани на регулярни изрази. Употребата им ясно личи в синтаксиса за групи от елементи на DTD.

През 1997 г. Филип Хейзъл започва да разработва библиотеката PCRE (Perl Compatible Regular Expressions, регулярни изрази, съвместими с Perl), която е предназначена наподобява точно функционалността на Perl за регулярни изрази и се използва в много съвременни инструменти, включително PHP и Apache HTTP Server.

Днес регулярните изрази се поддържат широко в езиците за програмиране, програмите за текстообработка (особено лексичните анализатори), усъвършенстваните текстови редактори и други видове програми. Поддръжката за регулярни изрази е част от стандартните библиотеки на много програмни езици, включително Java, Python и C++ (от C++11), и са вградени в синтаксиса на други, като Perl и ECMAScript. Налице са и самостоятелни библиотеки за многократно използване.

Основни понятия редактиране

Регулярните изрази, често наричани на английски и patterns (шаблони), служат за задаване на множества от низове, необходими за определена цел. Един прост начин да се зададе крайно множество от низове е да се изброят елементите му. Често обаче има по-компактен начин да се опише желаното множество. Например множеството от трите низа "Handel", "Händel" и "Haendel" може да бъде описано с шаблона H(ä|ae?)ndel; казваме, че този шаблон съответства на или съвпада с всеки от трите низа. В повечето формализми ако на дадено множество съответства поне един регулярен израз, то съществуват и безкрайно количество други регулярни изрази, които също му съответстват – описанието не е уникално. Повечето формализми предоставят следните операции за конструиране на регулярни изрази.

Логическо „или“: С вертикална черта се разделят алтернативи. Например gray|grey съвпада с "gray" и "grey".
Групиране: Скобите се използват за задаване на област на действие и приоритет на операторите (както и за други цели). Например, gray|grey и gr(a|e)y са еквивалентни шаблони, които описват множеството от двата низа "gray" и "grey".
Квантори: Квантор, добавен след даден синтактичен елемент (например знак) или група указва колко срещания на елемента се допускат. Най-често употребяваните квантори са въпросителен знак ?, звездичка * (от операцията звезда на Клийни), и знак плюс + (плюс на Клийни).

`?`	Въпросителният знак означава нула или едно срещане на предходния елемент. Например `colou?r` съвпада с "color" и "colour".
`*`	Звездичката означава нула или повече срещания на предходния елемент. Например `ab*c` съвпада с "ac", "abc", "abbc", "abbbc" и т.н.
`+`	Знакът плюс означава едно или повече срещания на предходния елемент. Например `ab+c` съвпада с "abc", "abbc", "abbbc" и т.н., но не и с "ac".
`{n}`^[15]	Допускат се точно n поредни съответствия на предходния елемент.
`{min,}`^[15]	Допускат се min или повече поредни съответствия на предходния елемент.
`{min,max}`^[15]	Допускат се поне min но не повече от max поредни съответствия на предходния елемент.

Заместител

Заместващият символ . съвпада с произволен знак. Например a.b съвпада с всеки низ, който съдържа "a", последван от произволен знак и след това "b", а a.*b съответства на всеки низ, който съдържа "a", последвано след някакъв брой знаци от "b".

Тези конструкции могат да бъдат комбинирани, за да се изграждат произволно сложни изрази, точно както аритметичните изрази могат да се конструират от числа и операциите +, −, . и :. Например, както H(ae?|ä)ndel, така и H(a|ae|ä)ndel са валидни шаблони, които съответстват на същите низове като в предходния пример, H(ä|ae?)ndel.

Точният синтаксис на регулярните изрази варира според софтуера и контекста; повече подробности са дадени в раздела Синтаксис.

Теория на формалните езици редактиране

В теорията на формалните езици регулярните изрази описват регулярни езици. Те имат същата изразителна сила като регулярните граматики.

Формална дефиниция редактиране

Регулярните изрази се състоят от константи, които обозначават множества от низове, и символи за операции, които обозначават операции върху тези множества. Следващото определение е стандартно и присъства в повечето учебници по теория на формалните езици. ^[16]^[17] Ако е дадена крайна азбука Σ, следните константи се дефинират като регулярни изрази:

(празно множество) ∅ обозначава множеството ∅.
(празна дума) ε обозначава множество с единствен елемент „празната“ дума, която не съдържа никакви символи.
(литерал) a от Σ означава множеството, съдържащо само символа a.

Ако са дадени регулярните изрази R и S, над тях са дефинирани следните операции, чиито резултати също са регулярни изрази:

(конкатенация) RS обозначава множеството от думите, които могат да се получат чрез конкатениране (долепване) на дума от R и дума от S. Например, ако R = {"ab", "c"} и S = {"d", "ef"}, то RS = {"abd", "abef", "cd", "cef"}.
(алтернация) R | S обозначава обединението на множествата, описани от R и S. например, ако R описва {"ab", "c"} и S описва {"ab", "d", "ef"}, то изразът R | S описва {"ab", "c", "d", "ef"}.
(звезда на Клийни) R* обозначава най-малкото надмножество на множеството, описвано от R, което съдържа ε и е затворено спрямо конкатенацията. Това е множеството на всички думи, които могат да се получат чрез конкатениране на произволен краен брой (включително нула) думи от множеството, описвано от R. Например {"0","1"}* е множеството на всички крайни двоични низове (включително празния), а {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", … }.

С цел избягване на скобите се приема, че звездата на Клийни има най-висок приоритет, следвана от конкатенацията и алтернацията. Ако няма двусмислие, скобите могат да се пропускат. Например (ab)c може да се изпише като abc, а a|(b(c*)) – като a|bc*. В много учебници за алтернация се използват символите ∪, + или ∨ вместо вертикална черта.

Примери:

a|b* обозначава множеството {ε, "a", "b", "bb", "bbb", …}
(a|b)* обозначава множеството от всички думи, съставени само от символите "a" and "b", включително празната дума: {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", …}
ab*(c|ε) обозначава множеството от думите, започващи с "a", последвано от нула или повече "b" и накрая, незадължително, от "c": {"a", "ac", "ab", "abc", "abb", "abbc", …}
(0|(1(01*0)*1))* обозначава множеството на двоичните числа, кратни на 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", … }

Изразителна сила и компактност редактиране

Формалното определение на регулярните изрази е преднамерено пестеливо и не дефинира дублираните квантори ? и +, които могат да бъдат изразени както следва: a+ = aa* и a? = (a|ε). Понякога се добавя операторът за допълненение, при което се получават обобщени регулярни изрази; R^c съвпада с всички думи над Σ*, които не съвпадат с R. По принцип този оператор е дублиран, защото винаги може да се опише чрез останалите. Изчисляването на подобно представяне обаче е сложно и резултатът може да изисква изрази с двойно експоненциално по-голям размер. ^[18]^[19]

Регулярните изрази в този смисъл могат да изразяват регулярните езици, точно същия клас езици, които се разпознават от детерминираните крайни автомати. Има обаче сериозна разлика в компактността. Някои класове регулярни езици могат да бъдат описани само от детерминирани крайни автомати, чийто размер расте експоненциално спрямо размера на най-късите еквивалентни регулярни изрази. Тук стандартният пример са езиците L_k, състоящи се от всички думи над азбуката {a, b}, чиято k^-та буква от края е a. От една страна, един регулярен израз, описващ L₄, е $(a\mid b)^{*}a(a\mid b)(a\mid b)(a\mid b)$ .

Като обобщим този шаблон за L_k, получаваме израза $(a\mid b)^{*}a\underbrace {(a\mid b)(a\mid b)\cdots (a\mid b)} _{k-1{\text{ пъти}}}.\,$

От друга страна, известно е, че всеки детерминиран краен автомат, разпознаващ езика L_k, трябва да има поне 2^k състояния. За щастие съществува просто изображение от регулярните изрази към по-общите недетерминирани крайни автомати (НКА), което не води до такова повишаване на размера; затова НКА често се използват като алтернативно представяне на регулярните езици. НКА са проста вариация на граматиките от тип 3 в йерархията на Чомски.^[16]

В обратна посока, има много езици, които лесно се описват с ДКА, но не и с регулярен израз.

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

Накрая, струва си да се отбележи, че много от практически реализираните ядра за „регулярни изрази“ реализират възможности, които не могат да се опишат с регулярни изрази в смисъла на теорията на формалните езици. За да се подчертае тази разлика, използваните в тях изрази често се наричат на английски regexes вместо regular expressions. За повече сведения вижте по-долу.

Еквивалентност на регулярни изрази редактиране

Както се вижда от горните примери, има много начини да се конструира регулярен израз, за да се постигне един и същ резултат.

Възможно е да се състави алгоритъм, който определя дали два дадени регулярни израза описват един и същ език. Той свежда всеки от изразите до минимален детерминиран краен автомат и определя дали двата автомата са изоморфни (еквивалентни).

Алгебричните закони за регулярните изрази могат да се получат чрез метода на Гишър, който най-добре се обяснява чрез пример: за да се провери дали (X+Y)^* и (X^* Y^*)^* представят един и същ регулярен език за всички регулярни изрази X и Y, е необходимо и достатъчно да се провери дали конкретните регулярни изрази (a+b)^* и (a^* b^*)^* представят един и същ език над азбуката Σ={a, b}. По-общо, равенството E=F между два регулярни израза с променливи е изпълнено тогава и само тогава, когато е изпълнена неговата конкретизация, в която различните променливи са заместени с различни символни константи.^[20]

Синтаксис редактиране

Шаблонът, представляващ регулярен израз, се сравнява с даден обработван низ. Шаблоните представляват поредици от атоми. Атомът е елемент от шаблона, който се проверява за съответствие с обработвания низ. Най-простите атоми са литералите, но групирането на части от шаблона, за да съответстват на атом, изисква използването на ( ) като метазнаци. Метазнаците позволяват съставяне на: атоми; квантори, които указват броя на атомите (и дали кванторът е алчен); набори от алтернативи, свързани чрез логическо „или“; логическо отрицание, което изисква отсъствие на указания атом; обръщения назад, които цитират предходни атоми от частично сравнен шаблон. Съответствие се отчита не когато има съвпадение на всички атоми от низа, а когато има съвпадение на всички шаблонни атоми от регулярния израз. Идеята е да се състави кратък шаблон, който да съответства на голям брой допустими низове, вместо огромен буквален списък от всички възможности.

В зависимост от процесора на регулярни изрази има около четиринайсет метазнака, които може да запазват или не значението си на литерали според контекста и според това дали са екранирани (escaped), т.е. предхождани от определена екранираща последователност (escape sequence), в случая – обратно наклонена черта \. В съвременните регулярни изрази и в тези от POSIX метазнаците се използват по-често със специалното си значение, отколкото като литерали, затова за да не се натрупват обратни наклонени черти, е разумно метазнакът да се екранира, когато е използван като литерал. По принцип обаче има смисъл и четирите ограждащи метазнака – ( ) и { } – да бъдат основно литерали и това подразбирано значение да се екранира, за да се тълкуват като метазнаци. Разпространените стандарти позволяват и двата варианта. Обичайните метазнаци са {}[]()^$.|*+? и \. Обичайните знаци, които се превръщат в метазнаци чрез екраниране, са dswDSW and N.

Разделители редактиране

Когато регулярен израз се въвежда в програмен код, той може да бъде представен като обикновен низов литерал, обикновено ограждан с кавички. Така е например в C, Java и Python, където регулярният израз re се изписва като "re". Регулярните изрази обаче често се изписват с разделител наклонена черта, например /re/ за израза re. Това води началото си от текстовия редактор ed, в който / е командата за търсене и изразът /re/ може да се използва за задаване на диапазон от редове (съответстващи на шаблона), който да бъде комбиниран с още команди и от двете страни. Най-известната такава комбинация е g/re/p като в grep (global regex print), инструмент, включен в повечето базирани на Unix операционни системи, например дистрибуциите на Linux. Подобна конвенция се използва в sed, където търсенето и заместването се указват с s/re/replacement/, а шаблоните могат да се съединяват чрез запетаи, за да се укаже диапазон от редове, например /re1/,/re2/. Този запис е особено известен заради употребата си в Perl, където представлява част от синтаксиса, отделна от нормалните низови литерали. В някои случаи, като при sed и Perl, могат да се използват алтернативни разделители, за да се избегнат конфликти със съдържанието на израза и да не е необходимо екраниране на знаците разделители, ако се срещат в израза. Например в sed командата s,/,X, замества / с X, използвайки запетаи като разделители.

Стандарти редактиране

Стандартът POSIX на IEEE дефинира три нива на спецификацията: BRE (Basic Regular Expressions, основни регулярни изрази),^[21] ERE (Extended Regular Expressions, разширени регулярни изрази) и SRE (Simple Regular Expressions, прости регулярни изрази). Спецификацията SRE е изоставена^[22] в полза на BRE, като и двете предоставят съвместимост назад. Долният подраздел относно класовете знаци важи и за BRE, и за ERE.

BRE и ERE действат заедно. ERE добавя ?, + и | и премахва необходимостта да се екранират метазнаците ( ) и { }, което е задължително в BRE. Освен това, ако се спазва стандартният синтаксис на POSIX за регулярни изрази, може да има – и това се случва често – допълнителен синтаксис, обслужващ конкретни съвместими с POSIX приложения. Макар че POSIX.2 оставя недефинирани някои подробности за реализацията, BRE и ERE предоставят „стандарт“, който с течение на времето е възприет като подразбиран от много програми, в които обикновено се поддържа опция за избор на режим BRE или ERE. Например GNU grep има следните опции: "grep -E" за ERE, "grep -G" за BRE (подразбира се), и "grep -P" за Perl.

Регулярните изрази на Perl са се превърнали в де факто стандарт, предоставяйки богат и мощен набор от атомарни изрази. Perl няма „основно“ и „разширено“ ниво. Както и в ERE на POSIX, ( ) и { } се третират като метазнаци, ако не са екранирани; други метазнаци се разпознават като литерали или специални символи според контекста. Допълнителната функционалност включва мързеливо търсене, търсене с връщане назад, наименувани групи и рекурсивни шаблони.

POSIX – основни и разширени регулярни изрази редактиране

В стандарта POSIX основният синтаксис за регулярни изрази (BRE) изисква метазнаците ( ) и { } да се означават с  и \{\}, а разширеният синтаксис (ERE) – не.

Метазнак	Описание
`^`	Съвпада с началната позиция в низа. В инструментите, работещи с редове, съвпада с началната позиция на произволен ред.
`.`	Съвпада с произволен единичен знак (много приложения изключват знаците за нов ред; кои знаци се смятат за такива зависи от програмата, кодировката и платформата, но знакът LF на практика винаги е сред тях). В изразите с квадратни скоби на POSIX точката означава буквално точка. Например `a.c` съвпада с "abc", и т.н., но `[a.c]` съвпада само с "a", "." или "c".
`[ ]`	Израз с квадратни скоби. Съвпада с един знак измежду изброените в скобите. Например `[abc]` съвпада с "a", "b" или "c". `[a-z]` задава диапазон, който съвпада с произволна малка буква от "a" до "z". Тези форми могат да се смесват: `[abcx-z]` съвпада с "a", "b", "c", "x", "y" или "z", както и `[a-cx-z]`. Знакът `-` се третира като литерал, ако е последен или първи (след `^`, ако присъства) в квадратните скоби: `[abc-]`, `[-abc]`. Забележете, че не се допуска екраниране с обратно наклонена черта. Знакът `]` може да бъде включен в израз с квадратни скоби, ако е първи (след `^`): `[]abc]`.
`[^ ]`	Съвпада с един знак, който не присъства между скобите. Например `[^abc]` съвпада с произволен знак, различен от "a", "b" и "c". `[^a-z]` съвпада с произволен знак, който не е малка буква от "a" до "z". Литералите могат да се смесват с диапазони по същия начин.
`$`	Съвпада с крайната позиция на низа или позицията точно преди знак за нов ред в края на низа. В програмите, работещи с редове, съвпада с крайната позиция на произволен ред.
`( )`	Отбелязват подизраз. Низът, съответстващ на елементите между скобите, може да бъде цитиран по-късно (вижте следващата рубрика, `\n`). Отбелязаните подизрази се наричат още блокове (blocks) или разпознати групи (capturing groups). Режимът BRE изисква ``.
`\n`	Съвпада с това, което е било разпознато с n-тия отбелязан подизраз, където n е цифра от 1 до 9. Тази конструкция е неясно дефинирана в стандарта POSIX.2. Някои програми позволяват цитиране на повече от девет подизраза.
`*`	Съвпада с нула или повече повторения на предишния елемент. Например `abc` съвпада с "ac", "abc", "abbbc" и т.н. `[xyz]` съвпада с "", "x", "y", "z", "zx", "zyx", "xyzzy" и т.н. `(ab)*` съвпада с "", "ab", "abab", "ababab" и т.н.
`{m,n}`	Съвпада с поне m, но не повече от n повторения на предходния елемент. Например `a{3,5}` съвпада само с "aaa", "aaaa" и "aaaaa". Това не се поддържа в някои по-стари варианти на регулярните изрази. Режимът BRE изисква `\{m,n\}`.

Примери:

.at съвпада с произволен низ от три знака, завършващ с "at", включително "hat", "cat" и "bat".
[hc]at съвпада с "hat" и "cat".
[^b]at съвпада с всички низове, съответстващи на .at, освен "bat".
[^hc]at съвпада с всички низове, съответстващи на .at, освен "hat" и "cat".
^[hc]at съвпада с "hat" и "cat", но само в началото на низа или реда.
[hc]at$ съвпада с "hat" and "cat", но само в края на низа или реда.
\[.\] съвпада с един произволен знак, ограден от "[" и "]", тъй като квадратните скоби са екранирани, например "[a]" и "[b]".
s.* съвпада с s, последвано от нула или повече знаци, например "s", "saw" и "seed".

POSIX – разширени регулярни изрази редактиране

В синтаксиса на POSIX за разширени регулярни изрази (ERE) значението на някои от метазнаците, екранирани с обратно наклонена черта, е обърнато. При този синтаксис екраниращият знак предизвиква третиране на метазнака като литерал. Така например  вече е ( ), а \{ \} е { }. Освен това се премахва поддръжката за обръщения назад \n и се добавят следните метазнаци:

Метазнак	Описание
`?`	Съвпада с нула или едно срещане на предходния елемент. Например `ab?c` съвпада само с "ac" и "abc".
`+`	Съвпада с едно или повече срещания на предходния елемент. Например `ab+c` съвпада с "abc", "abbc", "abbbc" и т.н., но не и с "ac".
`\|`	Операторът за избор (известен също като алтернация или обединение на множества) съответства или на израза преди този оператор, или на израза след него. Например `abc\|def` съвпада с "abc" и "def".

Примери:

[hc]?at съвпада с "at", "hat" и "cat".
[hc]*at съвпада с "at", "hat", "cat", "hhat", "chat", "hcat", "cchchat" и т.н.
[hc]+at съвпада с "hat", "cat", "hhat", "chat", "hcat", "cchchat" и т.н., но не и с "at".
cat|dog съвпада с "cat" и "dog".

Разширените регулярни изрази на POSIX често могат да се използват със съвременните инструменти на Unix чрез флага -E на командния ред.

Класове знаци редактиране

Класът знаци е най-основното понятие в регулярните изрази след съответствието с литерал. Чрез него се дефинира съответствие на кратка поредица от знаци с по-голямо множество от знаци. Например цялата латиница в горен регистър може да се замести с [A-Z], а \d може да означава произволна цифра. Знаковите класове важат и в двете нива на POSIX.

При задаването на диапазон от знаци като [a-Z] (т.е. от малка буква a до главна z) настройките за локал на компютъра определят съдържанието му според числовото подреждане на знаковата кодировка. В тази последователност може да има цифри или подреждането да бъде abc…zABC…Z или aAbBcC…zZ. Затова стандартът POSIX дефинира клас знаци, който гарантирано ще бъде известен на инсталирания процесор за регулярни изрази. Тези дефиниции са изброени в следната таблица:

POSIX	Нестандартни	Perl/Tcl	Vim	Java	ASCII	Описание
	`[:ascii:]`^[23]			`\p{ASCII}`	`[\x00-\x7F]`	Знаци от ASCII
`[:alnum:]`				`\p{Alnum}`	`[A-Za-z0-9]`	Буквено-цифрови знаци
	`[:word:]`^[23]	`\w`	`\w`	`\w`	`[A-Za-z0-9_]`	Буквено-цифрови знаци плюс "_"
		`\W`	`\W`	`\W`	`[^A-Za-z0-9_]`	Знаци, които не са част от дума
`[:alpha:]`			`\a`	`\p{Alpha}`	`[A-Za-z]`	Буквени знаци
`[:blank:]`			`\s`	`\p{Blank}`	`[ [[\t]]]`	Интервал (шпация) и знак за табулация
		`\b`	`\< \>`	`\b`	`(?<=\W)(?=\w)\|(?<=\w)(?=\W)`	Граници на думи
				`\B`	`(?<=\W)(?=\W)\|(?<=\w)(?=\w)`	Не граници на думи
`[:cntrl:]`				`\p{Cntrl}`	`[\x00-\x1F\x7F]`	Управляващи знаци
`[:digit:]`		`\d`	`\d`	`\p{Digit}` или `\d`	`[0-9]`	Цифри
		`\D`	`\D`	`\D`	`[^0-9]`	Не цифри
`[:graph:]`				`\p{Graph}`	`[\x21-\x7E]`	Видими знаци
`[:lower:]`			`\l`	`\p{Lower}`	`[a-z]`	Малки букви
`[:print:]`			`\p`	`\p{Print}`	`[\x20-\x7E]`	Видими знаци и интервал (шпация)
`[:punct:]`				`\p{Punct}`	[][!"#$%&'()*+,./:;<=>?@\^_`{\|}~-]	Пунктуационни знаци
`[:space:]`		`\s`	`\_s`	`\p{Space}` или `\s`	`[ \t\r\n\v\f]`	Знаци за празно място
		`\S`	`\S`	`\S`	`[^ \t\r\n\v\f]`	Не знаци за празно място
`[:upper:]`			`\u`	`\p{Upper}`	`[A-Z]`	Главни букви
`[:xdigit:]`			`\x`	`\p{XDigit}`	`[A-Fa-f0-9]`	Шестнадесетични цифри

Класовете от знаци в POSIX могат да се използват само в изрази с квадратни скоби. Например [[:upper:]ab] съвпада с главните букви и малките "a" и "b".

Допълнителен клас извън POSIX, разпознаван от някои програми, е [:word:], който обикновено се дефинира като [:alnum:] плюс знака долна черта. Това отразява факта, че в много езици за програмиране това са знаците, разрешени за използване в идентификатори. Редакторът Vim освен това разпознава класовете word и word-head (изписвани като \w и \h), защото в много езици за програмиране знаците, допустими като начало на идентификатор, са различни от тези, които са разрешени в други позиции.

Обърнете внимание, че класовете знаци от стандарта на POSIX за регулярни изрази обикновено се споменават с уточнението класове знаци на POSIX в други видове регулярни изрази, които ги поддържат. При повечето други видове регулярни изрази под клас знаци се разбира това, което в POSIX се нарича „израз с квадратни скоби“.

Perl и PCRE редактиране

В много инструменти и езици за програмиране се използва синтаксис, подобен на този на Perl, заради изразителната му сила и (относителна) четливост, например Java, JavaScript, Python, Ruby, Qt, .NET Framework на Майкрософт и XML Schema. Някои езици и инструменти, като Boost и PHP, поддържат по няколко вида регулярни изрази. Производните на Perl реализации на регулярни изрази не са еднакви и обикновено предоставят подмножество на функционалността от Perl 5.0, издаден през 1994 г. В Perl понякога се включва функционалност от други езици, например в Perl 5.10 са реализирани синтактични разширения, отначало разработени в PCRE и Python.^[24]

Мързеливо сравняване редактиране

В Python и някои други реализации (например Java) трите основни квантора (*, + и ?) по подразбиране са алчни, защото съвпадат с възможно най-дългата поредица от знаци.^[25] Регулярният израз ".+", приложен върху низа

"Ganymede," he continued, "is the largest moon in the Solar System."

съвпада с целия ред, вместо само с първия знак, ". Горните квантори обаче могат да бъдат направени мързеливи или минимални, за да съответстват на възможно най-късата поредица от знаци, чрез добавяне на въпросителен знак: ".+?" съвпада само с "Ganymede,".^[25]

Това обаче не гарантира, че в определен контекст няма да се разпознае цялото изречение. Операторът въпросителен знак не променя значението на оператора точка, така че той все пак може да съвпадне с кавичките във входните данни. Шаблон от рода на ".*?" EOF все пак ще съвпадне с целия низ, ако той е

"Ganymede," he continued, "is the largest moon in the Solar System." EOF

За да се гарантира, че кавичките няма да са част от разпознатия текст, точката трябва да бъде заменена, например така: "[^"]*". Последният израз съвпада с текст, ограден с кавички, който от своя страна не съдържа кавички.

Сравняване без връщане редактиране

В Java след кванторите може да се добавя знак плюс, който забранява връщането назад, дори когато то би позволило цялото сравнение да бъде успешно:^[26] докато регулярният израз ".*", приложен върху низа

"Ganymede," he continued, "is the largest moon in the Solar System."

съвпада с целия ред, изразът ".*+" изобщо не намира съвпадение, защото .*+ „поглъща“ всички обработвани знаци, включително последната кавичка ". Затова кванторите, забраняващи връщането (на английски possessive quantifiers), са най-полезни заедно с отрицателните класове знаци, например "[^"]*+", което съвпада с "Ganymede," от горния низ.

Кванторите без връщане са по-лесни за реализация от алчните и мързеливите квантори и обикновено подобряват ефективността по време на изпълнение.^[26]

Примери редактиране

PHP редактиране

<?php
// Returns true if "abc" is found anywhere in $string.
ereg("abc", $string);

// Returns true if "abc" is found at the beginning of $string.
ereg("^abc", $string);

// Returns true if "abc" is found at the end of $string.
ereg("abc$", $string);

// Returns true if client browser is Netscape 2, 3 or MSIE 3.
eregi("(ozilla.[23]|MSIE.3)", $_SERVER["HTTP_USER_AGENT"]);

// Places three space separated words into $regs[1], $regs[2] and $regs[3].
ereg("([[:alnum]]:+) (:alnum:+) (:alnum:+)", $string, $regs);

// Put a <br /> tag at the beginning of $string.
$string = ereg_replace("^", "<br />", $string);

// Put a <br /> tag at the end of $string.
$string = ereg_replace("$", "<br />", $string);

// Get rid of any newline characters in $string.
$string = ereg_replace("\n", "", $string);
?>

JAVA редактиране

package de.vogella.regex.string;

public class StringMatcher {
  // Returns true if the string matches exactly "true"
  public boolean isTrue(String s){
    return s.matches("true");
  }

  // Returns true if the string matches exactly "true" or "True"
  public boolean isTrueVersion2(String s){
    return s.matches("[tT]rue");
  }

  // Returns true if the string matches exactly "true" or "True"
  // or "yes" or "Yes"
  public boolean isTrueOrYes(String s){
    return s.matches("[tT]rue|[yY]es");
  }

  // Returns true if the string contains exactly "true"
  public boolean containsTrue(String s){
    return s.matches(".*true.*");
  }

  // Returns true if the string contains of three letters
  public boolean isThreeLetters(String s){
    return s.matches("[a-zA-Z]{3}");
    // Simpler from for<br />

// return s.matches("[a-Z][a-Z][a-Z]");
  }

  // Returns true if the string does not have a number at the beginning
  public boolean isNoNumberAtBeginning(String s){
    return s.matches("^[^\\d].*");
  }

  // Returns true if the string contains a arbitrary number of characters except b
  public boolean isIntersection(String s){
    return s.matches("([\\w&&[^b]])*");
  }

  // Returns true if the string contains a number less than 300
  public boolean isLessThanThreeHundred(String s){
    return s.matches("[^0-9]*[12]?[0-9]{1,2}[^0-9]*");
  }

JavaScript редактиране

<code>// The name string contains multiple spaces and tabs,
// and may have multiple spaces between first and last names.
var names = "Harry Trump; Fred Barney; Helen Rigby; Bill Abel; Chris Hand ";

var output = ["---------- Original String\n", names + "\n"];

// Prepare two regular expression patterns and array storage.
// Split the string into array elements.

// pattern: possible white space then semicolon then possible white space
var pattern = /\s*;\s*/;

// Break the string into pieces separated by the pattern above and
// store the pieces in an array called nameList
var nameList = names.split(pattern);

// new pattern: one or more characters then spaces then characters.
// Use parentheses to "memorize" portions of the pattern.
// The memorized portions are referred to later.
pattern = /(\w+)\s+(\w+)/;

// New array for holding names being processed.
var bySurnameList = [];

// Display the name array and populate the new array
// with comma-separated names, last first.
//
// The replace method removes anything matching the pattern
// and replaces it with the memorized string—second memorized portion
// followed by comma space followed by first memorized portion.
//
// The variables $1 and $2 refer to the portions
// memorized while matching the pattern.

output.push("---------- After Split by Regular Expression");

var i, len;
for (i = 0, len = nameList.length; i < len; i++){
  output.push(nameList[i]);
  bySurnameList[i] = nameList[i].replace(pattern, "$2, $1");
}

// Display the new array.
output.push("---------- Names Reversed");
for (i = 0, len = bySurnameList.length; i < len; i++){
  output.push(bySurnameList[i]);
}

// Sort by last name, then display the sorted array.
bySurnameList.sort();
output.push("---------- Sorted");
for (i = 0, len = bySurnameList.length; i < len; i++){
  output.push(bySurnameList[i]);
}

output.push("---------- End");

console.log(output.join("\n"));

C# редактиране

static string MDYToDMY(string input)
{
   try {
      return Regex.Replace(input,
            "\\b(?<month>\\d{1,2})/(?<day>\\d{1,2})/(?<year>\\d{2,4})\\b",
            "${day}-${month}-${year}", RegexOptions.None,
            TimeSpan.FromMilliseconds(150));
   }
   catch (RegexMatchTimeoutException) {
      return input;
   }
}

Източници редактиране

↑ Kleene 1951.
↑ ^а ^б Thompson 1968.
↑ ^а ^б Johnson Porter, с. Ackley, 1968.
↑ A Regular Expressions Matcher // Beautiful Code. O'Reilly Media. ISBN 978-0-596-51004-6. с. 1 – 2. Посетен на 15 май 2013.
↑ An incomplete history of the QED Text Editor // Архивиран от оригинала на 1999-02-21. Посетен на 9 октомври 2013.
↑ ^а ^б Aho Ullman, с. 1992, 10.11 Bibliographic Notes for Chapter 10, p. 589.
↑ Aycock 2003, 2. JIT Compilation Techniques, 2.1 Genesis, p. 98.
↑ Raymond, Eric S. citing Dennis Ritchie. Jargon File 4.4.7: grep // 2003.
↑ New Regular Expression Features in Tcl 8.1 // Посетен на 11 октомври 2013.
↑ PostgreSQL 9.3.1 Documentation: 9.7. Pattern Matching // Посетен на 12 октомври 2013.
↑ Wall, Larry and the Perl 5 development team. perlre: Perl regular expressions // 2006.
↑ Unicode and Localisation Support // Посетен на 11 октомври 2013.
↑ Russ Cox. Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …) // 2007. Посетен на 11 октомври 2013.
↑ Шаблон:Harvtxt
↑ ^а ^б ^в grep(1) man page
↑ ^а ^б Hopcroft, John E., Motwani, Rajeev, Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation. 2nd. Addison-Wesley, 2000.
↑ Sipser, Michael. Chapter 1: Regular Languages // Introduction to the Theory of Computation. PWS Publishing, 1998. ISBN 0-534-94728-X. с. 31 – 90.
↑ Gelade, Wouter, Neven, Frank. Succinctness of the Complement and Intersection of Regular Expressions. 2008. с. 325 – 336.
↑ Gruber, Hermann, Holzer, Markus. Finite Automata, Digraph Connectivity, and Regular Expression Size. Т. 5126. 2008. DOI:10.1007/978-3-540-70583-3_4. с. 39 – 50.
↑ John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Upper Saddle River/NJ, Addison Wesley, 2003. ISBN 0-201-44124-1. Here: Sect.3.4.6, p.117 – 120. — This property need not hold for extended regular expressions, even if they describe no larger class than regular languages; cf. p.121.
↑ ISO/IEC 9945 – 2:1993 Information technology – Portable Operating System Interface (POSIX) – Part 2: Shell and Utilities, преработен като ISO/IEC 9945 – 2:2002 Information technology – Portable Operating System Interface (POSIX) – Part 2: System Interfaces, ISO/IEC 9945 – 2:2003, текуща версия ISO/IEC/IEEE 9945:2009 Information technology – Portable Operating System Interface (POSIX®) Base Specifications, Issue 7
↑ The Single Unix Specification (Version 2)
↑ ^а ^б 33.3.1.2 Character Classes – Emacs lisp manual – Version 25.1 // gnu.org. 2016. Посетен на 13 април 2017.
↑ Perl Regular Expression Documentation // perldoc.perl.org. Посетен на 8 януари 2012.
↑ ^а ^б Regular Expression Syntax // Python Software Foundation. Посетен на 10 октомври 2015.
↑ ^а ^б Essential classes: Regular Expressions: Quantifiers: Differences Among Greedy, Reluctant, and Possessive Quantifiers // Oracle. Посетен на 23 декември 2016.

Тази страница частично или изцяло представлява превод на страницата Regular expression в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[Kleene1951-1] Kleene 1951.

[Thompson1968-2] а ^б Thompson 1968.

[JohnsonPorterAckley1968-3] а ^б Johnson Porter, с. Ackley, 1968.

[Beautiful_Code_Kernighan-4] A Regular Expressions Matcher // Beautiful Code. O'Reilly Media. ISBN 978-0-596-51004-6. с. 1 – 2. Посетен на 15 май 2013.

[5] An incomplete history of the QED Text Editor // Архивиран от оригинала на 1999-02-21. Посетен на 9 октомври 2013.

[AhoUllman199210.11_Bibliographic_Notes_for_Chapter_10,_p._589-6] а ^б Aho Ullman, с. 1992, 10.11 Bibliographic Notes for Chapter 10, p. 589.

[Aycock20032._JIT_Compilation_Techniques,_2.1_Genesis,_p._98-7] Aycock 2003, 2. JIT Compilation Techniques, 2.1 Genesis, p. 98.

[8] Raymond, Eric S. citing Dennis Ritchie. Jargon File 4.4.7: grep // 2003.

[9] New Regular Expression Features in Tcl 8.1 // Посетен на 11 октомври 2013.

[10] PostgreSQL 9.3.1 Documentation: 9.7. Pattern Matching // Посетен на 12 октомври 2013.

[11] Wall, Larry and the Perl 5 development team. perlre: Perl regular expressions // 2006.

[12] Unicode and Localisation Support // Посетен на 11 октомври 2013.

[13] Russ Cox. Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …) // 2007. Посетен на 11 октомври 2013.

[Apocalypse5-14] Шаблон:Harvtxt

[grep-15] а ^б ^в grep(1) man page

[HopcroftMotwaniUllman01-16] а ^б Hopcroft, John E., Motwani, Rajeev, Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation. 2nd. Addison-Wesley, 2000.

[17] Sipser, Michael. Chapter 1: Regular Languages // Introduction to the Theory of Computation. PWS Publishing, 1998. ISBN 0-534-94728-X. с. 31 – 90.

[18] Gelade, Wouter, Neven, Frank. Succinctness of the Complement and Intersection of Regular Expressions. 2008. с. 325 – 336.

[19] Gruber, Hermann, Holzer, Markus. Finite Automata, Digraph Connectivity, and Regular Expression Size. Т. 5126. 2008. DOI:10.1007/978-3-540-70583-3_4. с. 39 – 50.

[20] John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Upper Saddle River/NJ, Addison Wesley, 2003. ISBN 0-201-44124-1. Here: Sect.3.4.6, p.117 – 120. — This property need not hold for extended regular expressions, even if they describe no larger class than regular languages; cf. p.121.

[21] ISO/IEC 9945 – 2:1993 Information technology – Portable Operating System Interface (POSIX) – Part 2: Shell and Utilities, преработен като ISO/IEC 9945 – 2:2002 Information technology – Portable Operating System Interface (POSIX) – Part 2: System Interfaces, ISO/IEC 9945 – 2:2003, текуща версия ISO/IEC/IEEE 9945:2009 Information technology – Portable Operating System Interface (POSIX®) Base Specifications, Issue 7

[22] The Single Unix Specification (Version 2)

[char-classes-emacs-list-2016-23] а ^б 33.3.1.2 Character Classes – Emacs lisp manual – Version 25.1 // gnu.org. 2016. Посетен на 13 април 2017.

[24] Perl Regular Expression Documentation // perldoc.perl.org. Посетен на 8 януари 2012.

[py-re-25] а ^б Regular Expression Syntax // Python Software Foundation. Посетен на 10 октомври 2015.

[es-re-26] а ^б Essential classes: Regular Expressions: Quantifiers: Differences Among Greedy, Reluctant, and Possessive Quantifiers // Oracle. Посетен на 23 декември 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]