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

Регуларен израз — низа знаци со која може да се опишат низи кои според некоја одредена синтакса спаѓаа во одделна група. Регуларните изрази се користат во многу текст едитори и алатки за пребарување и манипулирање на тела на текстови засновани на одреден модел. Многу програмски јазици ги поддржуваат регуларните изрази за манипулирање со низите. На пример, Perl и Tcl имаат моќен систем на регуларни изрази изграден директно на нивната синтакса. Алатките (текст едиторот ed и филтерот grep) создадени од Unix беа првите кои го популаризираа концептот на регуларните изрази.

Основни концепти

Регуларните изрази, често наречени шаблони или калапи, се изрази преку кои се опишува група на низи, тие обично се користат за да дадат концизен опис на групата без да ги набројуваат сите елементи во таа група. На пример, групата која ги содржи следниве три низи од знаци Handel, Händel, и Haendel можат да се опишат со шаблонот "H(ä|ae?)ndel" (или алтернативно кажано, шаблонот се совпаѓа со секој од трите низи). Обично се користат следниве операции за да се конструираат регуларните изрази.

Унија

Се означува со вертикална линија („преграда“), како на пример, "gray|grey", која што може да има и скратена верзија како "gr(a|e)y", што значи дека низата може да биде или gray или grey.

Групирање

Заградите обично го опишуваат групирањето, тие означуваат на кој дел се однесува операцијата, како што во претходниот пример "gray|grey" и "gr(a|e)y" оначуваат иста група на низи.

Операторите како ?, * и + означуваат дека некој знак или група од знаци е дозволено на се повторуваат:

? прашалникот како оператор означува дека изразот може да се повторува нула или еден пат. На пример, "colou?r" означува дека низата може да биде или color или colour

астериск означува дека претходниот израз може да се повторува нула или повеќепати. На пример "go*gle", се совпаѓа со низите gogle, google, gooogle.

+ означува дека претходниот израз мора да го има најмалку еднаш, на пример "go+gle", се совпаќа со низите gogle, google, gooogle.

Овие конструкции можат да се комбинираат за да формираат комплексни изрази, слични на оние од кои се конструираат аритметичките операции од броеви и операторите +, *, - и /.

Па на пример, "H(ae?|ä)ndel" и "H(a|ae|ä)ndel", се валидни шаблони за низите дадени на почетокот на текстот, исто така и регуларниот израз "((great )*grand )?((fa|mo)ther)" се совпаѓа со : father, mother, grand father, grand mother, great grand father, great grand mother, great great grand father, great great grand mother, great great great grand father, great great great grand mother итн.

Од тука следува дека прецизноста на синтаксата на регуларните изрази варира во зависнос од алатките кои се користат.

Историја

Потеклото на регуларните изрази е од теоријата за автомати и теоријата на формалните јазици кои се дел на теоретската компјутерска наука. Математичарот Стефан Клини ( Stephan Kleene ) во 50-тите години го опишал овој модел користејќи математичка нотација и го нарекол регуларни сетови. Подоцна Кен Томсон (Ken Thopmson) ja изградил оваа нотација во едиторот QED за па се споредуваат шаблоните со текстуални податотеки. Тој подоцна ја додаде оваа способност на Unix едиторот ed , што всушност доведе со многу популарната алатка за пребарување grep. Од тогаш многу варијации на Томпсоновата адаптација на регуларни изрази широко се употребувани во Unix и други Unix-ови алатки како: expr, awk, Emacs, vi, lex и Perl.

Perl и Tlc се произлезени од регуларните изрази Хенри Спенсер (Henry Spencer), иако Perl подоцна се прошири и над Спенсеровите регуларни изрази. Филип Хезел (Philip Hazel) го изгради PCRE (Perl Compatible Regular Expressions) којшто се обиде приближно да ја има функционалноста на Perl-овите регуларни изрази , но со користење на модерни алатки како PHP, ColdFusion и Apache. Дел од трудот во дизајнот на Perl 6 беше за да се подобрат регуларните изрази на Perl и да се зголемат нивните можности за градење на парсирачки дрва.

