Regulárny výraz

Regulárny výraz (skrátene aj regexp, regex alebo RE z ) je textový reťazec, obsahujúci vyhľadávací vzor, ktorý popisuje celú množinu reťazcov (formálny jazyk), na základe určitých syntaktických pravidiel. Predstavuje úsporný zápis regulárnej gramatiky z teórie formálnych jazykov, regulárnymi výrazmiS pôvodnou syntaxou v zmysle sekcie Syntax. Niektoré výrazové prostriedky, doplnené v neskorších implementáciách (ako sú rôzne druhy kontextových podmienok, rekurentné podvýrazy, spätné odkazy na nájdený podvýraz), zvyšujú expresivitu výrazov nad triedu regulárnych jazykov, časť dokonca až nad triedu bezkontextových jazykov. Napriek tomu sa na takéto (silnejšie) výrazy stále v praxi odkazuje ako na regulárne výrazy, resp. v teoretických prácach ako na regexy/regexpy, na odlíšenie od regulárnych výrazov v pôvodnom zmysle. sú teda popísateľné práve regulárne jazyky, t. j. jazyky, akceptovateľné konečnostavovým automatom.

Regulárne výrazy sú používané v mnohých textových editoroch a nástrojoch na hľadanie a manipuláciu s textom podľa vzorov. Mnoho programovacích jazykov podporuje regulárne výrazy na prácu s reťazcami. Napríklad Perl a Tcl majú zabudovanú silnú podporu pre regulárne výrazy priamo v svojej syntaxi. Implementácie regulárnych výrazov, odvodených od Perl syntaxe existujú aj pre jazyky C, C++, C#, Java, JavaScript, Python, PHP a ďalšie. Množstvo nástrojov príkazového riadku (vrátane filtra grep a dávkového editora sed) poskytovaných pôvodne unixovými operačnými systémami, z ktorých sa neskôr ďalej rozšírili, masívne využíva regulárne výrazy.

 Dejiny 
Vznik pojmu a konceptu regulárnych výrazov sa datuje do roku 1951, kedy americký matematik Stephen Cole Kleene v rámci práce, venovanej McCulloch-Pittsovým neurónovým sieťam, formálne opísal regulárne jazyky (ktoré v práci nazýval regulárne udalosti, angl. regular events) a dokázal ekvivalenciu triedy jazykov, popísateľných regulárnymi výrazmi s triedou jazykov, akceptovateľných konečnostavovými automatmi.

V druhej polovici 60. rokov pracoval americký informatik a spolutvorca operačného systému Unix Ken Thompson na reimplementácii riadkovo orientovaného textového editora QED (predchodca editorov ed, vi a vim) pre viacpoužívateľský operačný systém so zdieľaním času CTSS, v rámci ktorej do editora zapracoval aj podporu regulárnych výrazov. Šlo o jedno z prvých využití regulárnych výrazov v softvéri pre širšiu používateľskú základňu. V roku 1971 získala spoločnosť Bell Labs na Thompsonov algoritmus hľadania vzorov v texte prostredníctvom regulárnych výrazov aj patent, podaný ešte v roku 1967.

V roku 1971 potom s podporou regulárnych výrazov nasledoval editor ed (Ken Thompson), v roku 1973 filter grep (Ken Thompson) a v roku 1974 neinteraktívny dávkový editor sed (Lee McMahon), všetko rovnako v rámci Bell Labs, úzko previazené so vznikom Unixu.

V roku 1986 vyvinul kanadský programátor Henry Spencer knižnicu regex, ktorá poslúžila ako základ pre podporu regulárnych výrazov vo vznikajúcom skriptovacom jazyku Perl (Larry Wall, 1988). Popularita Perlu prudko vzrástla v 90. rokoch, počnúc verziou 5.0, na čom sa významnou mierou podpísala aj podpora regulárnych výrazov s vyššou expresivitou, než poskytovali iné dobové jazyky a nástroje.Perl. In: 

V roku 1997 vznikla multiplatformná knižnica PCRE (vyvinutá pôvodne pre mailový server Exim), umožňujúca integrovať podporu Perl-kompatibilných regulárnych výrazov do softvéru tretích strán. Knižnicu využili napr. webový server Apache, webový skriptovací jazyk PHP a ďalšie významné projekty, čo spolu s popularitou Perlu prispelo k tomu, že sa Perl-kompatibilná syntax regulárnych výrazov stala de facto štandardnou aj pre ich mnohé ďalšie implementácie v programovacích jazykoch a iných softvérových projektoch.

 Využitie 
