Կանոնավոր արտահայտություններ

**Կանոնավոր արտահայտություն**-ը () որոնման ֆորմալ լեզու է, որը նկարագրում է տողի ենթատողերի հետ կատարվող գործողություններ։ Այն տող-ձևաչափ է (անգլերեն՝ pattern), որը բաղկացած է սիմվոլներից և մետասիմվոլներից՝ ներառելով որոնման կանոնները։

20-րդ դարի վերջում կանոնավոր արտահայտությունները բեկում են առաջացրել տեքստի էլեկտրոնային վերամշակման գործում։ Մի շարք ժամանակակից ծրագրավորման լեզուներ ունեն ներդրված կանոնավոր արտահայտությունների գործիքներ։ Այդպիսի ծրագրավորման լեզուներից են Perl-ը, TCL-ը, Ջավան, PHP-ն, ՋավաՍկրիպտը, Python-ը, Lua-ն, C++11-ը, .NET Framework-ի լեզուները։ Կանոնավոր արտահայտություններն օգտագործվում են մի շարք տեքստային խմբագրիչներում և գործիքներում՝ տեքստի որոնման և փոխարինման համար։ Օրինակ կանոնավոր արտահայտությունների միջոցով կարելի է ստեղծել ձևանմուշներ, որոնք թույլ են տալիս.
* ցանկացած տեքստում գտնել «երգ» բառը պարունակող հաջորդականությունները, օրինակ՝ «երգահան», «մեներգ»։
* գտնել «երգ» բառը և այն փոխարինել «տաղ»-ով։
* գտնել «երաժշտություն» բառը, որին հաջորդում է «ժողովրդական» կամ «էստրադային» բառը։
* տեքստից հեռացնել բոլոր նախադասությունները, որոնք պարունակում են «երգ» կամ «երաժշտություն» բառերը։

## Պատմություն
Կանոնավոր արտահայտությունների պատմության հիմքում ընկած են *ավտոմատների տեսությունը*, ֆորմալ լեզուների տեսությունը, ֆորմալ քերականության դասակարգումը՝ ըստ Չոմսկու։ 1940-ական թվականներին Ուորրեն Մակկալոկը և Ուոլտեր Փիթսը նկարագրել են նյարդային համակարգը, օգտագործելով պարզ ավտոմատը որպես նեյրոնի մոդել։ Ավելի ուշ մաթեմատիկոս Ստիվեն Կլինին նկարագրել է այդ մոդելները՝ օգտագործելով իր մաթեմատիկական նշանակումների համակարգը, որը կոչվում է *կանոնավոր բազմություններ*։ Քեն Թոմփսոնը (Ken Tompson) UNIX օպերացիոն համակարգում կանոնավոր արտահայտություններն իրականացրել է QED, ապա ed խմբագրիչներում։ Այդ ժամանակվանից կանոնավոր արտահայտությունները լայն տարածում են գտել UNIX-ում և UNIX-անման համակարգերում, օրինակ՝ expr, awk, Emacs, vi, lex և Perl գործիքներում ու լեզուներում։

Կանոնավոր արտահայտությունները Perl-ում և Tcl-ում ներառված են Հենրի Սպենսերի կողմից գրված իրականացմամբ։ Ֆիլիպ Հեյզելը մշակել է PCRE գրադարանը (անգլ. Perl-compatible regular expressions)։

