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ýrazmi 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.

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:

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.

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

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