Regulární výraz

Regulární výraz (zkratky regexp, regex či RE z anglického regular expression) je textový řetězec, který slouží jako vzor pro vyhledávání textu. Regulární výraz tvoří soubor dvou typů znaků – literálů, které musí hledaný řetězec obsahovat, a pomocných znaků, které umožňují pokročilé možnosti vyhledávání. Například pokud chce uživatel v textu vyhledat řetězec, který nezná přesně nebo který může mít více variant, umožňuje mu použití regulárního výrazu popsat podmínky vyhledávání („regule“), které musí hledaný řetězec splňovat. Regulární výraz se zapisuje regulárním jazykem, který zavedl americký matematik Stephen Cole Kleene.[1]

Regulární výrazy jsou dostupné v mnoha skriptovacích jazycích, internetových vyhledávačích, textových editorech nebo souborových manažerech, nejčastěji formou externí knihovny (oniguruma) nebo sady funkcí (regex.h jako součást libc).

Způsob využití

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é

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ý znakový literál (znak abecedy) a, popisující právě text a.
  2. ε je regulární výraz pro prázdný řetězec.
  3. ∅ označuje prázdný jazyk.
  4. 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.
  5. 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.
  6. 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.
  7. 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:

Varianty

  • | (svislá čára, roura) odděluje alternativy, např. výrazu kurz|kurs odpovídá řetězec „kurz“ i „kurs“

Seskupování

  • () kulaté závorky umožňují definovat, na jakou část se další operátory mají vztahovat, např. pro předchozí příklad lze využít i výraz kur(z|s)

Libovolný znak

  • . (tečka) znamená libovolný znak, např. .ez značí třípísmenný řetězec končící na -ez (bez, fez, jez, lez atd.). Pozn.: Podle konkrétního nastavení se nemusí vztahovat na nový řádek.
  • [ ] Jeden z uvedených znaků: zápis [a-z0-9] znamená libovolné malé písmeno nebo číslice.
  • [^ ] Jeden z neuvedených znaků: zápis [^a-z0-9] znamená libovolný znak kromě malých písmen a číslic. Jindy se místo stříšky používá vykřičník [! ].
  • \kód 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.

Počet opakování

  • ? Nepovinná část, sémanticky odpovídá „0 nebo 1 výskyt“. Např. výrazu hos?tel odpovídá hostel i hotel.
  • * Žádný nebo libovolný počet opakování, např. 10*1 označuje řetězce: 11, 101, 1001, 10001
  • + Jedno a více opakování, 49+ označuje: 49, 499, 499 atd., ale nikoli samotné 4.
  • {m,n} Zadaný počet opakování: zápis 10{3,5} popisuje jedničku a skupinu tří až pěti nul – 1000, 10000, 100000.

Začátek a konec

  • ^ 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.

Speciální znaky

  • \ zpětné lomítko Je-li potřeba zadat znak, který má zde speciální význam, je před něj potřeba vložit zpětné lomítko (tzv. escapování): \. pro vyhledání tečky.

Specifické dle jazyka

  • 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), 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ří ({3}) číslic (\d), mezeru a dvě číslice – formát PSČ.
  • <[^>]*> pro HTML prvek – libovolný text uzavřený mezi špičaté závorky; libovolný text je popsán jako libovolný počet znaků (*) jiných než „>“ ([^>]) (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 čárkou nebo čárkou následovanou mezerou: hexadecimální číslice může být kromě 0–9 i jedno z prvních šesti písmen malé nebo velké abecedy ([0-9a-fA-F]), první číslo může mít jednu nebo více číslic (+), po něm může následovat žádné nebo libovolný počet ((…)*) dálších čísel, vždy nejdříve čárka, pak žádná nebo jedna ( ?) mezera a nakonec vlastní číslo zapsané stejným způsobem jako to první.

Odkazy

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 Archivováno 12. 1. 2010 na Wayback Machine., 18. 5. 2006

Související články

Externí odkazy