Medzi základné spôsoby využitia regulárnych výrazov patrí:
 kontrola, či vstupný text vyhovuje danému regulárnemu výrazu
 rozdelenie vstupného textu na časti, oddelené separátorom, vyhovujúcim danému regulárnemu výrazu
 vyhľadávanie vo vstupnom texte
 zistenie pozícií vo vstupnom texte, kde sa nachádzajú výskyty, vyhovujúce danému regulárnemu výrazu
 výber všetkých výskytov, vyhovujúcich danému regulárnemu výrazu (s možnosťou zachytenia fragmentov, zodpovedajúcich uzátvorkovaným skupinám vo výraze)
 manipulácia s textom
 náhrada výskytov, vyhovujúcich danému regulárnemu výrazu; pričom nahrádzať je v praxi možné: 
 fixným textom
 nahrádzacím výrazom, kombinujúcim fixný text s odvolávkami na fragmenty, zachytené uzátvorkovanými skupinami v regulárnom výraze
 callback funkciou, ktorá ako vstup dostane nájdený výskyt, vyhovujúci regulárnemu výrazu (vrátane prípadných fragmentov pre uzátvorkované skupiny), zrealizuje výpočet podľa potrieb a ako výstup vráti nový reťazec

 Aplikácie 
Medzi konkrétne aplikácie regulárnych výrazov patrí napr.:
 validácia a normalizácia vstupu od používateľa
 extrakcia štruktúrovaných údajov z textu (napr. data scraping, web scraping)
 štruktúrované náhrady v texte, v markupe, v zdrojových kódoch
 filtrovanie údajov (riadkov súboru/výstupu, názvov súborov, položiek v databáze, položiek logov, netextových údajov)
 transformácia údajov
 tvorba systémov zvýrazňovania syntaxe
 tvorba jednoduchších parserov a kompilátorov, resp. ich častí – typicky lexikálna analýza (tokenizácia)

 Syntax 
Pre formálnu, matematickú definíciu, využívanú v prácach z oblasti teórie formálnych jazykov, pozri napr. zdroj .

Väčšina praktických implementácií regulárnych výrazov (POSIX, grep, sed, Perl, PCRE, Java, JavaScript, .NET) vychádza z nasledovnej syntaxe:
 Jednoznakové atómy  x Literálny znak (ľubovoľný znak, mimo vyhradených metaznakov: . \ + * ? [ ^ ] $ ( ) { } | a prípadných ďalších, implementačne špecifických) popisuje práve len doslovný výskyt tohoto konkrétneho znaku. Napr. výrazu A tak vyhovuje jedine reťazec „A“ (v režime bez rozlišovania malých/veľkých písmen aj „a“).  \x Opačné lomítko umožňuje zapísať doslovný výskyt vyhradeného metaznaku. Napr. výrazu \* tak vyhovuje jedine reťazec „*“ a výrazu \\ reťazec „\“.  . Bodka indikuje ľubovoľný jeden znak (pričom podľa konkrétneho nastavenia sa môže alebo nemusí vzťahovať aj na riadiaci kód prechodu na nový riadok). Napr. výrazu Ad.m vyhovujú reťazce „Adam“, „AdXm“, „Ad9m“, „Ad!m“ a ďalšie.  [trieda] Hranaté zátvorky indikujú jeden ľubovoľný znak z triedy, špecifikovanej obsahom zátvoriek. Trieda môže byť špecifikovaná vymenovaním konkrétnych znakov, uvedením rozsahu znakov (so symbolom spojovníka, „-“) a kombináciou týchto možností (jednotlivé implementácie potom ponúkajú aj ďalšie praktické možnosti špecifikácie). Napr. výrazu  vyhovujú reťazce „a“, „b“, „c“, „d“, „x“, „y“, „ “, „-“.  [^trieda] Hranaté zátvorky s obsahom, začínajúcim znakom striešky (^) indikujú jeden ľubovoľný znak, nepatriaci do triedy, špecifikovanej obsahom zátvoriek. Napr. výrazu  vyhovuje ľubovoľný jednoznakový reťazec, okrem reťazcov „a“, „b“, „c“, „d“, „x“, „y“, „ “, „-“. Zreťazenie  AB Ak A a B sú regulárne výrazy, tak výrazu AB vyhovujú reťazce, získané spojením (zreťazením) ľubovoľného reťazca, vyhovujúceho výrazu A s ľubovoľným reťazcom, vyhovujúcim výrazu B. Napr. výrazu Adam (zreťazenie jednoznakových literálnych atómov) tak vyhovuje jedine reťazec „Adam“. Výrazu  vyhovujú reťazce „a0“, „a1“, „b0“, „b1“, „c0“ a „c1“. Alternatívy (vetvenie)  | Zvislá čiara oddeľuje alternatívy (vetvy), predstavuje ekvivalent logického „alebo“. Výrazu Adam|Eva vyhovujú reťazce „Adam“ aj „Eva“. Zoskupovanie  () Jednoduché zátvorky vymedzujú rámec (scope), umožňujú tvorbu podvýrazov (a následné aplikovanie kvantifikátorov na celý podvýraz) a definujú skupiny, zachytávajúce podreťazce v nájdených výskytoch. Napr. výrazu Sol(ivar|ana|aris) vyhovujú reťazce „Solivar“, „Solana“ a „Solaris“. Kvantifikácia   Kvantifikátory sa vzťahujú na predchádzajúci atóm, ktorým môže byť buď jednoznakový atóm alebo podvýraz v jednoduchých zátvorkách. Hľadajú štandardne maximálny možný vyhovujúci počet výskytov atómu (tzv. „pažravý“, angl. greedy režim). Niektoré implementácie umožňujú voľbu opačného, non-greedy režimu, typicky buď príznakom pri volaní funkcie, pracujúcej s regulárnym výrazom, alebo uvedením znaku otáznik (?) za konkrétny kvantifikátor, ktorý má hľadať minimálny počet výskytov namiesto maximálneho. ? Otáznik indikuje žiaden alebo jeden výskyt predchádzajúceho atómu. Napr. ab?c popisuje reťazce „ac“ a „abc“.  Ďalšou funkciou je, pri doplnení za iný kvantifikátor, voľba non-greedy režimu, viď vyššie. * Hviezdička (Kleeneho operátor) indikuje nula alebo viac výskytov predchádzajúceho atómu. Napr. ab*c popisuje „ac“, „abc“, „abbc“, „abbbc“, atď. + Plus indikuje jeden alebo viac výskytov predchádzajúceho atómu. Napr. ab+c popisuje „abc“, „abbc“, „abbbc“, atď.; nie  však reťazec „ac“. {n} Exaktne n výskytov predchádzajúceho atómu. Napr. mu(ha){3} popisuje reťazec „muhahaha“. {min,} Najmenej min výskytov predchádzajúceho atómu. Napr. mu(ha){2,} popisuje reťazce „muhaha“, „muhahaha“, „muhahahaha“, atď. {min,max} Najmenej min, najviac max výskytov predchádzajúceho atómu. Napr. mu(ha){2,4} popisuje reťazce „muhaha“, „muhahaha“ a „muhahahaha“. Kotviace (pozičné) znaky  ^ Strieška kotví na začiatok reťazca (prípadne riadku, pri riadkovom spracovaní). Bez použitia tohoto kotviaceho znaku vyhovie výrazu výskyt, začínajúci od ľubovoľnej pozície vo vstupnom texte. $ Dolár kotví na koniec reťazca (prípadne riadku, pri riadkovom spracovaní). Bez použitia tohoto kotviaceho znaku vyhovie výrazu výskyt, končiaci na ľubovoľnej pozícii vo vstupnom texte.

 Triedy znakov 