Користењето на регуларните изрази во структурните информатички стандарди (за документирање и базно моделирање) е многу битно, тоа започнаво 60-тите , и се прошири во 80-тите кога индустриските стандарди како ISO SGML се утврдија. Јадрото на стандардите на структурно спесифицираните јазици се регуларните изрази.

Теорија на формалните јазици

Регуларните изрази можат да се објаснат со термините од теоријата за формални јазици. Регуларните изрази се состојат од константи и оператори коишто означуваат сетови на низи и операции извршени врз овие низи. Дадена како конечна азбука ∑ следниве константи се дефинираат:

(празна низа) –ε
(знак) – а во ∑

и следниве операции:

Конкатенација RS означува { αβ | α in R and β in S }. На пример {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}
Алтернација R|S означува унија множество од R и S;
Клини оператор – R* Ова е множество на низи кои се направени со конкатенација на нула или повеќе низи во R. На пример {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }.

Горенаведените константи и оператори ја сочинуваат т.н. Клини алгебра. Многу клиги наместо | користат +.

За да се избегнат заградите се претпоставува дека Клини операторот има најголем приоритет, потоа следи конкатенацијата, па унијата. Ако сакаме да манипулираме со приоритетот тогаш користиме загради.

Примери:

a|b* го означува множеството {ε, a, b, bb, bbb, ...}
(а|b)* го означува множеството на низи со каков и да е број на а или на b
ab*(c|ε) го означува множеството на низи кои започнуваат со а, и имаат нува или едно b, и опционално сч
(aa|ab(bb)*ba)*(b|ab(bb)*a)(a(bb)*a|(b|a(bb)*ba)(aa|ab(bb)*ba)*(b|ab(bb)*a))* множество на низи што имаат еднаков број на a и b;

Формалната дефиниција на регуларните јазици е со намера штедлива и го одбегнува користењето на ? и +, кои можат да бидат претставени како:

a+ = aa*,
a? = (ε|a).

Понекогаш се користи и комплементарниот оператор ~, на пример ~Ѕ означува дека множеството на сите низи во ∑* не се во Ѕ. Кмплементарниот оператор секогаш моче да се претстави само со користење на другите оператори.

Регуларните изрази можат да претстават токму таква класа јазици кои можат да се претстават со конечни автомати т.н. регуларни јазици. Но постои значајна разлика во компатибилностаЧ некои класи на регуларни јазици можат да се опишат само со автомати што растат експоненцијално во големина, додека должината на регуларните изрази расте само линеарно. Регуларните изрази кореспондираат на третиот тип на граматики од Чомски хиерархијата и можат да се користат за опишување на регуларниот јазик. Од друга страна има едноставно поврзување на регуларните изрази и недетерминистичките конечни автомати а тоа е дека тие не растат експоненцијално во големина, па поради таа причина недетерминистичките конечни автомати секористат за алтернативна репрезентација на регуларните изрази.

Исто тука може да се проучува експресивната моќ на формализмот. Но со пример се покажува дека различни регуларни изрази можат да изразат ист јазик- па тука формализмот е излишен.

Тука се поставува прашањето како да се елиминира овој проблем. Дали можеме да најдеме подмножествана регуларни изрази кои нема да бидат недвосмислени? Клини операторот и унијата се очигледно потребни но дали можеме да ја ограничиме нивната употреба. Ова излегува дека е изненадувачки тежок проблем.

Синтакса

Традиционалните Unix регуларни изрази

