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

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

Регуларните изрази претставуваат стрингови со кои може да се опишат стрингови кои според некоја одредена синтакса спаѓаа во одделна група. Регуларните изрази се користат во многу текст едитори и алатки за пребарување и манипулирање на тела на текстови базирани на одреден модел. Многу програмски јазици ги подржуваат регуларните изрази за манипулиразе со стринговите. На пример, 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

  • aстериск означува дека претходниот израз може да се повторува нула или повеќе пати. На пример "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 стандардот дефинира некои класи или категории на знаци прикажани во следната табела:

Posix1.jpg

Пример: [ [: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).



Наводи[уреди]

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