## Ֆորմալ լեզուների տեսությունում
Կանոնավոր արտահայտությունները կազմված են հաստատուններից եւ օպերատորներից, որոնք սահմանում են տողերի բազմություն եւ դրանց համապատասխան գործողությունների բազմություն։ Տվյալ վերջավոր Σ այբուբենում սահմանված են հետևյալ հաստատունները՝
* (դատարկ բազմություն) ∅, 
* (դատարկ տող) ε-ով նշանակում են այն տողը, որը որևէ սիմվոլ չի պարունակում։ Հավասարազոր է «», 
* (սիմվոլային լիտերալ) «a», որտեղ a-ն Σ այբուբենի սիմվոլ է, 
* սիմվոլների կամ այլ բազմությունների (բազմություն), 
և հետևյալ գործողությունները՝
* (կոնկատենացիա) RS նշանակում է բազմություն {αβ | α ∈ R & β ∈ S}: Օրինակ՝ {«boy», «girl»}{«friend», «cott»} = {«boyfriend», «girlfriend», «boycott», «girlcott»}, 
* (դիզյունկցիա) R|S նշանակում է R-ի և S-ի միավորում։ Օրինակ՝ {«ab», «c»}|{«ab», «d», «ef»} = {«ab», «c», «d», «ef»}, 
* (Կլինիի փակում, Կլինիի աստղ) R* նշանակում է նվազագույն ենթաբազմություն R բազմությունից, որը պարունակում է ε և փակ է կոնկատենացիայի նկատմամբ, այսինքն բոլոր տողերի բազմությունը, որոնք ստացվում են R-ի զրո կամ ավել տողերի կոնկատենացիայից։ Օրինակ՝ {«Run», «Forrest»}* = {ε, «Run», «Forrest», «RunRun», «RunForrest», «ForrestRun», «ForrestForrest», «RunRunRun», «RunRunForrest», «RunForrestRun», …}:

## Շարահյուսություն
### Սիմվոլների ներկայացումը
Հիմնական հոդվածը՝ Սիմվոլների ներկայացումը կանոնավոր արտահայտություններում։

#### Սովորական սիմվոլներ (լիտերալներ) և հատուկ սիմվոլներ (մետասիմվոլներ)
Կանոնավոր արտահայտություններում նշանների մեծ մասը ներկայացնում են իրենք իրենց՝ բացառությամբ [ ] \ / ^ $ . | ? * + ( ) { } հատուկ սիմվոլների, որոնք կարող են իրենք իրենց ներկայացնել «\»(ետշեղգիծ) սիմվոլի օգնությամբ։ Կարելի է էկրանավորել սիմվոլների մի ամբողջ հաջորդականություն՝ վերցնելով դրանք «\Q»-ի և «\E»-ի միջև։

Նմանապես կարող է ներկայացված լինել այլ հատուկ սիմվոլներ (սիմվոլների հավաքածուն, որոնք պահանջում են էկրանավորում, կարող են տարբեր լինել՝ կախված կոնկրետ իրականացումից)։ Սիմվոլների մի մասը, որոնք այս կամ այն իրականացման ժամանակ չեն պահանջում էկրանավորում (օրինակ պայմանական չակերտները՝ ), կարող են էկրանավորվել տեքստն ընթեռնելի դարձնելու նպատակով։

#### Ցանկացած սիմվոլ
Մետասիմվոլ «.»-ը (կետ) նշանակում է մեկ ցանկացած սիմվոլ՝ բացառությամբ որոշ իրականացումներում նոր տողի դեպքում։

#### Սիմվոլների հավաքածու
Սիմվոլների հավաքածուն քառակուսի փակագծերում՝ [], անվանվում է սիմվոլների դաս և թույլ է տալիս նշել կանոնավոր արտահայտությունների ինտերպրետատորին, որ տողի այդ մասում կարող է լինել թվարկված սիմվոլներից որևէ մեկը։ Մասնավորապես, [աբգ] տալիս է նշված երեք սիմվոլներից մեկին տեքստում հայտնվելու հնարավորություն, իսկ [1234567890]՝ համապատասխանաբար նշված թվերից մեկին։ Կարելի է տալ սիմվոլների միջակայքը հետևյալ ձևով՝ օրինակ [Ա-Ֆա-ֆ] համապատասխանում է հայոց այբուբենի բոլոր տառերին։ Եթե պահանջվում է նշել սիմվոլներ, որոնք չեն մտնում նշված հավաքածուի մեջ, ապա օգտագործում են «^» սիմվոլը քառակուսի փակագծերի մեջ, օրինակ՝ [^0-9] նշանակում է ցանկացած սիմվոլ՝ թվերից բացի։

Հատուկ սիմվոլների հավաքածուների ավելացումը էկրանավորման միջոցով ամենապարզ եղանակն է։ Սակայն ժամանակակից կանոնավոր արտահայտություններում կան նաև ավանդական մոտեցումներ - տես Ավանդական կանոնավոր արտահայտություններ։
Մի շարք սիմվոլների դասեր կարելի է փոխարինել հատուկ մետասիմվոլներով։

### Դիրքը տողի մեջ
Հետևյալ սիմվոլները թույլ են տալիս որոշել կանոնավոր արտահայտությունների տեղը տեքստի էլեմենտների նկատմամբ։

