Nahoru
 

Jak fungují regulární výrazy v programování

Regulární výraz je perfektní nástroj vyhledávání v textu. Stačí napsat pár znaků a klíčových slov, které hledáme a naše prostředí se postará o zbytek. I když se regulární výraz může zdát jako nepochopitelně složitá technologie, vnitřní fungování je až překvapivě jednoduché

Regulární výraz je řetězec, kterým zkráceně popisujeme celou množinu řetězců. Například regulárním výrazem „.*a.*“ popisujeme nekonečnou množinu všech slov, které obsahují písmeno „a“. Jiným regulárním výrazem, například „ahoj“, popisujeme konečnou množinu řetězců, konkrétně je to množina o velikosti jedna, se slovem „ahoj“.

Důležité je zmínit, že každý programovací jazyk může mít různou syntax regulárních výrazů. Na tom však nezáleží. Jelikož regulární výrazy obecně popisují nějaký regulární jazyk, můžeme s jistotou říci, že jsou regulární výrazy všech programovacích jazyků silově ekvivalentní. Některé jazyky mohou mít speciální znaky pro usnadnění psaní samotných výrazů (tzv. syntaktický cukr), nicméně co můžeme napsat v jednom programovacím jazyce, lze napsat i v jiném.

Víme tedy, že regulární výraz představuje (mnohdy i nekonečnou) množinu slov. Jak však program dokáže otestovat řetězec a všechny jeho podřetězce, zda náhodou nepatří do námi definované množiny (zvláště když je ta množina nekonečná)? Naivní způsob by byl jednoduchý „bruteforce“, tedy otestovat všechny možné rovnosti a doufat, že nalezneme shodu. Tento přístup je zjevně extrémně neefektivní a rozhodně nemůže fungovat v případech nekonečných množin (které jsou bohužel nejčastější).

Vzhledem k tomu, že regulární výraz má pevně danou sadu pravidel definovanou regulárním jazykem, můžeme vymyslet „přístroj“, který dokáže v lineárním čase otestovat, zda nějaký řetězec patří do námi definované množiny. Tento „stroj“ nazýváme konečný automat.

Konečný automat

Konečný automat je abstraktní popsání nějaké realizace, kontrolující, zda vstupní řetězec patří do cílové množiny (klidně i nekonečné množiny). Formálněji řečeno: Konečný automat dokáže rozhodnout, zda slovo patří do regulárního jazyka (popsaného například regulárním výrazem). Této funkce dociluje velmi elegantně, a to definováním jednoduchých stavů a přechodů mezi stavy.

Oficiální definice konečného automatu zní následovně:

Konečný automat je definován jako uspořádaná pětice (S, Σ, σ, s, A), kde:

  • S je konečná množina stavů
  • Σ je konečná vstupní abeceda
  • σ (přechodová funkce) je zobrazení S × Σ → S (deterministický automat), nebo S × {Σ ∪ ε} → P(S) (nedeterministický automat)
  • s je počáteční stav (s ∈ S)
  • A je množina koncových stavů (A ⊆ S)

Nebojte, tato formální definice není intuitivní ani pro část studentů ČVUT (včetně mě). Pojďme si konečný automat vysvětlit lidštěji a na příkladu.

Konečný automat začíná vždy v určeném počátečním stavu. Poté automat čte znak po znaku ze vstupu. Podle toho, jaký znak přečte, se buď posune do jiného stavu, nebo skončí a vyhodnotí, že vstupní řetězec do cílové množiny nepatří. Nezpracování celého vstupu automaticky znamená, že řetězec nepatří do cílové množiny. Po přečtení celého vstupního řetězce konečný automat zkontroluje, zda je poslední stav koncový. Pokud je koncový, vstupní řetězec do cílové množiny patří, jinak nepatří.

Ukažme si prostý příklad na konečném automatu, který kontroluje, zda vstupní slovo je buď „ahoj“, nebo slovo „ahojda“. Kontrolujeme tedy, zda vstupní řetězec patří do cílové množiny (resp. do regulárního jazyka) obsahující slova „ahoj“ a „ahojda“.

