Section author: Luka Vretenar

Regularni izrazi i konačni automati

Regularni izrazi

  • Nizovi znakova sa posebnim značenjem koji nam služe za pretragu i opisivanje nekog ulaznog niza znakova.

  • Način specificiranja konačnog automata koji procesira zadani ulazni niz znakova.

  • Imaju podršku u većini programskih jezika i alata koji se danas koriste.

  • Najčešće nam služe za:

    • opisivanje uzoraka u tekstu i pretragu teksta

    • izmjenu i manipulaciju opisanih uzoraka u tekstu

  • Neke od primjena regularnih izraza:

    • sustavi za bojanje sintakse (syntax highlighting)

    • srovjera validnosti podataka kod korisničkog unosa (form validation, text validation)

    • eskstrakcija pojedinih elemenata iz formatiranog niza

  • Primjer regularnog izraza koji opisuje sve prirodne brojeve u nekom tekstu: [1-9][0-9]*.

  • Kako bi nam olakšali izradu i testiranje regularnih izraza postoje razni pomoćni web alati:

  • U ovim vježbama se koriste prošireni regularni izrazi ili ERE.

Uzorci teksta i ostali znakovi

  • Uzorak koji odgovara određenom nizu znakova možemo specificirati kao točno taj niz znakova.

  • Ako pretražujemo tekst za niz Dobar dan, uzorak za traženje tog niza bi bio Dobar dan.

Hint

Važno je paziti na mala i velika slova u uzorcima jer su regularni izrazi osjetljivi na veličinu slova.

  • Ako želimo zadati uzorak koji na određenom mjestu ima bilo koji znak, onda možemo koristiti specijalni znak ..

  • Primjer takvog uzorka je d..r, nizovi koji tom uzorku odgovaraju mogu biti:

    • daar

    • dabr

    • dacr

    • i tako dalje za sve kombinacije dva znaka na mjestima gdje je .

