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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

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

  • ցանկացած տեքստում գտնել «երգ» բառը պարունակող հաջորդականությունները, օրինակ՝ «երգահան», «մեներգ»:
  • գտնել «երգ» բառը և այն փոխարինել «տաղ»-ով։
  • գտնել «երաժշտություն» բառը, որին հաջորդում է «ժողովրդական» կամ «էստրադային» բառը։
  • տեքստից հեռացնել բոլոր նախադասությունները, որոնք պարունակում են «երգ» կամ «երաժշտություն» բառերը։

Բովանդակություն

Պատմություն[խմբագրել | խմբագրել կոդը]

Կանոնավոր արտահայտությունների պատմության հիմքում ընկած են ավտոմատների տեսությունը, ֆորմալ լեզուների տեսությունը, ֆորմալ քերականության դասակարգումը՝ ըստ Չոմսկու[3]։ 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»-ի միջև։

Օրինակ Համապատասխանություն
a\.? a. կամ a
a\\\\b a\\b
a\[F\] a[F]
\Q+-*/\E +-*/

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

Ցանկացած սիմվոլ[խմբագրել | խմբագրել կոդը]

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

Սիմվոլների հավաքածու[խմբագրել | խմբագրել կոդը]

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

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

Սիմվոլ Հավասարազոր Համապատասխանություն
\d [0-9] Թվային սիմվոլ
\D [^0-9] Ոչ թվային սիմվոլ
\s [ \f\n\r\t\v] Space սիմվոլ
\S [^ \f\n\r\t\v] Ոչ Space սիմվոլ
\w [ [:word:] ] Տառային կամ թվային սիմվոլ կամ ընդգծելու սիմվոլ
\W [^[:word։]] Ցանկացած սիմվոլ, բացի տառային, թվային, ընդգծելու սիմվոլներից

Դիրքը տողի մեջ[խմբագրել | խմբագրել կոդը]

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

Ներկայացում Դիրք Օրինակ Համապատասխանություն
^ Տեքստի սկիզբ (կամ տողի՝ ?m կերպափոխիչից հետո) ^a aaa aaa
$ Տեքստի վերջ (կամ տողի՝ ?m կերպափոխիչից հետո) a$ aaa aaa
\b Բառի ծայր a\b aaa aaa
\b Բառի ծայր \ba aaa aaa
\B Բառի ոչ ծայր \Ba\B aaa aaa
\G Նախորդ բարեհաջող փնտրում \Ga aaa aaa (փնտրումը կանգնեցվել է 4-րդ դիրքում՝ այնտեղ, որտեղ «a»չի գտնվել)

Խմբի նշանակություն[խմբագրել | խմբագրել կոդը]

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

Թվարկում[խմբագրել | խմբագրել կոդը]

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

Քվանցիֆիկացիա (հաջորդականության որոնում)[խմբագրել | խմբագրել կոդը]

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

Ներկայացում Կրկնման քանակ Օրինակ Համապատասխանություն
{n} n colou{3}r colouuur
{m, n} m-n ներառյալ colou{2, 4}r colouur, colouuur, colouuuur
{m, } ոչ քիչ, քան m colou{2, }r colouur, colouuur, colouuuur և այլն
{, n} ոչ շատ, քան n colou{, 3}r color, colour, colouur, colouuur
Ներկայացում Կրկնման քանակ Հավասարազոր Օրինակ Համապատասխանություն
 ? 0 կամ 1 {0, 1} colou?r color, colour
* 0 կամ ավել {0, } colou*r color, colour, colouur և այլն
+ 1 կամ ավել {1, } colou+r colour, colouur և այլն (բայց ոչ color)

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

Ագահ և ծույլ քվանցիֆիկացիա[խմբագրել | խմբագրել կոդը]