V prvním kroku se nacházíme v počátečním stavu, označený vstupní šipkou. Na vstupu máme 4 znaky, konkrétně „AHOJ“.

Automat v počátečním stavu
Obrázek č. 1: Nacházíme se v počátečním stavu automatu

Následující písmeno na čtení je „A“. Pokud ho přečteme, realizujeme přechod do dalšího stavu vyznačený šipkou a přesuneme se na čtení dalšího znaku. Nutno podotknout, že se můžeme pohybovat pouze po přechodu, jehož písmenko je identické se vstupním. Nemůžeme například přečíst písmeno „A“ a vydat se po přechodu s písmenkem „B“.

Konečný automat ve stavu
Obrázek č. 2: Přestoupili jsme do dalšího stavu po přijetí písmena „A“ ze vstupu
Konečný automat ve stavu
Obrázek č. 3: Přestoupili jsme do dalšího stavu po přijetí písmena „H“ ze vstupu
Konečný automat ve stavu
Obrázek č. 4: Přestoupili jsme do dalšího stavu po přijetí písmena „O“ ze vstupu
Konečný automat ve stavu
Obrázek č. 5: Přestoupili jsme do dalšího stavu po přijetí písmena „J“ ze vstupu

Jelikož jsme dočetli celý vstupní řetězec a skončili jsme v koncovém stavu, onačeným dvojitým kroužkem, můžeme říci, že tento vstup patří do naší cílové množiny. Pokud bychom na vstup dali například „AHO“, v koncovém stavu bychom neskončili a věděli bychom, že „AHO“ do naší cílové množiny nepatří. Pokud bychom zvolili na vstupu například „DOPE“, potom bychom se zastavili rovnou u písmena „D“, pro které nemáme definovaný přechod „D“ (máme pouze přechod „A“), a tudíž do cílové množiny nepatří.

Příklad konečného automatu, který přijímá množinu všech slov, obsahující písmeno „a“, můžeme definovat například takto:

Konečný automat
Obrázek č. 6: Příklad konečného automatu přijímající slova obsahující „A“

Hvězdička ve výše zobrazeném automatu označuje všechna slova v abecedě a křížek označuje všechna slova v abecedě kromě „A“.

V automatu bude vstupní slovo iterovat ve stavu „1“, který není konečným stavem. Jakmile obdržíme písmeno „A“, přesuneme se do konečného stavu, kde přijmeme celý zbytek vstupu a vyhodnotíme jej jako slovo, patřící do cílové množiny. Pokud zůstaneme ve stavu „1“, který není konečný, víme, že slovo neobsahuje písmeno „A“ a tudíž nepatří do cílové množiny.

Regulární výrazy a konečné automaty

Tím, že regulární výrazy jsou regulárním jazykem, máme dokázáno, že každý regulární výraz lze převést do konečného automatu. Regulární výrazy se tedy uvnitř programu překládají do konečných automatů a následně pouze kontrolují vstupní text, zda některé jeho části náhodou „neprostoupí“ testem vygenerovaného konečného automatu.

Příklady překladu regulárních výrazů na konečné automaty, kde hvězdička u přechodu mezi stavy značí jakýkoliv znak abecedy:

Konečné automaty
Obrázek č. 7: Příklad prostých konečných automatů reprezentovaných regulárními výrazy
Konečný automat
Obrázek č. 8: Příklad složitějších regulárních výrazů a jejich konečných automatů
Konečný automat
Obrázek č. 9: Příklad složitějšího regulárního výrazu a jeho konečného automatu

Regulární výrazy popisují množinu slov neboli regulární jazyk. Abychom v našem programovacím jazyce mohli testovat, zda vstupní řetězec nebo jeho podřetězce patří do množiny definované regulárním výrazem, překládáme regulární výraz na konečný automat. Konečný automat tuto úlohu zvládne velmi prostě a efektivně, a to za pomocí stavů a podmíněných přechodů mezi stavy.