Zadatak

  • Zadan je tekst na dnu poglavlja.

  • Regularnim izrazom označiti sva pojavljivanja riječi Perl.

  • Regularnim izrazom označiti pojavljivanje sve riječi koje počinju sa izraz a završavaju bilo kojim slovom.

  • Određeni znakovi u regularnim izrazima imaju posebno značenje, da bi ih koristili u uzorku kao znakove koje zapravo predstavljaju, potrebno ih je označiti znakom \ ispred samog znaka.

  • Ti znakovi su:

    • \ i /

    • ^ i $

    • .

    • |

    • ?

    • * i +

    • ( i )

    • [ i ]

    • {

  • Primjer je traženje izraza $20, kako sadrži jedan od posebnih znakova potrebno je napraviti regularni izraz \$20 da bi ga mogli tražiti.

  • Specijalni znakovi koji predstavljanju neki element niza su:

    • . – bilo koji znak

    • ^ – označava početak linije

    • $ – označava kraj linije

    • \b – označava početak ili kraj riječi (gdje je riječ odvojena razmacima)

Zadatak

  • Regularnim izrazom označiti izraz (automate) uključujući i zagrade.

  • Regularnim izrazom označiti izraz Perl koji se nalazi na početku linije.

Višestruki izbor i grupiranje

  • Moguće je pretraživati izraze koji mogu biti sastavljeni od jednog ili više različitih podnizova.

  • Da bi specificirali pretragu po jednom i drugom nizu koristimo simbol | kojem ih odvajamo.

  • Regularni izraz jedan|dva će nam pronaći nizove jedan i dva.

Zadatak

  • Regularnim izrazom označiti sve nizove reg i izraz u zadanom tekstu.

  • Ako želimo specificiratid da su pojedini podnizovi djelovi većeg niza koji tražimo, možemo grupirati pojedine višestruke izbore u odvojene grupe koristeći ( i ).

  • Regularni izraz gr(a|e)y će nam pronaći nizove gray i grey.

Zadatak

  • Regularnim izrazom označiti sve nizove ama i aka grupirajući po slovu m ili k u zadanom tekstu.

Klase znakova

  • Već smo vidjeli da sa . možemo specificirati da želimo bilo koji znak na određenom mjestu, no ako želimo da bude samo jedan od definiranih znakova možežmo koristiti klase znakova.

  • Klasa znakova se definira unutar [ i ], primjer [abcd] i [0-9].

  • Klasom znakova definiramo da određeni znak u nizu možež biti jedan od znakova u toj klasi.

  • Regularni izraz [Dd]obar dan će nam pronaći nizove Dobar dan i dobar dan.

Zadatak

  • Pronaći sva velika slova u zadanom tekstu.

  • Pronaći sva velika slova i znamenke 0 i 1.

  • Pronaći sve brojeve duljine 4 u tekstu, pronađeni niz ne smije biti sastavljen ododvojenih znakova.

  • U klasama možemo definirati i raspone znakova koristeći - da odvojimo početni i krajnji znak u rasponu.

  • Klasu [abcdefghijklmnoprsquvwxz] koja nam predstavlja sva mala slova, možemo zapisatiti i kao [a-z].

  • Ako želimo obrnuti znakove koje predstavlja klasa, koristimo znak ^ na početku klase.

  • Regularni izraz [^0-9] će nam pronaći sve znakove koji nisu znamenke 0123456789.

Zadatak

  • Pronaći sve znamenke koji nisu 0.

  • Pronaći sva slova koja nisu u rasponu od a do j i koja nisu znakovi ( i ).

Ponavljanja izraza

  • Ako želimo da se određeni znak, klasa znakova ili grupa znakova ponavlja nula, jednom ili više puta, možemo koristiti modifikatore ponavljanja.

  • Modifikatori ponavljanja su ?, + i * i nalaze se nakon znaka, klase ili grupe čije ponavljanje određuju.

  • Značenja pojedinih modifikatora su:

    • ? – znak koji prethodi se može pojaviti jednom ili nijednom

    • + – znak koji prethodi se može pojaviti jednom ili više puta

    • * – znak koji prethodi se može pojaviti nijednom ili više puta

  • Regularni izraz [a-z]* će nam pronaći sve nizove koji sadrže samo mala slova: a, aa, ab, asdf…

  • Regularni izraz abc? će pronaći nizove ab i abc.

Zadatak

  • Pronaći sve brojeve duljine jedan ili više koristeći klasu i ponavljanja.

  • Pronaći sve nizove velikih slova koristeći klasu i ponavljanja.

  • Pronaći sve riječi koji započinju velikim slovom i završavaju malim slovima.

  • Ponavljanja također možemo specificirati i brojčanim vrijednostima m i n u modifikatoru oblika {m,n} gdje su:

    • {0,1} – ekvivalentno ?

    • {1,} – ekvivalentno +

    • {0,} – ekvivalentno *

    • {m,n} – znak, klasa ili grupa se ponavlja najmanje m a najviše n puta

Zadatak

  • Pronađi sve riječi koji su duljine veće od 8 znakova.

Primjena u alatu grep

  • Na svim Linux sustavima postoji alat koji nam omogućuje pretragu teksta koristeći regularne izraze.

  • Alat grep podržava proširene regularne izraze i možemo ga pozvati slijedećom naredbom:

    egrep "regex" datoteka

  • Gdje je regex regularni izraz koji pretražujemo a datoteka naziv daoteke u kojoj pretražujemo.

  • Izlaz iz programa su sve linije koje sadrže tražene izraze.

Zadatak

  • Koristeći alat egrep pretraživati datoteku /etc/passwd iz komandne linije.

  • Pronaći sve linije koje imaju izraze /var ili /bin.

  • Pronaći sve linije koje počinju sa nizom slova duljim od 4.

  • Pronaći sve linije koje završavaju na bash.

  • Pronaći sve linije dulje od 50 znakova.

  • Pronaći sve brojeve koji započinju sa znamenkom 1.

Tekst za vježbe

Porijeklo regularnih izraza leži u teoriji automata i teoriji formalnih jezika, pri čemu su oboje discipline teoretskog računarstva.
Ove discipline proučavaju modele računanja (automate) te načine opisa i klasifikacije formalnih jezika.
Matematičar Stephen Kleene je 1950-ih opisao ove modele koristeći matematičku notaciju zvanu regularni skupovi.
Ken Thompson je ugradio ovu notaciju u uređivač QED, a potom i u Unix editor ed, što je s vremenom dovelo do uporabe regularnih izraza u grep-u.
Otad se regularni izrazi naširoko koriste u Unixu i Unixoidnim pomoćnim programima kao što su expr, awk, Emacs, vi, lex i Perl.

Perl i Tcl regularni izrazi su izvedeni iz regex biblioteke koju je napisao Henry Spencer, iako je Perl kasnije proširio Spencerovu regex biblioteku i dodao mnogo novih svojstava.
Philip Hazel je razvio PCRE (Perl Compatible Regular Expressions) koji jako dobro oponaša funkcionalnost regularnih izraza u Perlu, i kojeg koriste mnogi moderni programski alati kao što su PHP, ColdFusion, i Apache.
Dio napora uloženog u dizajn Perla 6 je baš u smjeru poboljšanja integracije Perlovih regularnih izraza, te povećanju njihovog područja djelovanja u svrhu dozvole definicije tzv. 'parsing expression grammar'.
Rezultat je mini-jezik zvan Perl 6 pravila, koja se koriste kako za definiciju gramatike Perla 6 tako i kao alat Perl programerima.
Ova pravila čuvaju sva svojstva regularnih izraza, ali i dozvoljavaju definicije u BNF stilu parsera tehnikom rekurzivnog spusta preko potpravila.

Korištenje regularnih izraza u strukturiranim informacijskim standardima (za modeliranje dokumenata i baza podataka) se pokazalo vrlo važnim, počevši od 1960-ih te se proširujući 1980-ih konsolidacijom industrijskih standarda kao što je ISO SGML.
Jezgra standarda jezika specifikacije strukture su regularni izrazi.
Jednostavnija i evidentnija uporaba jest u groupnoj sintaksi DTD-a.

Izvor: Wikipedia

Konačni automati

  • Regularni izraz zadan nizom specijalnih znakova se prije korištenja u računalu pretvori u konačni automat.

  • Optimalan alat za izvršavanje regularnog izraza.

  • Mogu opisivati i mnoge druge pojave vezane za svijet oko nas.

digraph finite_state_machine { rankdir=LR; node [ shape = point ]; s node [ shape = doublecircle, label = "S1" ] S1; node [ shape = circle, label = "S2" ] S2; s -> S1; S1 -> S1 [ label = "1" ]; S1 -> S2 [ label = "0" ]; S2 -> S1 [ label = "0" ]; S2 -> S2 [ label = "1" ]; }

  • Čitanjem određenog ulaznog znaka, konačni automat prelazi u novo stanje i generira neki izlazni znak.

  • Određeni konačni automat definiran je:

    • stupom stanja u kojima se taj automat može nalaziti

    • skupom ulaznih znakova koje taj automat može pročitati sa ulaza

    • skupom prijelaza koji definiraju kako automat prelazi u nova stanja

Deterministički konačni automati

  • Najjednostavniji oblik konačnog automata.

  • Determinizam konačnog automata nam govori da za pojedini ulaz i određeno stanje postoji samo jedno novo stanje u koji taj automat može preći.

  • Konačni automat možemo specificirati:

    • matematičkom definicijom

    • tablicom prijelaza

    • grafičkim prikazom

  • Matematički, konačni automat možemo specificirati parom skupova: \(A=(Q, \Sigma, \Delta, q_0, F)\)

    • \(Q\) – skup svih stanja u kojima može biti automat

    • \(\Sigma\) – skup svih ulaznih znakova koje automat može pročitati

    • \(\Delta\) – skup svih funkcija prijelaza, funkcije su oblika \(\delta(q, \sigma) = q\)

    • \(q_0\) – početno stanje u kojem se nalazi automat prije čitanja znakova

    • \(F\) – skup svih prihvatljivih stanja, stanja u kojima prihvaćamo pročitani niz kao ispravan

Zadatak

  • Za konačni automat zadan matematičkom definicijom napraviti tablicu prijelaza i grafički prikaz:

\[Q = \{S, A\}; \Sigma = \{a, b\}; q_0 = S; F = \{A\}; \delta_0(S, a) = A; \delta_1(S, b) = A; \delta_2(A, a) = S; \delta_3(A, b) = A\]

  • Za isti atuomat provjeriti da li prihvaća ulazni niz znakova baab.

  • Iz zadane matematičke definicije konstruiramo tablicu prijelaza:

    a

    b

    >

    S

    A

    A

    0

    A

    S

    A

    1

  • Grafički prikaz istog automata:

    digraph finite_state_machine { rankdir=LR; node [ shape = point ]; s node [ shape = circle, label = "S" ] S; node [ shape = doublecircle, label = "A" ] A; s -> S; S -> A [ label = "a, b" ]; A -> S [ label = "a" ]; A -> A [ label = "b" ]; }

  • Provjera da li konačni automat prihvaća zadani niz baab se vrši postupkom:

    \[S \xrightarrow{b} A \xrightarrow{a} S \xrightarrow{a} A \xrightarrow{b} A\]

  • Niz je ispravan i prihvaća se jer je završno stanje \(A\) u skupu prihvatljivih stanja \(F\).

Zadatak

  • Za konačni automat zadan matematičkom definicijom napraviti tablicu prijelaza i grafički prikaz:

\[ \begin{align}\begin{aligned}Q = \{pp, np, pn, nn\}; \Sigma = \{0, 1\}; q_0 = pp; F = \{pp, nn\}\\\delta_0(pp, 1) = pn; \delta_1(pp, 0) = np; \delta_2(pn, 1) = pp; \delta_3(pn, 0) = nn; \delta_4(np, 1) = nn; \delta_5(np, 0) = pp; \delta_6(nn, 1) = np; \delta_7(nn, 0) = pn\end{aligned}\end{align} \]

  • Za isti atuomat provjeriti da li prihvaća ulazni niz znakova 10110.