### Խմբի նշանակություն
Կլոր փակագծերը օգտագործվում են գործողության սահմանը և առաջնահերթությունը որոշելու համար։ Խմբի միջի կաղապարը մշակվում է որպես մեկ ամբողջություն։ Օրինակ՝ (տր[աու]մ-?)* արտահայտությունը գտնում է տրամ-տրամ-տրումտրամ-տրում-տրամտրում տեսքի հաջորդականություն։

### Թվարկում
Ուղղահայաց գիծը՝ «|», բաժանում է հնարավոր տարբերակները։ Օրինակ՝ gray|grey համապատասխանում է gray կամ grey: Պետք է հիշել, որ տարբերակների դասավորումը կատարվում է ձախից աջ, ինչպես ցույց են տրված։ Եթե պահանջվում է նշել տարբերակների ցուցակը ավելի բարդ կանոնավոր արտահայտությունների մեջ, ապա դրանք պետք է վերցնել խմբի մեջ:Օրինակ՝ gray|grey կամ gr(a|e)y նկարագրում են gray կամ grey տողը։
Մեկ սիմվոլանի այլընտրանքի դեպքում նախընտրելի է gr(a|e)y, քանի որ սիմվոլների դասի հետ համեմատած ավելի հեշտ է իրականացվում, քան խմբի վերամշակումը՝ իր բոլոր հնարավոր ձևափոխություններով և գեներացնող հետադարձ կապով։

### Քվանցիֆիկացիա (հաջորդականության որոնում)
Սիմվոլից, սիմվոլային դասից կամ խմբից հետո քվանցիֆիկատորը որոշում է, թե քանի անգամ կարող է հանդիպել նախորդ արտահայտությունը։ Նշենք, որ կանոնավոր արտահայտության մեջ քվանցիֆիկատորը կարող է վերաբերել ավելի քան մեկ սիմվոլի, եթե այն սիմվոլային դաս է կամ խումբ։

Հաճախ օգտագործվում է «.*» հաջորդականությունը երկու կանոնավոր արտահայտությունների միջև ցանկացած քանակի և ցանկացած սիմվոլի նշանակման համար։ Սիմվոլային դասերը՝ համադրելով քվանցիֆիկատորների հետ, թույլ են տալիս հաստատել համապատասխանություն իրական տեքստերի հետ։ Օրինակ՝ թվերի, հեռախոսահամարների, փոստային հասցեների սյուներ և այլն։ Եթե «{» և «}» սիմվոլները չեն ձևավորում քվանցիֆիկատոր, նրանց հատուկ նշանակությունը անտեսվում է։

#### Ագահ և ծույլ քվանցիֆիկացիա
Կանոնավոր արտահայտությունների մի քանի իրականացումներում քվանցիֆիկատորներին համապատասխանում է հնարավոր տողերից ամենաերկարը (քվանցիֆիկատորները համարվում են ագահ, անգլերեն՝ greedy)։ Դա կարող է հանդիսանալ կարևոր խնդիր։ Օրինակ՝ հաճախ ակնկալվում է, որ () արտահայտությունը տեքստում կգտնի HTML-ի տեգերը։ Սակայն, եթե տեքստը ունի ավելի քան մեկ HTML-տեգ, ապա այս արտահայտությանը համապատասխանում է տեգերի բազմությունը պարունակող ամբողջ տողը։
**Վիկիպեդիան** ազատ հանրագիտարան է, որտեղ *ամեն ոք* կարող է փոփոխել կամ ավելացնել ցանկացած հոդված։
Այդ խնդիրը կարելի է լուծել երկու եղանակով։
# Դիտարկել սիմվոլները, որոնք չեն համապատասխանում ցանկալի օրինակին (]*> վերը նշված դեպքի համար)։
# Սահմանել քվանցիֆիկատորը որպես ծույլ (անգլերեն՝ lazy)։ Շատ իրականացումներ թույլ են տալիս դա անել՝ քվանցիֆիկատորից հետո ավելացնելով ? սիմվոլը։
Ծույլ քվանցիֆիկատորների օգտագործումը կարող է հանգեցնել հակառակ խնդրին՝ երբ արտահայտությանը համապատասխանում է շատ կարճ, մասնավորապես, դատարկ տող։