Основните Unix регуларни изрази се дефинирани како нејасни од стрна на POSIX, но сепак тие широко се употребувале за различни цели. Во основната синтакса повеќето знаци се третираат буквално- што значи дека тие се совпаѓаат само со самите себеси (на пример “a” се совпаѓа само со “a”, “(bc” се совпаѓа само со “(bc”)) исклучоците се наречени метазнаци:

. се совпаѓа со билокој знак
[ ] Означува билокој знак кој се наоѓа во заградите. На пример [abc] се совпаѓа со “a” ,“b” или ”c”. [a-z] значи билокој знак од малите знаци во англиската азбука. Ова може и да се искористи на овој начин [abcq-z] што се совпаѓа со било кој од a,b,c,q,r,s,t,u,v,w,x,y,z, , исто како и [a-cq-z].

Знакот ‘-’ се преведува буквално само ако е прв или последен во заградите :[abc-] [-abc]. Треба да се внимава со затворањето на заградите: пример [][ab] се совпаѓа со “]”,”[”, “a”, “b”.

[^ ] Означува било кој знак кој не се содржи во заградите. На пример [^abc] ги означува сите низи кои се различни од “a”, “b”, и “c”. [^a-z] означува било кој низа кој не е мала буквач
^ се совпаѓа со почеток на нова линија,
$ е крај на линија,
( ) со мали загради се обележува подизраз. Доколку сакаме да означиме ( ) како знаци тогаш се користи коса црта $ и $
\n каде што n e број од 1 до 9 , ова се совпаѓа со n-тиот подизраз. Оваа конструкција е теоретски ирегуларна.
* израз од еден знак проследен со * значи нула или повеќе копии на тој знак . На пример "ab*c" се совпаѓа со "ac", "abc", "abbbc" итн. Но , "[xyz]*" ги содржи "", "x", "y", "zx", "zyx", итм.

Примери:

".at" претставува низа од три знаци од типот hat, cat, bat
"[hc]at" ги означува само низите hat и cat
"[^b]at"- сите низи што завршуваат на аt освен bat
"^[hc]at"- означува само hat и cat но на почеток на линија
"[hc]at$"- означува само hat и cat но на крај на линија

Бидејќи многу зависи од тоа како се организирани знаците (пример некаде редоследот е организиран како abc...xyzABC...Z додека некаде како аАbB....zZ), POSIX стандардот дефинира некои класи или категории на знаци прикажани во следната табела:

Пример: [ [:upper:] ]ab ] ги означува сите големи букви плус a и b

Генерално се сложуваме дека [:print:] се состои од [:graph:] плус празно место, но Perl – регуларниот израз [:print:] го поистоветува со [:graph:] унија [:space:].

Друга не-POSIX класа која ја разбираат некои алатки е [:word:], која е дефинирана како [:alnum:] плус повлака. Ова се однесува на тоа дека во многу програмски јазици овие знаци можат да се користат кај променливите.

Алчни изрази

Квантификаторите во регуларните изрази сеобидуваат да совпаднат колку што е можно низи. Ова е голем проблем. На пример некој сака да го пронајде првото појавување на низа со дупли средни загради во следниов текст:

Се случи експлозија на January 26, 2004, in Tainan City, Taiwan.

Обично би го искористиле регуларниот израз (\[\[.*\]\]), кој изгледа коректен. Но овој израз како резултат ќе го врати January 26, 2004, in Tainan City, Taiwan наместо очекуваното January 26. Тоа е затоа што ќе врати сè што е измеѓу првите две загради на January 26 и последните загради на Taiwan .

Постојат два начина да се реши овој проблем , првиот начин е наместо да се специфицира што треба да се пронајде, ќе се означи она што не треба да се пронајде, во овој случај ] не треба да се препознае, па од тука регуларниот израз ќе изгледа вака (\[\^\*\]\]). Но ова нема да важи за овој низа:

A B C D E F G]]

