Preskočiť na obsah

Regulárny výraz

z Wikipédie, slobodnej encyklopédie
[0-9a-fA-F]+(, *[0-9a-fA-F]+)*
Regulárny výraz, popisujúci čiarkou oddelený zoznam hexadecimálnych čísel z príkladov nižšie a jeho syntaktický diagram

Regulárny výraz[1] (skrátene aj regexp[1], regex[2] alebo RE z angl. regular expression) 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[pozn. 1] 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

[upraviť | upraviť zdroj]

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.[3][4]

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.[5] 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.[6]

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

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.[10][11]

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

[upraviť | upraviť zdroj]

Medzi základné spôsoby využitia regulárnych výrazov patrí:

  1. kontrola, či vstupný text vyhovuje danému regulárnemu výrazu[12]
  2. rozdelenie vstupného textu na časti, oddelené separátorom, vyhovujúcim danému regulárnemu výrazu[13]
  3. vyhľadávanie vo vstupnom texte[14]
    • 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)
  4. 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[15]
      • 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[16]

Aplikácie

[upraviť | upraviť zdroj]

Medzi konkrétne aplikácie regulárnych výrazov patrí napr.:

  • validácia a normalizácia vstupu od používateľa[17]
  • extrakcia štruktúrovaných údajov z textu (napr. data scraping, web scraping)[18][19]
  • štruktúrované náhrady v texte, v markupe, v zdrojových kódoch[17][20]
  • filtrovanie údajov (riadkov súboru/výstupu, názvov súborov, položiek v databáze, položiek logov, netextových údajov)[21]
  • transformácia údajov
  • tvorba systémov zvýrazňovania syntaxe[22]
  • tvorba jednoduchších parserov a kompilátorov, resp. ich častí – typicky lexikálna analýza (tokenizácia)[23][24]

Syntax

[upraviť | upraviť zdroj]

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

Väčšina praktických implementácií regulárnych výrazov (POSIX[25], grep[21], sed[20], Perl[26], PCRE[27], Java[2], JavaScript[28], .NET[29]) 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 [a-dxy -] 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 [^a-dxy -] 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 [a-c][01] 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

[upraviť | upraviť zdroj]

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[26] a následne prevzatých do knižnice PCRE[27] a ďalších odvodených implementácií. POSIX regulárne výrazy používajú pre pomenované triedy inú syntax.[25]

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

[upraviť | upraviť zdroj]
  • 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

[upraviť | upraviť zdroj]
  1. ↑ S 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.

Referencie