Ինչպես նաև ագահ և ծույլ արտահայտությունների ընդհանուր խնդիր են համարվում վերադարձի կետերը արտահայտության տարբերակների կրկնման համար։ Կետերը դրվում են քվանցիֆիկատորի ամեն մի գործողությունից հետո։ Եթե ինտերպրետատորը քվանցիֆիկատորից հետո չի գտել համապատասխանություն, ապա այն սկսում է վերադառնալ բոլոր սահմանած կետերին՝ արտահայտությունը այդտեղից այլ կերպ հաշվելով։

#### Խանդոտ քվանցիֆիկացիա
Ի տարբերություն սովորական (ագահ) քվանցիֆիկացիային, խանդոտ (possessive) քվանցիֆիկացիան ոչ միայն փորձում է գտնել առավելագույն երկարությամբ տարբերակը, 
այլև թույլ չի տալիս ալգորիթմին վերադառնալ նախորդ քայլերին, որպեսզի գտնի հնարավոր համապատասխանությունը կանոնավոր արտահայտության մնացած մասի համար։

Քվանցիֆիկատորի օգտագործումը մեծացնում է փնտրման արագությունը հատկապես այն դեպքերում, երբ տողը չի համապատասխանում կանոնավոր արտահայտությանը։
Բացի այդ, խանդոտ քվանցիֆիկատորները կարող է վերացնել անցանկալի համընկնումները։

Սա նման է ատոմային խմբավորոմանը

### Խմբավորում
#### Հետադարձ կապ
Խմբավորման կիրառություններից մեկը վաղ գտնված սիմվոլների խմբերի կրկնակի օգտագործումն է։ Արտահայտության վերամշակման ժամանակ ենթատողերը, որոնք գտնվել են խմբի ներսում՝ ըստ կաղապարի, պահվում են հիշողության առանձին տարածքներում և ստանում են համարներ՝ սկսած մեկից։ Կանոնավոր արտահայտություններում յուրաքանչյուր ենթատողի համապատասխանում է մի զույգ փակագիծ։ Խնբի քվանցիֆիկացիան չի ազդում պահպանվող արդյունքի վրա, այսինքն պահպանվում է միայն առաջին դեպքը։ Որպես կանոն, ապահովվում է մինչև 9 համարակալված ենթատողերը՝ 1-9 համարներով, սակայն որոշ ինտերպրետատորներ թույլ են տալիս աշխատել ավելի մեծ համարներով։ Հետեւաբար, տվյալ կանոնավոր արտահայտության սահմաններում կարելի է օգտագործել \1-ից մինչև \9 արժեքները նախօրոք գտնված ենթատողի համապատասխանությունը ստուգելու համար։
Օրինակ, (տա|տու)-\1 կանոնավոր արտահայտությունը կգտնի տա-տա կամ տու-տու տողը, բայց բաց կթողնի տա-տու տողը։ Ինչպես նաև նախօրոք գտնված ենթատողը կարելի է օգտագործել կանոնավոր արտահայտության փոխարինման համար։ Այս դեպքում փոխարինող տեքստում դրվում են այն նույն արժեքները, որոնք դրված են հենց արտահայտության մեջ։

#### Խմբավորում առանց հետադարձ կապի
Եթե խումբը օգտագործվում է միայն խմբավորման համար, և նրա արժեքը հետագայում չի օգտագործվում, ապա կարելի է օգտագործել (?:կաղապար) տեսքի խմբավորումը։ Այդպիոի խմբավորման դեպքում չի հատկացվում հիշողության առանձին տարածք և, հետևաբար, նրան չի տրվում համար։ Դա դրական է ազդում արտահայտության կատարման արագության վրա, սակայն նվազեցնում է ընթերցանելիությունը։

#### Ատոմային խմբավորում
(?>կաղապար) տեսքի ատոմային խմբավորումը, ինչպես նաև առանց հետադարձ կապի խմբավորումը, չեն ստեղծում հետադարձ կապեր։ Ի տարբերություն առանց հետադարձ կապի խմբավորման, այսպիսի խմբավորումը արգելում է տողով վերադառնալ ետ, եթե կաղապարի մի մասը արդեն հայտնաբերված է։