Pre zjednodušenie špecifikácie tried znakov v regulárnych výrazoch existujú vo väčšine implementácií aj preddefinované pomenované triedy. V nasledujúcej tabuľke je základný zoznam a stručný popis tried, pochádzajúcich pôvodne z Perlu a následne prevzatých do knižnice PCRE a ďalších odvodených implementácií. POSIX regulárne výrazy používajú pre pomenované triedy inú syntax.
+ Triedy resp. množiny znakov Trieda znakov Význam \w Znak, tvoriaci slovo (angl. word char). Písmeno, číslica alebo podčiarnik, v prípade ASCII znak z množiny [a-zA-Z_0-9], v prípade Unicode rozsiahlejšia sada znakov \W Iný znak než písmeno, číslica alebo podčiarnik (non-word char) \s „Biely znak“ (whitespace), čiže znak, ktorý v informatike predstavuje biele miesto, nie je priamo viditeľný. Príkladom môže byť napr. znak medzery, znak tabulátora alebo prípadne iného riadiaceho znaku z ASCII.  \S Iný než „biely znak“ (non-whitespace) \d Číslica (decimal digit) čiže znaky 0 až 9 \D Iný znak než číslica (non-decimal digit) \t Znak tabulátora \r Carriage return je špeciálnym riadiacim znakom slúžiacim na návrat kurzora na začiatok riadku \v Vertical tab \f Form feed \n Nový riadok (newline) \e Escape

 Príklady 
 So(ň|v)a popisuje reťazce „Soňa“ a „Sova“.
 Ba*f popisuje reťazce „Bf“, „Baf“, „Baaf“, „Baaaf“, atď.
 \d{3} ?\d{2} popisuje formát PSČ – postupnosť troch číslic, nepovinnú medzeru a dve číslice, napr. „845 08“, „97644“ a pod.
 <[^>]*> popisuje (zjednodušene) tag v jazyku HTML – ľubovoľný text, uzavretý medzi ostré zátvorky.
 [0-9a-fA-F]+(, *[0-9a-fA-F]+)* popisuje zoznam hexadecimálnych čísel, oddelených čiarkami a nepovinnými medzerami, napr. „10C, 61, 75, 263A, 0D, 0A“.
 ((a*b)(a*b))*a* popisuje slová z abecedy {a, b}, obsahujúce párny počet b, napr. „baaabbaaaaaba“.

 Poznámky 

 Referencie 

 Literatúra 




 Iné projekty 

 Externé odkazy 
 Regulární výrazy – publikácia Pavla Satrapu, pôvodne seriál pre server Root.cz
 Regex101 – online nástroj na testovanie regulárnych výrazov s podporou viacerých syntaxí
 Regexper – vizualizátor regulárnych výrazov do podoby syntaktických diagramov
 Syntax regulárnych výrazov: POSIX, grep, sed, Perl, PCRE, Java, JavaScript, .NET, Python, PHP

Kategória:Formálne jazyky
Kategória:Programovanie
Kategória:Počítačová veda
Kategória:Matematická logika
Kategória:Hľadanie vzorov
Kategória:Vzniklo v 1951