[upraviť | upraviť zdroj]
  1. ↑ a b c Rovan 2013, s. 28
  2. ↑ a b Pattern (Java Platform SE 8 ) [online]. docs.oracle.com, [cit. 2021-10-08]. Dostupné online.
  3. ↑ KLEENE, Stephen Cole. Representation of Events in Nerve Nets and Finite Automata [online]. Princeton University Press, 1951-12-15, [cit. 2021-10-06]. Dostupné online.
  4. ↑ LEUNG, Hing. Regular Languages and Finite Automata [online]. maa.org, 2013, [cit. 2021-10-06]. Dostupné online. [nefunkčný odkaz]
  5. ↑ RITCHIE, D. M.; THOMPSON, K. L.. MM-70-1373-3 : [QED Text Editor] [online]. Bell Laboratories, 1970-06-22, [cit. 2021-10-10]. Dostupné online. Archivované 2006-06-20 z originálu.
  6. ↑ US3568156A : Text matching algorithm [online]. Google Patents, 1971-03-02, [cit. 2021-10-10]. Dostupné online.
  7. ↑ About grep, a 40 year old UNIX command [online]. developpaper.com, 2019-11-10, [cit. 2021-10-10]. Dostupné online. Archivované 2021-10-24 z originálu.
  8. ↑ PEMENT, Eric. Frequently-Asked Questions about sed, the stream editor : What is sed? [online]. sed.sourceforge.net, [cit. 2021-10-12]. Dostupné online. Archivované 2018-06-27 z originálu.
  9. ↑ CASSEL, David. Brian Kernighan Remembers the Origins of ‘grep’ [online]. thenewstack.io, 2018-07-22, [cit. 2021-10-12]. Dostupné online.
  10. ↑ HIETANIEMI, Jarkko. perlhist – the Perl history records [online]. perldoc.perl.org, [cit. 2021-10-12]. Dostupné online.
  11. ↑ Perl. In: RAYMOND, Eric Steven. The Art of Unix Programming : Language Evaluations [online]. catb.org, 2003, [cit. 2021-10-12]. Dostupné online.
  12. ↑ Java Platform SE 8 : Class String : public boolean matches(String regex) [online]. docs.oracle.com, [cit. 2021-10-08]. Dostupné online.
  13. ↑ Java Platform SE 8 : Class String : public String[] split(String regex) [online]. docs.oracle.com, [cit. 2021-10-08]. Dostupné online.
  14. ↑ Java Platform SE 8 : Class Matcher [online]. docs.oracle.com, [cit. 2021-10-08]. Dostupné online.
  15. ↑ Java Platform SE 8 : Class String : public String replaceAll(String regex, String replacement) [online]. docs.oracle.com, [cit. 2021-10-08]. Dostupné online.
  16. ↑ Java Platform SE 9 : Class Matcher : public String replaceAll​(Function<MatchResult,String> replacer) [online]. docs.oracle.com, [cit. 2021-10-08]. Dostupné online.
  17. ↑ a b .NET regular expressions [online]. docs.microsoft.com, 2020-06-30, [cit. 2021-10-10]. Dostupné online.
  18. ↑ KOEHRSEN, Will. Web Scraping, Regular Expressions, and Data Visualization: Doing it all in Python [online]. tools.freeside.sk, 2018-04-28, [cit. 2021-10-10]. Dostupné online.
  19. ↑ Regex match parser [online]. webscraper.io, [cit. 2021-10-10]. Dostupné online.
  20. ↑ a b sed, a stream editor : Regular Expressions: selecting text [online]. Free Software Foundation, [cit. 2021-10-08]. Dostupné online.
  21. ↑ a b GNU Grep 3.7 : Regular Expressions [online]. Free Software Foundation, [cit. 2021-10-08]. Dostupné online.
  22. ↑ NEdit 5.5 : Highlighting Patterns [online]. edoras.sdsu.edu, [cit. 2021-10-10]. Dostupné online.
  23. ↑ HalaBadr : Compiler Project [online]. github.com, [cit. 2021-10-10]. Dostupné online.
  24. ↑ SRB, Martin. Flex – fast lexical analyzer generator [online]. root.cz, 2001-05-11, [cit. 2021-10-10]. Dostupné online.
  25. ↑ a b IEEE Std 1003.1-2017 : Regular Expressions [online]. pubs.opengroup.org, [cit. 2021-10-08]. Dostupné online.
  26. ↑ a b Perl regular expressions [online]. perldoc.perl.org, [cit. 2021-10-08]. Dostupné online.
  27. ↑ a b pcrepattern man page [online]. pcre.org, [cit. 2021-10-08]. Dostupné online.
  28. ↑ Regular expressions [online]. developer.mozilla.org, [cit. 2021-10-08]. Dostupné online.
  29. ↑ .NET : Regular Expression Language - Quick Reference [online]. docs.microsoft.com, 2021-03-02, [cit. 2021-10-08]. Dostupné online.

Literatúra

[upraviť | upraviť zdroj]
  • SATRAPA, Pavel. Regulární výrazy. Liberec : Technická univerzita v Liberci, 2000. 26 s. Dostupné online. (po česky)
  • FRIEDL, Jeffrey E. F. Mastering Regular Expressions. 3. vyd. Sebastopol : O'Reilly, 2006. 515 s. ISBN 978-0-596-52812-6. (po anglicky)
  • ROVAN, Branislav; FORIŠEK, Michal. Formálne jazyky a automaty : skriptá. Bratislava : Katedra informatiky FMFI UK, 2013. 125 s. Dostupné online. Kapitola 2.10 Regulárne výrazy, s. 28 – 29.

Iné projekty

[upraviť | upraviť zdroj]

Externé odkazy

[upraviť | upraviť zdroj]
Zdroj: „https://sk.wikipedia.org/w/index.php?title=Regulárny_výraz&oldid=7897569“