Ատոմային խմբավորումը կատարվում է ավելի արագ, քան առանց հետադարձ կապի խմբավորումը, և արտահայտության մնացած մասը կատարելիս խնայում է ժամանակ, քանի որ արգելվում են ցանկացած այլ տարբերակների ստուգումները խմբի ներսում, երբ մեկ տարբերակը արդեն գտնված է։ Դա շատ օգտակար է բազմաթիվ տարբերակներ ունեցող խմբերի օպտիմիզացման ժամանակ։
Սա նման է խանդոտ քվանցիֆիկացիային

#### Ձևափոխիչներ
Ձևափոխիչները ազդում են կիրառման պահից մինչև կանոնավոր արտահայտության վերջ կամ մինչև հակառակ ձևափոխիչի կիրառումը։ Որոշ ինտերպրետատորներ կարող են ընդունել ձևափոխիչը ամբողջ արտահայտության համար, այլ ոչ թե կիրառման պահից։

Ձևափոխիչների խմբերը կարելի է համատեղել մեկ խմբում՝ (?i-sm): Այդպիսի խումբը միացնում է i և անջատում s, m ռեժիմները։ Եթե ձևափոխիչները օգտագործվում են միայն խմբի ներսում, ապա տվյալ կաղապարը դրվում է խմբի ներսում ձևափոխիչից հետո, բայց «:» սիմվոլից առաջ։ Օրինակ՝ (?-i)(?i:tv)set կգտնի TVset, բայց ոչ TVSET:

#### Մեկնաբանություններ
Կանոնավոր արտահայտություններում մեկնաբանություններ ավելացնելու համար կարելի է օգտագործել մեկնաբանությունների խումբ (?#մեկնաբանություն) տեսքով։ Այդպիսի խումբը ամբողջությամբ անտեսվում է ինտերպրետատորի կողմից և չի ստուգվում տեքստ մտնելուց առաջ։ Օրինակ՝ Ա(?#այստեղ մեկնաբանություն է)Բ արտահայտությունը համապատասխանում է ԱԲ տողին։

### Դիտում առաջ և հետ
Կանոնավոր արտահայտությունների իրականացումներից շատերում կա տեքստի մի մասի որոնման միջոց։

### Փնտրում պայմանով
Կանոնավոր արտահայտությունների մի շարք իարականացումներում հնարավոր է ընտրել, թե որ ճանապարհով է կատարվելու ստուգումը կանոնավոր արտահայտության այս կամ այն մասում՝ հիմնվելով արդեն գտնված արժեքների վրա։

### Դրոշակներ
Մի շարք լեզուներում (օրինակ՝ JavaScript-ում ) կան «դրոշակներ», որոնք ընդլայնում են կանոնավոր արտահայտությունների ֆունկցիաները։ Դրոշակները դրվում են կանոնավոր արտահայտությունից հետո (դրոշակների հերթականությունը կարևոր չէ)։Օրինակ՝ /[0-9]$/**m**:
* g-համընդհանուր փնտրում 
* i-տառերի ռեգիստրը կարևոր չէ
* m-բազմատողանի փնտրում
* s-տեքստը համարվում է որպես մեկ տող։ Այս դեպքում «.» սիմվոլին համապատասխանում է ցանկացած մեկ սիմվոլ, բացառությամբ «նոր տող»-ի սիմվոլը։

## Կանոնավոր արտահայտությունների տեսակները
### POSIX-ի հիմնական կանոնավոր արտահայտություններ
(անգլերեն՝ basic regular expressions (BRE))։ UNIX-ի ավանդական կանոնավոր արտահայտություններն են։ Հիմնական կանոնավոր արտահայտությունների գրելաձև ներկայիս պահին սահմանվում է որպես հնացած POSIX-ը, բայց այն հետադարձ համատեղելիության համար մինչև այժմ լայն տարածում ունի։ Շատ UNIX-համակարգեր լռելյայն օգտագործում են այդպիսի կանոնավոր արտահայտություններ։ 
Այս տարբերակում ներառված են հետևյալ մետասիմվոլները՝
* .
* [ ]
* [^ ]
* ^ (ազդում է միայն արտահայտության սկզբում)
* $ (ազդում է միայն արտահայտության վերջում)
* *
* \{ \} — «{ }»-ի սկզբնական տեսքը
* \( \) — «( )»-ի սկզբնական տեսքը 
* \n, որտեղ n-ը 1-9 թիվ է

Առանձնահատկություններ՝
* Աստղանիշը պետք է հաջորդի արտահայտությանը։ Օրինակ՝ [xyz]*:
* «\(բլոկ\)*» արտահայտությունը պետք է համարել սխալ։ Որոշ դեպքերում, դա համապատասխանում է զրոյին կամ «բլոկ» տողի մի քանի կրկնություններին։ Մնացած դեպքերում համապատասխանում է «բլոկ*» տողին
*Սիմվոլների դասի ներսում սիմվոլների հատուկ նշանակությունը հիմնականում անտեսվում է։Հատուկ դեպքեր՝
**Որպեսզի ավելացնել «^» սիմվոլը հավաքծուի մեջ, նրան չպետք է առաջինը տեղադրել հավաքածուի մեջ։
**Որպեսզի ավելացնել «-» սիմվոլը հավաքծուի մեջ, նրան պետք է տեղադրել հավաքածուի մեջ առաջինը կամ վերջինը։ Օրինակ՝
***DNS անվան կաղապարը, որտեղ կարող են դրվել թվեր, տառեր, «-» և «.»` [-0-9a-zA-Z.]:
***ցանկացած սիմվոլ՝ «-»-ից և թվերից բացի՝ [^-0-9]:
**Որպեսզի ավելացնել «[» կամ «]» սիմվոլը հավաքծուի մեջ, նրան պետք է տեղադրել հավաքածուի մեջ առաջինը։ Օրինակ՝
***[][ab]-ին համապատասխանում է ], [, a կամ b:

### POSIX-ի ընդլայնված կանոնավոր արտահայտություններ
(անգլերեն՝ extended regular expressions (ERE)): Գրելաձևը հիմնականում նման է ավանդականին։
* Չի թույլատրվում օգտագործել «\» սիմվոլը «{», «}», «(» և «)» մետասիմվոլների համար։
* «\» սիմվոլը մետասիմվոլից առաջ փոխում է նրա հատուկ նշանակությունը (տես՝ Հատուկ սիմվոլների ներկայացումը)։
* Չի օգտագործվում տեսականորեն անկանոն կառուցվածք ունեցող «\n»-ը։
* Ավելացված են «+», «?», «|» մետասիմվոլները։

### Perl-ի հետ համընկնող կանոնավոր արտահայտություններ

Perl-համատեղելի կանոնավոր արտահայտությունները (անգլերեն՝ Perl-compatible regular expressions (PCRE)) ունեն ավելի հարուստ և, միևնույն ժամանակ, կանխատեսելի գրելաձև, քան անգամ POSIX ERE-ն։ Այդ պատճառով շատ ծրագրեր օգտագործում են հենց PCRE գրելաձևը։

## Բարդ կանոնավոր արտահայտություններ
Որոշ դեպքերում, կանոնավոր արտահայտությունները հարմար են օգտագործել տեքստային հատվածների՝ մարդկանց կողմից գրված լեզվով վերլուծության համար, որոնք կարող են պարունակել տպագրական սխալներ կամ պահանջվող բառի ոչ ստանդարտ ձևը։ Օրինակ, եթե անցկացնել հարցում, (ենթադրենք՝ web-site-ով) թե մետրոյի որ կայարանից են օգտվում մարդիկ, հնարավոր է «Երիտասարդական» կայարանը նշեն որպես՝
* Երիտասարդական
* Երիտ. կայարան
* Երիտ. կայ.
Այստեղ սովորական կանոնավոր արտահայտություններ կիրառելի չեն նախևառաջ այն պատճառով, որ մուտքային տարբերակները կարող են չհամընկնել, բայց, այնուամենայնիվ հարմար կլիներ տարբերակների կառուցվածքային փոխհարաբերությունները նկարագրել կանոնավոր արտահայտությունների միջոցով։ Օրինակ՝ այս դեպքում ցույց տալ, որ կարող են համընկնել «Երիտասարդական» և «Երիտ.», «կայարան» և «կայ.» տարբերակները։
Այս խնդիրը նման է լիարժեք տեքստային որոնմանը։ Տարբերությունն այն է, որ այստեղ կարճ հատվածը պետք է համեմատել մի շարք նմուշների հետ, իսկ լրիվ տեքստային որոնման դեպքում՝ ընդհակառակը, նմուշը սովորաբար մեկն է, իսկ տեքստի հատվածը շատ մեծ։ Այս խնդիրը նման է նաև բառային անորոշություն թույլատրման խնդրին, որը, սակայն, թույլ չի տալիս սահմանել կառուցվածքային հարաբերություններ նմուշի տարրերի միջև։

Կան մի շարք գրադարաններ, որոնք իրականացնում են կանոնավոր արտահայտությունների մեխանիզմներ՝ հնարավոր բարդ համեմատությունների դեպքում։
* TRE - C-ով գրված անվճար գրադարան, որը օգտագործում է կանոնավոր արտահայտությունների գրելաձևը, որը նման է POSIX -ին (կայուն ծրագիր)։
* FREJ - Բաց կոդով գրադարան Java-ով գրված, որը օգտագործում է Lisp-անման գրելաձև և որը զրկված է սովորական կանոնավոր արտահայտությունների մի շարք հատկություններից, բայց կենտրոնացած է տարբեր տեսակի տեքստային հատվածի ավտոմատ փոխարինողների վրա (beta-տարբերակ)։

## Իրականացում
* NFA-ն (անգլերեն՝ nondeterministic finite-state automata) օգտագործում է rollback-ի ագահ ալգորիթմը՝ ստուգելով կանոնավոր արտահայտության բոլոր հնարավոր ընդլայնումները՝ որոշակի կարգով և վերցնելով առաջին համապատասխան արժեքը։ NFA-ն կանող է գործածել ենթաարտահայտություններ և հետադարձ հղումներ։ Բայց rollback ալգորիթմի պատճառով ավանդական NFA-ն կարող է մի տեղը ստուգել մի քանի անգամ, ինչը բացասաբար է ազդում աշխատանքի արագության վրա։ Քանի որ ավանդական NFA-ն վերցնում է առաջին գտնված համապատասխանությունը, նա կարող է և չգտնել ամենաերկար համապատասխանությունը (դա պահանջում է POSIX-ի ստանդարտը և կան NFA ձևափոխիչներ, որոնք կատարում են այդ պահանջը՝ GNU sed)։ Կանոնավոր արտահայտությունների հենց այդպիսի մեխանիզմ է օգտագործվում օրինակ Perl-ում, TCL-ում, .NET-ում։ 
* DFA-ն (անգլերեն՝ deterministic finite-state automata) աշխատում է գծային ժամանակում, քանի որ չի օգտագործում rollback-ներ և ոչ մի անգամ տեքստի տվյալ հատվածը երկու անգամ չի ստուգում։ Նրանք գտնում են տարբերակներից ամենաերկարը։ DFA -ն պահում է միայն վերջնական վիճակը, հետեւաբար այն չի կարգավորում հետադարձ հղումները, ինչպես նաև չի ապահովում հստակ ընդլայնումներով կառույցները։ DFA-ն օգտագործվում է օրինակ Lex-ում, egrep-ում։

## Ծանոթագրություններ

## Գրականություն
* Ջ. Ֆրիդլ Կանոնավոր արտահայտություններ. - «Питер», 2001. — 352 с. — (Ծրագրավորողի գրադարան). — ISBN 5-318-00056-8.
* Բիլլ Սմիթ.Computing Patterns in Strings. — М.: «Вильямс», 2006. — 496 с. — ISBN 0-201-39839-7.
* Բեն Ֆորտա. 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.

## Արտաքին հղումներ
* Regular Expressions - Basics
* Կանոնավոր արտահայտությունների ուղեցույց և ռեսուրսներ (անգլերեն) -դասագիրք և շարահյուսության մանրամասն նկարագրություն օրինակներով, տարբեր ինտերպրետատորների համեմատում և այլն
* կանոնավոր արտահայտությունների կոնստրուկտոր՝ շարահյուսության կարևորմամբ (անգլերեն)
* TRE- Անվճար և տեղափոխելի գրադարան՝ կանոնավոր արտահայտությունների միջոցով բարդ համեմատություններ կատարելու համար
* FREJ (Fuzzy Regular Expressions for Java) -Անոշ կանոնավոր արտահայտություններ Java-Ի համար SourceForge.net լեզվով

Կատեգորիա:Ալգորիթմներ
Կատեգորիա:Ծրագրավորում