Вториот начин е т.н. модерни регуларни изрази кои дозволуваат квантификаторот да биде означен како не-алчен, со ставање на прашалник после него: (\[\[.*?\]\]). Во PHP програмирањето е дозволено еден квантификатор да биде означен како неалчен со додавање на ‘U’ на крајот на регуларниот израз. На пример /\[\[.*\]\]/U.

POSIX модерни регуларни изрази

Модерните регуларни изрази често се користат со модерните Unix алатки кои ја вклучуваат ознаката за командна линија “-E”. POSIX проширените регуларни изрази се слични на обичните Unix регуларни изрази со тоа што имаат некои мали разлики. Следниве метазнаци се додадени:

+ означува последниот блок треба да се повтори еднаш или повеќепати
? означува последниот блок треба да се повтори нула или еден пат
| оператор за избор, избира еден од двата операнди
Исто така косата црта е одстранета: \{...\} станува {...} и$...$ станува (...).

Примери:

"[hc]+at" ги содржи низите "hat", "cat", "hhat", "chat", "hcat", "ccchat" итн. "[hc]?at" се совпаѓа со "hat", "cat" и "at" "([cC]at)|([dD]og)" се совпаѓа со "cat", "Cat", "dog" и "Dog"

Бидејќи знаците '(', ')', '[', ']', '.', '*', '?', '+', '^' и '$' се користат како специјални симболи треба да се избегнуваат ако се однесуваат букавално или пред нив да се стави знакот \.

Perl-compatible регуларни изрази (PCRE)

Perl има побогата и попредвидлива синтакса која дури и од POSIX проширените регуларни изрази. На пример еве низа којшто можеме да го специфицираме со Perl но не можеме со POSIX без разлика дали квантификаторот ќе ставиме да биде алчен или не, неговиот регуларен израз е /a.*b/, .* ќе се обиде да приграби најмногу ќто е возможно, додека /a.*?b/ тогаш .*? ќе се потруди да го издвои најмалиот дел. Така во дадениот низа “a bad dab”, првиот шаблон ќе го земе целиот низа , а вториот “a b”

Поради оваа причина многу алатки и апликации ја имаат присвоено синтаксата на Perl- како на пример Java, Ruby, Plython, PHP, exim, BBEdit и NET Framework.

Имплементација и време на извршување

Има најмалку два различни алгоритми кои определуваат дали даден низа припаѓа на некој регуларен израз. Најстариот и најбрзиот се заснова на теоријата на формални јазици која што дозволува секој Недетерминистички Конечен Автомат (НКА) да се трансформира во Детерминистички Конечен Автомат (ДКА). Овој алгоритам ја симулира оваа претворба и потоа се извршува резултантниот низа над создадениот ДКА , се внесува еден по еден симбол и така автоматот преминува во состојби, доколку дојде до прифатлива состојба тогаш и низата е прифатлив. Низата со големина n може да се тестира дали припаѓа на некој регуларен израз со големина m за време O(n+2m) или O(nm), во зависност од имплементацијата. Овој алгоритам е брз но не работи за споредување на низи со регуларни изрази кои содржат групина подизрази кои повторно се повикуваат. Постои и таков алгоритам но тој се извршува поспоро за време O(n2m).

Наводи

Forta, Ben. Sams Teach Yourself Regular Expressions in 10 Minutes. Sams. ISBN 0-672-32566-7.
Friedl, Jeffrey. Mastering Regular Expressions. O'Reilly. ISBN 0-596-00289-0.
Habibi, Mehran. Real World Regular Expressions with Java 1.4. Springer. ISBN 1-59059-107-0.
Liger, Francois; Craig McQueen, Paul Wilton. Visual Basic .NET Text Manipulation Handbook. Wrox Press. ISBN 1-86100-730-2.
Sipser, Michael. "Chapter 1: Regular Languages", Introduction to the Theory of Computation. PWS Publishing, 31–90. ISBN 0-534-94728-X.
Stubblebine, Tony. Regular Expression Pocket Reference. O'Reilly. ISBN 0-596-00415-X.