Կանոնավոր արտահայտությունների մի քանի իրականացումներում քվանցիֆիկատորներին համապատասխանում է հնարավոր տողերից ամենաերկարը (քվանցիֆիկատորները համարվում են ագահ, անգլերեն՝ greedy)։ Դա կարող է հանդիսանալ կարևոր խնդիր։ Օրինակ՝ հաճախ ակնկալվում է, որ (<.*>) արտահայտությունը տեքստում կգտնի HTML-ի տեգերը։ Սակայն, եթե տեքստը ունի ավելի քան մեկ HTML-տեգ, ապա այս արտահայտությանը համապատասխանում է տեգերի բազմությունը պարունակող ամբողջ տողը։
< p >Վիկիպեդիան ազատ հանրագիտարան է, որտեղ ամեն ոք կարող է փոփոխել կամ ավելացնել ցանկացած հոդված։< /p > Այդ խնդիրը կարելի է լուծել երկու եղանակով։

  1. Դիտարկել սիմվոլները, որոնք չեն համապատասխանում ցանկալի օրինակին (<[^>]*> վերը նշված դեպքի համար)։
  2. Սահմանել քվանցիֆիկատորը որպես ծույլ (անգլերեն՝ lazy)։ Շատ իրականացումներ թույլ են տալիս դա անել՝ քվանցիֆիկատորից հետո ավելացնելով ? սիմվոլը։

Ծույլ քվանցիֆիկատորների օգտագործումը կարող է հանգեցնել հակառակ խնդրին՝ երբ արտահայտությանը համապատասխանում է շատ կարճ, մասնավորապես, դատարկ տող։

Ագահ Ծույլ
* *?
+ +?
{n, } {n, }?

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

Ագահ և ծույլ արտահայտությունների օգտագործման օրինակներ
(<.*>) արտահայտությունը համապատասխանում է HTML-ի մի քանի տեգ պարունակող տողի ամբողջությամբ։

< p >Վիկիպեդիան ազատ հանրագիտարան է, որտեղ ամեն ոք կարող է փոփոխել կամ ավելացնել ցանկացած հոդված։< /p >
Որպեսզի տարբերել առանձին տեգերը, կարելի է օգտագործել այդ արտահայտության ծույլ տարբերակը՝ (<.*?>)։
Նրան համապատասխանում է ոչ թե վերևում նշված ամբողջ տողը, այլ առանձին տեգերը։
< p >Վիկիպեդիան — ազատ հանրագիտարան է, որտեղ ամեն ոք կարող է փոփոխել կամ ավելացնել ցանկացած հոդված։< /p >

Խանդոտ քվանցիֆիկացիա[խմբագրել | խմբագրել կոդը]

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

aaaaa տողի մեջ (a+a+)+a արտահայտությունը փնտրելու համար

ինտերպրետատորը կկատարի հետևյալ քայլերը՝

  1. aaaaa
  2. aaaa
  3. aaaaa
  4. aaa
  5. aaaaa
  6. aaaa
  7. aaaaa - և միայն այստեղ ստուգելով բոլոր վերադարձի կետերը՝ կդադարեցնի։

Խանդոտ քվանցիֆիկատորի օգտագործման դեպքում կկատարվի ալգորիթմի միայն առաջին քայլը։

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

Ագահ Խանդոտ
* *+
 ?  ?+
+ ++
{n, } {n, }+
Օրինակ Համապատասխանություն
ab(xa)*+a abxaabxaa, բայց ոչ abxaabxaa, քանի որ a տառը արդեն զբաղված է։

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

Խմբավորում[խմբագրել | խմբագրել կոդը]

Հետադարձ կապ[խմբագրել | խմբագրել կոդը]

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

Խմբավորում առանց հետադարձ կապի[խմբագրել | խմբագրել կոդը]

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

Ատոմային խմբավորում[խմբագրել | խմբագրել կոդը]

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

Օրինակ Համապատասխանություն Ստեղծվող խումբ
a(bc|b|x)cc abccaxcc, abccaxcc abccaxcc, abccaxcc
a(?:bc|b|x)cc abccaxcc, abccaxcc չկա
a(?>bc|b|x)cc abccaxcc , բայց ոչ abccaxcc ՝ x-ը գտնված է, մնացածը անտեսվում է չկա
a(?>x*)xa չի գտնվի axxxa ՝ բոլոր x-երը զբաղված են և խմբի ներսում ետ դարձ չկա չկա

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

