Regulární výraz

Z Multimediaexpo.cz

Regulární výraz (zkracováno na regexp, regex či jen RE podle anglického regular expression) je řetězec popisující celou množinu řetězců, konkrétně regulární jazyk. Představil je americký matematik Steven Kleene.[1] Regulární výrazy mohou pro hledání podporovat i jiné programy, například propracovanější textové editory nebo souborové manažery. Nejčastěji jsou ale podporovány v počítačových programech a skriptovacích jazycích formou externí knihovny nebo sady funkcí. Nejčastější využití je:

  • vyhledávání textu
    • buď prosté zjištění, zdali vstupní text vyhovuje zadanému regulárnímu výrazu, nebo
    • zjištění offsetu (pozice) ve vstupním textu, kde shoda s regulárním výrazem začíná
  • manipulace s textem
    • záměna textu v jednom z podvýrazů regexu
    • extrakce všech shod s regulárním výrazem do předané proměnné

Pokud chce uživatel v textu vyhledat nějaký řetězec, který nezná přesně nebo který může mít více podob, může zadat regulární výraz, který postihne všechny požadované varianty. Program tak nalezne všechny části textu, které danému výrazu odpovídají. Regulární výraz se skládá z literálů textu, které se mají shodovat, a speciálních znaků, které nejsou součástí hledaného textu, sloužících pro popis alternativ, množin, počtů výskytů a přepínačů.

Obsah

Formální definice

Formálně je regulární výraz definován následujícím způsobem:

  1. a je regulární výraz pro libovolný literál (znak abecedy, popř. prázdný symbol ε) a, popisující právě text a.
  2. Pokud A a B jsou regulární výrazy, je AB regulární výraz, popisující zřetězení textů popsaných výrazy A a B.
  3. Pokud A a B jsou regulární výrazy, je A + B regulární výraz, popisující buď text popsaný výrazem A, nebo text, popsaný výrazem B.
  4. Pokud A je regulární výraz, pak A* je regulární výraz, popisující libovolný počet opakování (včetně žádného opakování) textů popsaných výrazem A.
  5. Pokud A je regulární výraz, je (A) regulární výraz popisující stejný jazyk. (Závorky slouží pouze pro vyjasnění priorit.)

Tato definice dostačuje pro popis libovolného regulárního jazyka.

Prakticky používané syntaxe

V praxi se používají obvykle rozšířené definice regulárních jazyků, které umožňují běžné konstrukce zapsat jednodušším způsobem (ale schopnosti takto rozšířených výrazů se od základní definice neliší). V běžných syntaxích se zpravidla objevují následující konstrukce:

  • Místo znaku + (plus) se pro alternativy obvykle používá | (svislítko neboli pajpa).
  • Kulaté závorky mají funkci substituce za dílčí regulární výraz (například regulární výraz (a1|a2)(b1|b2) zachycuje případy a1 nebo a2 následované b1 nebo b2)
  • Jeden z uvedených znaků: zápis [a-z0-9] znamená libovolný znak v rozsahu a–z, 0–9.
  • Jeden z neuvedených znaků: zápis [^a-z0-9] znamená libovolný znak kromě znaků v rozsahu a–z, 0–9. Jindy se místo stříšky používá znak ! (vykřičník).
  • Libovolný znak: symbol . (tečka) znamená libovolný znak. Pozn.: podle konkrétního nastavení se nemusí vztahovat na nový řádek.
  • Pouze na začátku řetězce: zápis ^nějakývýraz popisuje pouze takové řetězce nějakývýraz, které se nachází na začátku řetězce.
  • Pouze na konci řetězce: zápis nějakývýraz$ popisuje pouze takové řetězce nějakývýraz, které se nachází na konci řetězce.
  • Nepovinná část: zápis xy? popisuje znak x, který může, ale nemusí, být následován znakem y. Sémanticky odpovídá „0 nebo 1 výskyt“.
  • Libovolný počet opakování: x* (0 až ∞ výskytů x)
  • Libovolný počet opakování, ale nejméně jednou: x+ vyžaduje alespoň jeden výskyt znaku x.
  • Zadaný počet opakování: zápis x{3,5} popisuje troj- až pěti-násobné opakování znaku x.
  • Je-li potřeba zadat znak, který má zde speciální význam, dá se tento znak escapovat zpětným lomítkem – \.
  • Definované množiny znaků: některé speciální skupiny znaků mají zkratkový zápis, např. \d pro libovolnou desítkovou číslici, \s pro bílý znak apod.
  • Různá rozšíření (nemusejí být standardní), například [[:<:]]Wikipedie[[:>:]] (pro MySQL) hledá výraz Wikipedie jako celé slovo (tj. oddělené mezerami, interpunkcí či jinými znaky, které nejsou součástí slova).
  • Celý regulární výraz podle PCRE (viz níže) je navíc oddělen znakem (nejčastěji dopředným lomítkem), které jej též uzavírá a za kterým následují „přepínače“. Například přepínač i vypíná citlivost na velká/malá písmena.

Mezi nejznámější používané syntaxe zápisu regulárních výrazů patří POSIX Regular Expressions a Perl Compatible Regular Expressions (PCRE), odvozená z definice jazyka Perl. Syntaxe PCRE (případně s malými odlišnostmi) se používá mimo jiné v PHP (funkce preg_ nebo (nyní již zastaralé) funkce ereg(i)_), Pythonu či JavaScriptu.

Regulární výrazy popisující neregulární jazyky

V mnoha dnešních nástrojích obsahuje syntaxe „regulárních výrazů“ prostředky, kterými lze popsat jazyky silnější než regulární. Např. prostřednictvím tzv. zpětných odkazů v PCRE lze zapsat výraz (.*)\1, který označuje dvojí opakování libovolného textu (např. „masomaso“ či „123123“). Jazyk všech takových opakování však není regulární, není dokonce ani bezkontextový; běžné nástroje tak umožňují zapsat NP-těžké jazyky (a vyhledávat podle nich). To vede k jistému zmatení pojmů, neboť „regulární výraz“ v běžném použití označuje obecnější pojem než „regulární výraz“ ve smyslu teorie formálních jazyků. Pro jednoznačnost se někdy tyto „rozšířené regulární výrazy“ označují jinak, např. výhradně výrazem „regex“.[2][3]

Příklady

  • Pe(t|p)a popisuje řetězce „Peta“ a „Pepa“.
  • Ba*f popisuje řetězce „Bf“, „Baf“, „Baaf“, „Baaaf“ atd.
  • \d{3} \d{2} popisuje posloupnost tří číslic, mezeru a dvě číslice – formát PSČ.
  • <[^>]*> popisuje tag v jazyce HTML – libovolný text uzavřený mezi špičaté závorky (poznámka: tento výraz je zjednodušený, ve skutečném HTML situaci komplikují řetězce v uvozovkách).
  • [0-9a-fA-F]+(, ?[0-9a-fA-F]+)* popisuje seznam hexadecimálních čísel, oddělených čárkami a nepovinnými mezerami.

Reference

  1. ↑ http://phpfashion.com/regularni-korektura-intervalu-cz
  2. ↑ Ian Graham: Kleene Would Be Shocked – Redrawing the Link Between Theory and Modern Regex Engines – prezentace na Carnegie Mellon University, 2. 8. 2002 (PPT; anglicky)
  3. ↑ Larry Wall: Apocalypse 5: Pattern Matching, 18. 5. 2006

Související články

Externí odkazy


Citováno z „http://www.multimediaexpo.cz/mmecz/index.php/Regul%C3%A1rn%C3%AD_v%C3%BDraz“