Ձևափոխիչներ[խմբագրել | խմբագրել կոդը]

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

Ձևաչափ Նկարագրություն
(?i) Արտահայտությանը դարձնում է ոչ զգայուն սիմվոլների ռեգիստրի նկատմամբ։
(?-i) Արտահայտությանը դարձնում է զգայուն սիմվոլների ռեգիստրի նկատմամբ։
(?m) ^ և $ սիմվոլները առաջացնում են համապատասխանություն միայն «նոր տող» սիմվոլից առաջ և հետո։
(?-m) ^ և $ սիմվոլները առաջացնում են համապատասխանություն միայն տեքստի սկզբում և վերջում։
(?x) Կանոնավոր արտահայտության մասերի միջև հաշվի չի առնում բացատների առկայությունը և թույլ է տալիս օգտագործել «#» սիմվոլը մեկնաբանությունների համար
(?-x) Կանոնավոր արտահայտության մասերի միջև հաշվի է առնում բացատների առկայությունը և թույլ է տալիս օգտագործել «#»սիմվոլը մեկնաբանությունների համար

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

Մեկնաբանություններ[խմբագրել | խմբագրել կոդը]

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

Դիտում առաջ և հետ[խմբագրել | խմբագրել կոդը]

Կանոնավոր արտահայտությունների իրականացումներից շատերում կա տեքստի մի մասի որոնման միջոց:

Ներկայացում Դիտման տեսակ Օրինակ Համապատասխանություն
(?=կաղապար) Դրական առաջդիտում Լյուդովիկ(?=XVI) ԼյուդովիկXV, ԼյուդովիկXVI, ԼյուդովիկXVIII, ԼյուդովիկLXVII, ԼյուդովիկXXL
(?!կաղապար) Բացասական առաջդիտում Լյուդովիկ(?!XVI) ԼյուդովիկXV, ԼյուդովիկXVI, ԼյուդովիկXVIII, ԼյուդովիկLXVII, ԼյուդովիկXXL
(?<=կաղապար) Դրական հետդիտում (?<=Սերգեյ) Իվանով Սերգեյ Իվանով, Իգոր Իվանով
(?<!կաղապար) Բացասական հետդիտում (?<!Սերգեյ) Իվանով Սերգեյ Իվանով, Իգոր Իվանով

Փնտրում պայմանով[խմբագրել | խմբագրել կոդը]

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

Ներկայացում Բացատրություն Օրինակ Համապատասխան
(?(?=եթե )ապա |հակառակ դեպքում) Եթե գործողությունը հաջող է դիտարկվել, ապա կատարվում է «ապա»-ի

մասը, համառակ դեպքում՝ «համառակ դեպքում»-ի մասը։
Արտահայտության մեջ կարող են օգտագործվել չորս դիտարկման
գործողություններից ցանկացածը։

(?(?<=ա)մ|պ) մամ, պապ
(?(n)ապա|հակառակ դեպքում) Եթե n-րդ խումբը վերադարձրել է որևէ արժեք, ապա պայմանով

փնտրումը կատարվում է «ապա» կաղապարով, հակառակ դեպքում՝
«հակառակ դեպքում» կաղապարով։

(ա)?(?(1)մ|պ) մամ, պապ

Դրոշակներ[խմբագրել | խմբագրել կոդը]

Մի շարք լեզուներում (օրինակ՝ 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»-ը։
  • Ավելացված են «+», «?», «|» մետասիմվոլները։

Տես նաև POSIX սիմվոլների դաս

Perl-ի հետ համընկնող կանոնավոր արտահայտություններ[խմբագրել | խմբագրել կոդը]

    1rightarrow.png Հիմնական հոդված՝ PCRE

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-ում։

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. docs.oracle.com
  2. MSDN
  3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Синтаксический анализ. — Мир. — М., 1978. — Т. 2.

Գրականություն[խմբագրել | խմբագրել կոդը]

  • Ջ. Ֆրիդլ Կանոնավոր արտահայտություններ. - «Питер», 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.

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]