REGULAARAVALDISED

Sissejuhatus. 3

1. Regulaaravaldised formaalsete keelte teoorias. 5

1.1. Regulaaravaldise definitsioon. 5

1.2. Regulaaravaldise poolt defineeritud keel 5

1.3. Lõplikud automaadid. 6

1.4. Regulaaravaldisest mittedetermineeritud lõpliku automaadi moodustamine. 7

2. Regulaaravaldiste tutvustus. 9

2.1. Koht arvutiteaduses. 9

2.2. Kasutusvaldkond. 10

2.3. Jokkerid. 13

3. Regulaaravaldiste koostamine. 14

3.1. Süntaks operatsioonisüsteemis UNIX.. 14

3.2. Kokkuvõte metasümbolitest 18

3.3. Näiteid. 18

3.4. Jokkerite teisendus regulaaravaldisteks. 20

4. Regulaaravaldiste kasutamine. 21

4.1. UNIX�i korraldus grep. 21

4.2. UNIX�i korraldus egrep. 25

4.3. Elektronposti töötlemise programm Procmail 26

4.4. Otsisüsteemid. 29

5. Realisatsioon. 30

5.1. Kasutajaliides. 30

5.2. Realiseerimisest 32

Kokkuvõte. 33

Kirjandus. 34

Abstract 36

Lisa 1. Formaalsete keelte teoorias esinevate regulaaravaldiste poolt genereeritud keelt ära tundva Java rakendi lähtetekst 37


Sissejuhatus

 

Regulaaravaldiste teooriale aluse panijaks võib pidada ameerika matemaatikut Stephen Kleene�i (1909-1994), kes on üks mõjukamaid tegelasi teoreetilise arvutiteaduse arendamisel [18]. Regulaaravaldised on pärit formaalsete keelte ning automaatide teooriast, millest mõlemad on teoreetilise arvutiteaduse osad. Kleene kasutas regulaaravaldisi regulaarsete hulkade algebra üleskirjutamiseks.

 

Regulaaravaldised on vahend, mida kasutatakse sõnade hulga kirjeldamiseks. Regulaaravaldisi kasutatakse laialdaselt UNIX�i platvormil, kus neid rakendatakse kõikvõimalikel tekstiga seotud operatsioonidel (nt. otsimine, otsimine/asendamine, valideerimine).

 

Käesoleva semestritöö eesmärgiks on luua abimaterjal regulaaravaldiste mõiste õpetamisel, näidata regulaaravaldiste kasulikkust teksti otsimisel  operatsioonisüsteemi UNIX baasil ning anda ülevaade regulaaravaldiste kohast arvutiteaduses. Antud töö sobib arvutiteaduse algkursusi kuulavatele informaatika, infotehnoloogia ja informaatika õpetaja erialade tudengitele.

 

Töö koosneb viiest peatükist. Esimeses peatükis on esitatud regulaaravaldiste formaalne käsitlus, nii nagu seda kasutatakse regulaaravaldiste õpetamisel ka TÜ arvutiteaduse instituudi poolt loetavas aines �Arvutiteaduse elemendid� informaatika õpetajatele. Defineeritakse regulaaravaldis ja regulaarne keel ning antakse ülevaade regulaaravaldise seosest lõplike automaatidega.

 

Teises peatükis räägitakse regulaaravaldiste olemusest, otstarbest ja kasutus-valdkondadest.

 

Kolmandas peatükis defineeritakse regulaaravaldiste kirjapanemisel kasutatav sümboolika.

 

Neljandas peatükis tuuakse näiteid regulaaravaldiste kasulikkusest teksti otsimisel ja filtreerimisel UNIX�i käskudes grep ja egrep ning programmis procmail.

 

Vastavalt esimeses peatükis esitatud definitsioonidele on viiendas peatükis kirjeldatud käesoleva semestritöö raames koostatud interaktiivset veebilehekülge [19], kus tudengitel on võimalus harjutada kätt regulaaravaldiste tundmisel ning koostamisel. Regulaaravaldised on realiseeritud lõplikke automaate kasutades ning realisatsiooni idee on samuti viiendas peatükis ära seletatud ning lähtekood on esitatud lisana.


1. Regulaaravaldised formaalsete keelte teoorias

 

Regulaaravaldiste ülesmärkimiseks kasutatakse mitmeid erinevaid tähistusviise. Alljärgnevalt pakutud süntaks on üks enim kasutatav.

Esimesed kolm punkti baseeruvad allikatel [15] ja [16], ülejäänud kaks punkti allikal [17].

 

1.1. Regulaaravaldise definitsioon

 

Tähistame: ε - tühisõna, ¨ - tühi hulk, ∑ - tähestik, ∙ - konkatenatsioon (tähtede kõrvutikirjutamine).

1) ε ja ¨ on regulaaravaldised tähestikus ∑;

2) suvaline täht a Î ∑ on regulaaravaldis tähestikus ∑;

3) kui R1 ja R2 on regulaaravaldised, siis on ka (R1+R2), (R1∙R2) ja (R1)* regulaaravaldised.

 

Punktides 1) ja 2) defineeritud regulaaravaldisi nimetatakse ka primitiivseteks regulaaravaldisteks. Seega, kui |∑| = n, siis on tähestikus ∑ defineeritud n+2 primitiivset regulaaravaldist.

 

Punkti 3) põhjal võib regulaaravaldisse tulla üsna palju kohustuslikke sulge, näiteks: (((((e∙b)∙c)+a))*∙d). Kuna sellised sulud raskendavad avaldise lugemist, siis tehakse regulaaravaldiste lihtsamaks üleskirjutamiseks järgmised kokkulepped:

1. Operatsioonide prioriteedid on määratud kahanevalt: *,∙,+

2. Sulud võib ära jätta, kui nad on üheselt taastatavad.

3. Konkatenatsiooni '∙' jätame kirjutamata.

Seega saame ülaltoodud regulaaravaldise kirjutada lihtsalt: (ebc+a)*d

 

1.2. Regulaaravaldise poolt defineeritud keel

 

Igale regulaarsele avaldisele R seatakse vastavusse sõnade hulk R' (regulaarne keel) tähestikus ∑, järgmise definitsiooniga:

1) kui R = ε, siis R' = {ε}; kui R = ¨, siis R' = {}.

2) kui R = a, kus a Î ∑, siis R' = {a}.

3) kui R1 ja R2 on regulaaravaldised ning R'1 ja R'2 neile vastavusse seatud hulgad, siis

            kui R = (R1+R2), siis R' = R'1 È R'2 (kus È - hulgateoreetiline ühend)

            kui R = (R1∙R2), siis R' = R'1 ∙ R'2 (kus ∙ - kahe hulga konkatenatsioon)

            kui R = (R1)*, siis R' = R'1 = {ε} È {x | x on R1 sõnade konkatenatsioon}

NÄITEID regulaarsetest avaldistest ja neile vastavatest hulkadest:

            Regulaaravaldis         Keel

            a*                                {ε, a, aa, aaa, ...}

            abc                               {abc}

            a+b+c                          {a, b, c}

            a(bc+dc)                      {abc, adc}.

 

1.3. Lõplikud automaadid

 

Lõplik automaat on masin, millel on lõplik lähtesümbolite hulk ehk tähestik ∑, lõplik olekute hulk Q, fikseeritud lähteolek, fikseeritud lõppolekute hulk ja üleminekuseos d Ì Q x ∑ x Q.

Kui d ei ole funktsioon, s.t kehtivad d(q, a) = q1 ja d(q, a) = q2, kus q, q1, q2 Î Q, a Î ∑ ja q1 ¹ q2, siis nimetatakse seda automaati mittedetermineeritud lõplikuks automaadiks.

 

Kõige levinum on lõpliku automaadi esitus graafina. Ütleme, et lõplik automaat A aktsepteerib (tunneb ära) sõna x, kui sellele sõnale vastav tee automaadi A graafis algab algolekust ja lõpeb lõppolekus.

 

Igale regulaaravaldisele R leidub vastav lõplik automaat, mis tunneb ära selle regulaaravaldise R poolt genereeritud keele.


 

1.4. Regulaaravaldisest mittedetermineeritud lõpliku automaadi moodustamine

 

Igale regulaaravaldises esineda võivale operatsioonile seatakse vastavusse lõplik automaat. Kogu avaldisele vastab lõplike automaatide lihtne kompositsioon, millel on üks algolek ja lõppolek.

 

Igal lõplikul automaadil on oma algolek i ja lõppolek f. Iga uue lõpliku automaadi koostamisel võtame kasutusele uue alg- ja lõppoleku. Hiljem kompositsiooni juures võivad mõned neist seisunditest osutuda üleliigseiks, siis ühendame nad üheks või jätame lihtsalt kirjutamata.

 

1. Tühjale sümbolile ε seame vastavusse järgmise automaadi:

2. Igale kasutatavale terminaalsele sümbolile aÎ seame vastavusse automaadi

3. Regulaaravaldises esinevatele valikutele s + t seame vastavusse järgmised automaadid (kus N(s) ja N(t) on s ja t vastavad lõplikud automaadid):

4. Regulaaravaldises esinevatele konkatenatsioonidele st seame vastavusse järgmised automaadid:

5. Regulaaravaldises esinevatele kordustele s* seame vastavusse sellised automaadid:

6.Alamavaldistele kujul (s) seame vastavusse sama automaadi, mis avaldisele s, s.t N(s).

 

1.5. Näide

 

Võtame regulaarse avaldise a*(ba+c) ja konstrueerime sellele avaldisele vastava mittedetermineeritud lõpliku automaadi, mis näeb välja selline:


2. Regulaaravaldiste tutvustus

 

2.1. Koht arvutiteaduses

 

Regulaaravaldisi saab kasutada tekstilise mustri tuvastamiseks ehk mallvõrdlemise (võrdlus näidisega, pattern-matching) vahendina, mida rakendatakse mingile tekstile. Iga teksti jaoks antakse vastus, kas tekst sobis avaldisega või mitte. Regulaaravaldistes on oluline sümbolite omavaheline järjestus.

 

Matemaatiliselt, iga regulaaravaldis esindab keelt (sõnade hulka). Sõnad, mis sobivad regulaaravaldise mustriga, kuuluvad sinna keelde, sõnad, mis ei sobi mustriga, ei kuulu.

 

Mustri tuvastamist võib vaadelda kui masinat, mis saab sisendiks sümbolite jada (sõna) ning tulemuseks on sõna aktsepteerimine või mitteaktsepteerimine. Kõikide sisendsõnade läbi proovimisel saamegi keele, mille see masin defineerib (ära tunneb).

 

Ameerika filoloog Noam Chomsky esitas keelte klassifikatsiooni, mis jagab formaalsed keeled nelja klassi ning millele vastab täpselt neli masinate klassi, mis interpreteerivad neid keeli [2]. Kõik, mida saab arvutada madalama taseme masinaga, saab arvutada ka kõrgema taseme masinaga. Chomsky klassifikatsioon on järgmine:

 

MASINATE KLASS             KEELTE KLASS                   NÄIDE

lõplik automaat                         regulaarne keel                         mallvõrdluskeel

magasinmäluga automaat           kontekstivaba keel                    lihtne programmeerimiskeel

lineaarselt seotud automaat        kontekstiga keel                        programmeerimiskeel

Turingi masin                            kitsendused puuduvad              

 

Kõige lihtsam masin on lõplik automaat, kõige keerulisem on Turingi masin, mis realiseerib iga algoritmi.

 

Keeled on defineeritud grammatika reeglite formaalse kujuga. Regulaarse keele grammatika on regulaaravaldis. [2]

 

2.2. Kasutusvaldkond

 

Kasutusvaldkonna kirjeldamisel on tehtud kokkuvõte allikatest [3], [4], [5] ja [6].

 

Kui küsida mistahes piisavalt kogenud UNIX-laadse keskkonna (*NIX [3]) kasutaja käest, mis on tema operatsioonisüsteemi 10 kõige enam meeldivamat iseärasust, siis kindlasti mainitakse ka regulaaravaldisi lisaks niisugustele suurepärastele omadustele nagu süsteemi 99%-line töökindlus (99% uptime) ja operatsioonisüsteemi kaugtaaskäivituste võimalus (remote system reboots).

 

Kui aga küsida kõige ebameeldivamaid jooni, siis kuskil �zombie protsesside� (tütarprotsess, mis on oma töö lõpetanud ning mille all kinni olnud ressursid tuleb vabastada) ja installeerimiste hulgas kirutakse ka regulaaravaldisi.

 

Seega võib öelda, et regulaaravaldistes nähakse nii head kui ka halba samal ajal. Üks põhjus on see, et regulaaravaldisi on lihtne kirjutada ning nad on teksti otsimisel hädavajalikud, kuid neid on raske lugeda. Kasutatav süntaks ning regulaaravaldise �välimus� on pigem eemaletõukav kui julgustav. Seda illustreerib järgnev näide regulaaravaldisest (reaalarvu muster):

 

(\+|-)?([1-9][0-9]*|0)(\.[0-9]+)?

 

Regulaaravaldisega esitatud mustrit saab võrrelda mingis failis oleva tekstiga või mingile programmile ette antud andmetega või näiteks ka veebilehe külastaja poolt vormile sisestatud infoga.

 

Olenevalt sellest, kas muster sobis tekstiga või mitte, saab peale võrdlustulemuse teadasaamist sooritada vastavaid operatsioone, näiteks vastava programmi või skripti täitmine.

 

Regulaaravaldised ei ole mitte vahend omaette, vaid ta on osa suuremast mehhanismist. Regulaaravaldised ei määra keelt, nii nagu seda teevad näiteks programmeerimiskeeled C, Perl jms., ega moodusta eraldiseisvat vahendit, näiteks nagu UNIX�i otsimisvahend grep, vaid ta defineerib süntaksi, mida paljud keeled ja vahendid toetavad.

 

Regulaaravaldised on seotud peaaegu kõigi *NIX�il baseeruvate vahenditega, sealhulgas tekstitoimetitega (nt. vi, emacs), lehitsejatega (nt. more, less), skriptikeeltega (nt. Perl, Tcl, PHP) ja shell-programmidega (nt. grep, egrep, ed, awk, sed). Neid saab kasutada konfiguratsioonifailides ning elektronposti filtreerimisel. Lisaks kasutatakse teda sellistes skriptikeeltes nagu JavaScript ja Python ning programmeerimiskeskkondades nagu Delphi, C ja Visual C++.

 

Kõige kuulsam programmeerimiskeel regulaaravaldiste kasutamise võimaluste poolest on Perl, kus saab väga lühidalt kirja panna keeruliste otsitavate sõnade mustreid.

 

Teisiti öeldes, regulaaravaldisega saab öelda otsimootorile milliseid sõnu on vaja otsida.

 

Üks kõige tavalisem regulaaravaldiste rakendamise viis on kontrollida, kas kasutaja poolt veebivormile sisestatud elektronpostiaadress vms. on korrektses vormis: kui on, siis jätkatakse mingi skripti täitmist, mis tegeleb nende andmetega edasi, kui ei ole, siis tekitatakse veateateaken, mis palub kasutajal viga parandada. Seega regulaaravaldised mängivad olulist rolli veebirakenduste otsuseid tegevates programmiosades.

 

Regulaaravaldisi saab kasutada ka algse teksti asendamisel uuega. Kõigepealt leitakse algtekstist see koht, mis vastab regulaaravaldise mustrile ning seejärel asendatakse selle koha peale mingi uus tekst ning algne tekst kustutatakse. Regulaaravaldisega sobinud �vana teksti� võib ka mitte kustutada, vaid salvestada muutujasse, et seda hiljem programmis kasutada.

 

Iga rakendus, mis tegeleb tekstiliste andmetega, saab kasu lõigata regulaaravaldistest. Näiteks WWW-s cgi-skriptid, mis puutuvad kokku mitmesugust liiki teksti ja andmetega, otsisüsteemid jms.

 

Kokkuvõtvalt võibki öelda, et regulaaravaldisi rakendatakse peaasjalikult otsimis- ja otsimis/asendamis-operatsioonides.

 

Keskmine arvutikasutaja tavaliselt ei kasuta ära regulaaravaldiste kogu võimsust, vaid tarvitab regulaaravaldisi ainult konkreetsete sõnade otsimiseks, jättes kõrvale erisümbolid (\ | ( ) [ ] { } ^ $ * + . ?). Näiteks, kui ei ole teada, kas tekstis esines sõna �colour� või �color�, siis otsitakse esimene kord ühte teine kord teist sõna, kuid sama tulemuse saab ka ühe korraga, kasutades otsimisel regulaaravaldist �colou?r�, kus �?� regulaaravaldises tähendab, et tähte �u� võib olla ja võib ka mitte olla selles sõnas.

 

Kui tavaline arvutikasutaja ei oskagi regulaaravaldistest puudust tunda, siis kogenud arvutispetsialistidele (nt. tarkvaraarendaja, süsteemiadministraator jt.) teeb regulaaravaldiste tundmine elu palju lihtsamaks. Arendajad kasutavad regulaaravaldisi tekstifaili parsimiseks, koodi parandamiseks; süsteemihaldurid aga logide läbi vaatamiseks, rutiinsete kohustuste automatiseerimiseks, võrguliiklusest volitamata tegevuse ilmingute avastamiseks jne.

 

Tegeledes dokumentide, sõnumite, logiandmete, failide jms. haldamisega, saab regulaaravaldisi kasutades aega oluliselt kokku hoida.

 

Kuigi paljud regulaaravaldiste kasutamist võimaldavad vahendid on *NIX�i päritolu on nad siiski kasutatavad juba ka paljudel teistel platvormidel, sealhulgas DOS/Windows ja MacOS. Alates JDK1.4-st on regulaaravaldised kasutatavad ka programmeerimiskeeles Java (pakett java.util.regex), kus on aluseks võetud Perl�is kasutatav süntaks.


 

2.3. Jokkerid

 

Jokker (metamärk,  wildcard) on märk, millega võib nt. otsingul asendada teisi märke.

 

Kõige tavalisemad ja kergemini pruugitavamad jokkerid standardses UNIX�i käsuinterpretaatoris on �?� ja �*� [7], mida kasutatakse näiteks käskudes ls, cp, mv, rm. Jokkerid muudavad UNIX�is failidega seotud operatsioonide kirjutamise lihtsamaks. Tihti arvatakse ekslikult, et kasutatakse regulaaravaldisi, mida aga jokkeritega moodustatud string ei ole.

 

Küsimärk (�?�) asendab mistahes (täpselt) ühte sümbolit. Näiteks avaldisega p?pe sobivad pipe, pupe, p2pe, aga ei sobi pulpe.

 

Tärn (�*�) asendab null kuni mitu mistahes sümbolit. Näiteks avaldisega p*pe sobivad ppe, pupe, pulpe ja isegi party tape.

 

Jokkereid saab ühes failinimes omavahel kombineerida. Näited:

·        rm *.t?t ¾ kustutab kõik failid, mille failinimed lõpevad �.t<mingi sümbol>t�, näiteks Oscar.tnt, Wilde.txt, Melmoth.tot.

 

·        mv Use*.txt_? Usenet_Files ¾ tõstab kõik failid, mille nimed algavad sõnaga �Use� ja lõpevad �.txt_<mingi sümbol>� kataloogi Usenet_Files, näiteks kuuluvad tõstmisele Use100.txt_1, Use10.01.txt_a, Use.txt_0.

 

Kuigi ka regulaaravaldised lubavad sümbolit või mingit stringi osa asendada erisümboli(te)ga ei ole antud juhul tegemist n.ö �pärisregulaaravaldistega�, kuid idee on sama. Regulaaravaldiste korral tõlgendatakse erisümboleid teist moodi ning neil samadel sümbolitel (*, ?) on teine tähendus.


3. Regulaaravaldiste koostamine

 

3.1. Süntaks operatsioonisüsteemis UNIX

 

Nagu juba öeldud peatükis 2., on *NIX see operatsioonisüsteemide perekond, mis kasutab väga laialt regulaaravaldiste aparatuuri.

UNIX'i regulaaravaldis [4][8][9] koosneb tähtedest (alfabeet), numbritest ja erisümbolitest ehk metasümbolitest. Metasümbolid on järgmised:

 

\ | ( ) [ ] { } ^ $ * + . ?

 

Esimeses peatükis toodud definitsiooni kohaselt regulaarvaldiste maailmas iga sümbol, mis ei ole metasümbol, sobib iseendaga (neid nimetatakse literaalseteks sümboliteks), s.t regulaaravaldisele abc vastab sõna abc. Enamikul lihtsatel juhtudel kasutataksegi regulaaravaldistena ainult tähti ja numbreid. Üks väga eriline sümbol on kurakaldkriips (�\�), see muudab iga metasümboli literaalseks sümboliks ja tavalise tähe jälle metasümboliks või sümbolite järjendiks (nt. \d, \D, \s, \S, \w, \W programmeerimiskeeles Perl või \<, \>, \(, \) käsus grep).

 

Märkus. Järgnevates näidetes pakutakse regulaaravaldisega sobivate sõnade kandidaatideks ainult neid sõnu, mida antud regulaaravaldis täpselt kirjeldab, mitte neid, milles sisaldub regulaaravaldisega kirjeldatud sõna. Alljärgnevalt toodud näites võib seega regulaaravaldisele tekstist otsimisel vastata peale sõna �cat� ka �catalog�, �catherine�, �sophisticated�.

 

regulaaravaldis: cat

sobiv sõna: cat

 

Metasümbolitest tekitab kõige rohkem segadust punkt (�.�). Sellele sümbolile ei vasta mitte punktimärk (�.�), vaid mistahes (ainult üks) sümbol (va reavahetus). Näiteks regulaaravaldisele 1.23 ei vasta mitte ainult reaalarv 1.23, vaid ka 1x23, 1 23, 1-23. Et aga regulaaravaldis leiaks ainult ujukomaarvu 1.23, tuleb kurakaldkriipsuga punktilt ära võtta tema eritähendus. Seega saame ainult ujukomaarvu 1.23 sisaldavaid sõnu ära tundvaks regulaaravaldiseks 1\.23 .

 

regulaaravaldis: t.n

sobivad sõnad: tan, ten, tin, ton, t n, t#n, tpn, t.n

 

Metasümbol tärn (�*�) tähendab, et temale eelnevat sümbolit võib vastavas sõnas olla null või mitu korda. Metasümbol pluss (�+�) tähendab, et temale eelnevat sümbolit võib vastavas sõnas olla üks või mitu korda. Seega regulaaravaldisele c* võib vastata ka tühisõna (c võtta null korda) ning me saame, et kõik sõnad vastavad sellele avaldisele, sest tühisõna sisaldub igas sõnas. Näiteks sõnas �go� sisaldub kolm tühisõna (enne g, g ja o vahel, peale o). Regulaaravaldis c+ tunneb ära kõik sõnad, milles on vähemalt üks täht c.

 

regulaaravaldis: ab*c

sobivad sõnad: ac, abc, abbc, abbbbbbbc

 

regulaaravaldis: ab+c

sobivad sõnad: abc, abbc, abbbbbbbc

ei sobi: ac

 

regulaaravaldis: cyclo.*ane

sobivad sõnad: cyclodecane, cyclohexane, cyclones drive me insane, cycloane

 

regulaaravaldis: cyclo�ane

sobivad sõnad: cyclodecane, cyclohexane

ei sobi: cyclones drive me insane, cyclopentane

 

regulaaravaldis: a\.*z

sobivad sõnad: az, a.z, a..z, a...z

 

regulaaravaldis: a.\*z

sobivad sõnad: ag*z, a5*z, a**z

 

regulaaravaldis: a\++z

sobivad sõnad: a+z, a++z, a+++z

ei sobi: az

 

regulaaravaldis: a\+\+z

sobiv sõna: a++z

 

Metasümbol küsimärk (�?�) tähendab, et temale eelnevat sümbolit võib vastavas sõnas olla null või üks kord.

 

regulaaravaldis: cows?

sobivad sõnad: cow, cows

 

regulaaravaldis: a.?e

sobivad sõnad: ae, ace, ale, axe

 

Metasümbolitena kasutatavad loogelised sulud (�{n,m}�) tähendavad, et konstruktsioonile {n,m} eelnevat sümbolit võib vastavas sõnas olla n kuni m korda. Tegemist on üldistava konstruktsiooniga: {0,1} on sama, mis �?�; {0,} on sama, mis �*�; {1,} on sama, mis �+�. Lisaks saab kasutada ilma komata varianti {n}, mis tähendab, et sellele eelnevat sümbolit võib esineda sõnas täpselt n korda.

 

Nurksulgudega (�[ ]�) ümbritsetud sümbolite hulgast võib vastavas sõnas esineda korraga ainult üks sümbol ja ainult nurksulgude seest. Kõiki sümboleid nurksulgude sees vaadatakse kui literaalseid sümboleid (kaasa arvatud metasümbolid). Kaks erisümbolit nurksulgude sees on sidekriips (�‑�), mis tähistab sümbolite vahemikku ([3-5], arvud 3st kuni 5ni ehk 3, 4 või 5), ja katus (�^�), mis tähendab eitust: sobivad kõik sümbolid, mis ei ole nurksulgude vahel ([^d], ükskõik milline sümbol v.a d).

 

regulaaravaldis: t[aeio]n

sobivad sõnad: tan, ten, tin, ton

 

Alljärgnevates näidetes on vahemiku moodustamisel aluseks võetud inglise tähestik, s.t sümboli sinna vahemikku kuuluvuse määrab ära inglise tähestikus (abc�xyz) olevate tähtede järjestus (nt. vahemikku [a‑z] kuuluvad kõik inglise tähestiku väiketähed, sest nad jäävad tähestikus a ja z vahele.

 

regulaaravaldis: [0-9]{3}[A-Z]{2}

sobivad sõnad: 123AB, 999XX

 

regulaaravaldis: [A-Za-z]+

sobivad sõnad: cow, Linus, Regular, expreSSion

ei sobi: 200, x-files, C++

 

regulaaravaldis: [^a-zA-Z0-9]+

sobivad sõnad: ¤%//&, +*.<>

ei sobi: 1.23, regular, expreSSion

 

Sulgudega ( ) saab moodustada alamavaldisi (grupeerida üksikud sümbolid suuremaks grupiks ning seejärel rakendada sellele grupile metasümboleid).

 

regulaaravaldis: ( ?ho)+

NB! Antud regulaaravaldises on enne küsimärki tühik.

Sobivad sõnad: ho, ho ho, ho ho ho, hohoho

 

Metasümbol püstkriips, toru (�|�) tähendab regulaaravaldises valikut, võib valida kas vasakpoolse või parempoolse alamavaldise või sümbolite jada vahel.

 

regulaaravaldis: cow(ard|age|boy|l)?

sobivad sõnad: cow, coward, cowage, cowboy, cowl

 

regulaaravaldis: t(a|e|i|o|oo)n

sobivad sõnad: tan, ten, tin, ton, toon

 

Kuna tavaliselt otsitakse regulaaravaldise poolt genereeritud sõnu tekstist ridade kaupa (eraldajaks reavahetuse sümbol), siis osutuvad kasulikeks metasümbolid katus (�^�) ja dollar (�$�), millest esimene väidab, et temast paremal olev avaldis on vahetult rea alguses, ja teine väidab, et temast vasakul olev avaldis on vahetult rea lõpus.

Need sümbolid omavad mõtte sellise otsimise korral, kus regulaaravaldisele vastav sõna võib esineda suurema sõna alamsõnana (vt. Märkust eespool). Sellisel juhul vastavad regulaaravaldisele ^The kõik read (kogu tekstirida), mis algavad sõnaga The.

 

3.2. Kokkuvõte metasümbolitest

 

. � punkt: tähistab suvalist sümbolit

[märgid] - suvaline märk (üks) loetelust

[algusmärk-lõppmärk] - suvaline märk (üks) sellest vahemikust

[^märgid] - suvaline märk (üks), mis ei kuulu loetelu hulka

märk* - null või enam korda seda märki

^avaldis - avaldis asub rea alguses

avaldis$ - avaldis asub rea lõpus

märk+ - üks või enam korda seda märki

märk? - null või üks korda seda märki

avaldis|avaldis - eelnev või järgnev regulaaravaldis

(avaldis) - sulud: grupeerib regulaaravaldisi

märk{n,m} ‑ n kuni m korda seda märki

 

3.3. Näiteid

 

Regulaaravaldiste näiteid on võetud allikast [4].

 

Regulaaravaldisi saab rakendada mingi programmi (kasutajapoolse)sisendi kontrollis, kus sisend peab vastama mingile mustrile.

 

Kui sisendiks on elektronposti aadress, siis tuleb kontrollida, et enne sümbolit �@� peab olema mingi tähtede/numbrite jada(d) (mis võivad olla eraldatud punktiga), peale @‑märki peab tulema samasuguse mustriga sümbolite jada ning lõpuks veel peale punkti kahe või kolme sümboliline riigitunnus, nt. user@host.com, eesnimi.perenimi@math.ut.ee, jne: 

 

[a-z0-9_-]+(\.[a-z0-9_-]+)*@[a-z0-9_-]+(\.[a-z0-9_-]+)*\.[a-z]{2,3}

 

NB! Vahemiku [a-z] moodustamisel on aluseks võetud inglise tähestik (täpsemalt ASCII-märgistik) ning seega hõlmaks kõiki inglise keele (väike)tähti. Kui märgistikus on tähed järjestatud nii nagu eesti tähestikus, siis oleks õige vahemik [a-y].

 

Elektronposti aadressi kontroll koos isiku ees- ja perekonnanimega selle ees; sobima peavad: Jaan Hunt <j.h@mail.ee> ,"Joe Doe" <joe@host.name.fi> , jne.

 

("?[a-zA-Z]+"?[ ]*)+<[a-z0-9_-]+(\.[a-z0-9_-]+)*@[a-z0-9_-]+(\.[a-z0-9_-]+)*\.[a-z]{2,3}>

 

Protokolli tüübi (vähemalt kaks sümbolit pikk ning lõppeb sümbolitega �://�) kontroll, sobima peavad näiteks veebipõhised protokollid nagu http://, ftp://, https:// jms.

 

[a-z]{2,}://

 

Programmerimiskeele C/C++ lähtetekstis olevad include-laused peavad asuma rea alguses, kus #include�le järgneb üks või mitu tühikut ning peale seda asub jutumärkide või väiksemkui/suuremkui-märkide vahel tekst, mis ei tohi enam sisaldada neid märke (><"), nt. #include <ctype.h>, #include   "in_all.h", jne.

 

^#include[ ]+[<"][^><"]+[">]

 

Reaalarvulist sisendit võib kontrollida järgmise regulaaravaldisega (reaalarv võib alata pluss- või miinusmärgiga või mitte kummagagi, siis järgneb, kas täisarv vahemikust 1 kuni 9 ja seejärel kuitahes palju täisarve vahemikust 0 kuni 9, või arv 0, peale seda võib esineda punkt ja vähemalt üks täisarv vahemikust 0-9):

 

(\+|-)?([1-9][0-9]*|0)(\.[0-9]+)?


 

3.4. Jokkerite teisendus regulaaravaldisteks

 

Regulaaravaldised on väga sarnased punktis 2.3. kirjeldatud jokkeritega.

 

Viimaseid saab väga lihtsalt teisendada regulaaravaldisteks [4].

Jokkerile �*� vastab regulaaravaldis �.*� .

Jokkerile �?� vastab regulaaravaldis �.� .

Kasutatud metasümbolite ette panna kurakaldkriips.

 

Näiteks *.jpg teisendub regulaaravaldiseks kujul �.*\.jpg�.


4. Regulaaravaldiste kasutamine

 

4.1. UNIX�i korraldus grep

 

UNIX�is kasutatav käsk grep on kõige lihtsam vahend regulaaravaldiste kasutamiseks. Grep võimaldab moodustada lihtsaid regulaaravaldisi ning otsida mustrile vastavaid sõnu etteantud failide hulgast. Grep on n.ö sissejuhatus awk, sed�i ja Perl�i edasiõppimisel.

 

UNIX�i tekstitoimetis ed saab kasutada konstruktsiooni g/re/p, mis globaalselt (g) otsib üle kogu teksti regulaaravaldisega (re, regular expression) sobivaid sõnu ning väljastab (p, print) read, mis sisaldavad leitud sõna. Seda konstruktsiooni läks vaja nii tihti, et tehtigi sellele omaette käsk UNIX�is, nimega grep. Niipalju siis selle käsu tekkeloost. [10]

 

Tavaliselt ja kõige lihtsamalt kasutatakse grep käsku nii:

 

grep foo file

 

See väljastab kõik read failist file, mis sisaldasid (ka alamstringina) sõna foo.

 

Üldine kasutus:

 

grep [võtmed] �regulaaravaldis� [failid]

 

Kui faile, kust otsitakse, on rohkem kui üks, siis väljastatakse iga rea (kirje) ette ka failinimi, kust sõna leiti.

 

Regulaaravaldis on soovitav panna ülakomade vahele, et käsuinterpretaatori eest varjata erisümboleid. Grep saab aru järgmistest metasümbolitest: *.$^[]\

Neid nimetatakse ka traditsioonilisteks metasümboliteks. Grupeerimiseks saab lisaks kasutada ka sulge, kui nende ette kirjutada kurakaldkriips \( ja \).

 

 

Võtmeid [11]:

·        -c - näitab ainult leitud kirjete arvu, kirjeid endid ei näita

·        -h - ei näita failinimesid (mitmest failist otsimisel)

·        -i - ei tee vahet suurtel ja väikestel tähtedel

·        -l - näitab ainult failinimesid (ühekordselt), kirjeid endid ei näita

·        -n - lisab rea numbri väljundkirjete algusesse

·        -v - näitab ainult neid ridasid, milles ei ole vastavat kirjet

·        -x - näitab ridu, mis on täpselt (s.t kogu rida) regulaaravaldisega ära kirjeldatud (nt. regulaaravaldisele cat vastab rida, milles sisaldub ainult sõna cat, mitte catalog jms., sest seal on veel lisaks sümboleid, mida regulaaravaldis ei kirjeldanud); ei otsita sõna kui alamstringi

·        -w - näitab ridu, kus asub regulaaravaldisega täpselt ära kirjeldatud sõna (s.t inimkeele sõna, mis tekstis on tavaliselt ümbritsetud tühikutega või lõpeb kirjavahemärgiga). Kui võtit -w mitte kasutada, saab sama efekti, kui ümbritseda regulaaravaldis märkidega \< (nt. �\<fle� väidab, et sõna algab tähtedega f, l ja e) ja \> (�fle\>� sõna lõpeb tähtedega f, l ja e).

 

Näiteks kui oletada, et on olemas tohutu hulk elektronposti faile ning on teada, et seal asub üks kiri, kus oli juttu mingil konkreetsel teemal (meeles on tunnussõna) ning on vaja see kiri üles leida, siis tuleb minna sinna kataloogi, kus kirjad asuvad, ja anda käsk:

 

grep �n see_sõna *

 

siis otsitakse kõigist kirjafailidest (seda tähendab jokker �*�) otsitavat sõna. Kui midagi leitakse, siis väljastatakse, millises failis see sõna oli ja rida, kus see sõna oli.

 

Peale korraldust

 

grep 'hello\.gif' *.html

 

otsitakse kõigist failidest, mille nimed lõppevad .html, teksti hello.gif.

 

Kui on vaja leida, millistes html-failides on juttu ussidest, nii et see sõna esineks kindlasti ka pealkirjas, s.t märgendi <title> ja veel mingite tähtede järel (�.*�), siis tuleb kirjutada

 

grep -i '<title>.*ussid' *.html

 

Näited grep�i kasutamise kohta baseeruvad allikal [1].

 

Kui on olemas näiteks kalameeste tabel kalastus, kus kalamehe nimi ja kalade arv on eraldatud alakriipsude jadaga kujul:

 

kalamees    kalade arv

Priit_______1

Mart______12

Andres_____45

Konstant___34

Tibu_______3

Miima_____100

Mari-Liis__100

 

Oma suurest tabelist alla 10-ne kala püüdnud kalastajate leidmiseks, tuleb kasutada järgmist regulaaravaldist �_.$�, mis tähendab, et rea lõpus ($) asuvad kõrvuti alakriips �_� ja üks suvaline sümbol (.), �>� enne käsku grep tähistab käsurea viipa:

 

> grep �_.$� kalastus

Täpsem oleks grep '_[0-9]$' kalastus

            Priit_______1

            Tibu_______3

 

Järgnevad näited on sellise teksti alusel (fail kohad):

 

Tartu 1437

Helsinkki 1960

Yellowstone 1903

Tokio 1990

Praha 1400

Pariis 1500

 

 

Leiame kõik kahekümnenda sajandi aastaarvud:

 

> grep �19..� kohad

            Helsinkki 1960

Yellowstone 1903

Tokio 1990

 

Leiame kõik u või o lõpuliste kohanimedega read:

 

> grep �[uo] � kohad

NB! Peale ] on tühik.

 

Tartu 1437

Tokio 1990

 

Et täpse otsinguga (võti -x) saada sama tulemust peame regulaaravaldises ära kirjeldama kogu rea mustri: grep -x '.*[uo] [0-9]*' kohad. Käsk grep -x '[uo] ' kohad ei annaks tulemust, kuna ühtegi rida, mis sisaldaksid �u � või �o �, ei leidu.

 

Leiame kõik mitte i, e või u lõpuliste kohanimedega read:

 

            > grep �[^ieu] � kohad

          NB! Peale �]� on tühik.

 

Tokio 1990

Praha 1400

Pariis 1500

 

Leiame tähega P algavad viietähelise kohanimega read:

 

            > grep �^P.... � kohad

          NB! Peale viimast �.� on tühik.

Praha 1400

 

4.2. UNIX�i korraldus egrep

 

UNIX�i käsu egrep (extended grep) eeliseks on see, et lisaks traditsioonilistele metasümbolitele (grep) saab ta aru ka järgnevatest:

 

?|+(){n,m}

 

Seega on võimalik moodustada paindlikumaid regulaaravaldisi.

 

Näited egrep�i kasutamise kohta baseeruvad allikal [1].

 

Otsime kõik täpselt 100 kala kinni püüdnud ja tähega s lõppevad kalamehed. Siin on ülihea kasutada �+� võimalusi, sest �_� on sisestatud suvaline arv (kuid vähemalt üks):

 

            > egrep �s_+100$� kalastus

            Mari-Liis_______100

 

Kui on teada, et tekstis esineb nimi, mida võib kirjutada sidekriipsuga või ilma, siis viited sellele nimele leiame, kasutades ära �?� võimalusi:

 

            > egrep �Mari-?Liis� kalastus

            Mari-Liis_______100

 

Kui otsida kalameeste nimesid, mis on pikemad kui 7 tähte, siis

 

            > egrep �^[^_]{8,}_� kalastus

            NB! �^� on kaks tähendust: reaalgus ja eitus.

Konstant________34

Mari-Liis_______100

 

Oletame, et meil on tekstifailis mobiiltelefonide numbrid. Näiteks võiks faili numbrid sisu välja näha selline:

 

05089654 - Kaupo Kurg

056626410 - Janno Metsa

05245689 - Mati Hunt

055123456 ‑ Jaan Ots

 

Meil on vaja välja sorteerida EMT numbrid. Teame, et nad algavad numbritega 050, 051, 052 ja 053. Selleks on otstarbeks kasutada �|� teenust:

 

> egrep �(^050)|(^051)|(^052)|(^053)� numbrid

05089654 - Kaupo Kurg

05245689 - Mati Hunt

 

4.3. Elektronposti töötlemise programm Procmail

 

Procmail [12] on elektronposti töötlemise programm, millega saab sissetulevaid kirju filtreerida. Ta töötab operatsioonisüsteemis UNIX ning ta tuleb sinna ka installeerida.

 

Procmaili kasutatakse postimasinasse tulnud kirjade kasutajate vahel laiali jaotamiseks.

 

Kasutajal on võimalik häälestada Procmail nii, et talle saabunud elektronpost salvestatakse teatud tunnuste alusel kasutaja postikataloogi erinevatesse failidesse. Postikataloogi faile käsitleb Pine kirjakastidena. Lisaks on võimalik käivitada konfiguratsioonis näidatud tingimustel programme, näiteks selleks, et saabunud oluline post edasi saata mobiiltelefonile teatena.

 

Konfiguratsioonifailis ~/.procmailrc on kirjas reeglid, mille järgi saabuva elektronpostiga tegeldakse. Reegleid kirjutatakse järgmise süntaksi alusel:

 

0: [ võtmed ]

* tingimus

käsu rida

 

Tingimus esitatakse regulaaravaldisena, milles saab kasutada laiendatud metasümbolite hulka (nagu egrep�is).

 

Toome näiteks ühe reegli ja selgitame

 

:0 HB

* Z|zoo

ZOO

 

Reegli algust märgib :0, mille järele kirjutatakse võtmed.

Tingimust alustab tärn, millele järgneb regulaaravaldis.

'Z|zoo' tähendab, et reegel rakendub neile kirjadele, mille sisus (võti B) või päises (võti H) leidub regulaaravaldisega klappiv rida. Antud juhul klapivad stringe 'Zoo' või 'zoo' sisaldavad read.

Käsu reale kirjutatud stringi tõlgendatakse faili nimena, kuhu kiri salvestatakse. Antud juhul faili ZOO.

 

Konfiguratsioonifailis võib esitada mitmeid reegleid, mida kontrollitakse järgemisi. Tegutsetakse vastavalt esimesele sobivale, ignoreerides järgnevaid. Kui ükski reegel ei sobinud, tegutsetakse vaikimisi seatud tingimuste alusel (nii nagu enne, ilma .procmailrc failita). Konfiguratsioonifaili alguses saab defineerida mõned spetsiifilised keskkonnamuutujad:

 

·        MAILDIR - kasutaja postikataloog, kuhu tehakse kirjade failid (eelmises näites fail ZOO luuaksegi muutujaga MAILDIR määratud kataloogi)

·        DEFAULT - fail, kuhu salvestatakse kirjad, millele ühtegi reeglit ei rakendunud (vaikimisi on sellel väärtus ~/mbox)

 

Esitame ühe tervikliku näite, kuidas sorteerida saabunud kirju. Failidesse paigutamine toimub Subject, From ja Sender rea alusel. Kirjad, millele reeglid ei rakendu, salvestatakse faili allumatud. Vaikimisi kasutavad reeglid kirja päist (võtit H pole vaja kirjutada). Alljärgnev tekst kujutab endast faili .procmailrc sisu:

 

MAILDIR=$HOME/Mail

DEFAULT=$MAILDIR/allumatud

 

:0

* ^From.*kasutaja@ut.ee

kasutaja

 

:0

* ^Subject.*\[linux\]

LINUX

 

:0

* ^Sender.*owner-zoo-chat

ZOO-CHAT

 

Kui me tahame kirja edasi saata teisele e-posti aadressile, tuleb käsu rida alustada erisümboliga �!�:

 

:0 c

!minu@mail.ee

 

See faili .procmailrc sisu tähendab, et iga kiri (kuna tühjale regulaaravaldisele vastab iga sõna) saadetakse edasi aadressile minu@mail.ee ning koopia sellest (võti c) jäetakse ka siia (~/mbox).


 

4.4. Otsisüsteemid

 

Interneti otsimootorites regulaaravaldisi otseselt ei kasutata, küll aga on olemas jokkerite kasutamise võimalus.

 

AltaVista�s saab kasutada jokkerit �*�, millele on seatud järgmised piirangud:

tohib paikneda sõnas alles peale kolmandat sümbolit (Sel*zer)

asendab enda positsioonile 0-5 suvalist sümbolit. [13]

 

NorthernLight lubab kasutada kahte jokkerit: �*� (oma tavalises tähenduses, peale neljandat sümbolit) ja �%� (asendab ühe sümboli oma positsioonile; nagu �?�). [14]

 

Ka Yahoo�s on võimalik jokkerit �*� kasutada.

Google aga ei toeta jokkerite kasutamist.


 

5. Realisatsioon

 

Esimeses peatükis kirjeldatud regulaaravaldiste käsitlusele vastav realisatsioon on ka Internetti üles pandud [19].

 

Sellel veebilehel asub keeles Java realiseeritud programm, mis vastab küsimusele: kas antud sõna on olemas antud regulaarsele avaldisele vastavas sõnade hulgas.

 

Lehekülje eesmärk on anda regulaaravaldisi õppivatele tudengitele lihtne võimalus testida ja kinnistada oma teadmisi regulaaravaldiste alal lisaks loengus räägitule.

 

5.1. Kasutajaliides

 

Olemas on tekstilahtrid regulaaravaldise ja otsitava sõna sisestamiseks. Sisestuse lõpetamisel tuleb vajutada klahvi <enter> või klikkida nupule "Otsi sõna", et otsimisprogrammi käivitada.

 

Regulaaravaldiste üles kirjutamisel saab siin kasutada kolme n.ö tehet:

1) * (kordus, sama tähendus, mis UNIX�is), mis tähendab, et sümbolile '*' eelnevat tähte (regulaaravaldist) võib selle regulaaravaldise poolt ära tuntavates sõnades sisalduda null kuni mitu korda.

2) + (valik, nagu �|� UNIX�is), mis annab võimaluse valida kahe tähe (regulaaravaldise) vahel, millest üks või teine peab esinema selle regulaaravaldise poolt ära tuntavates sõnades antud positsioonil.

3) konkatenatsioon (nagu ikka korrutusmärki matemaatikas vaikimisi ei kirjutata) määrab ära tähtede järjestuse selle regulaaravaldise poolt ära tuntavates sõnades.

 

Tähestiku moodustavad inimkeele tähed ja numbrid. Tühja sõna tähistatakse: #.

 

NÄITEID regulaaravaldistest ja neile vastavatest sõnadest:

 

Regulaaravaldis         Sõnad

 


            (ab)*                            #, ab, abab, ababab, ...

            (ab)*c                          c, abc, ababc, abababc, ...

            (#+s)koor                     koor, skoor

            (ab+d)*                        #, ab, abab, d, dd, abdddddddab, ...

            (ab+d)c*                      ab, abcccc, d, dccccccccccc, ...

            (v+r)(edel+ool)             vedel, vool, redel, rool .

 

Kui sõna ei kuulu regulaaravaldise poolt genereeritud keelde, siis antakse väljundiks see mittesobinud sõna, kus sinise värviga on tähistatud see osa sõnast, mis sobis regulaaravaldise mustriga (maksimaalselt) ning punasega see osa, mis ei sobinud.

 

Kui sõna sobis antud regulaaravaldisega, antakse ka vastav teade. Kui regulaaravaldis on moodustatud ebakorrektselt antakse samuti vastav veateade. Enne otsima asumist peavad sisestuse lahtrid olema täidetud, tühju lahtreid ei aktsepteerita. Otsitakse täpselt seda sõna, mida regulaaravaldis kirjeldab, mitte alamsõna.

Kasutajaliides näeb välja selline:

 

5.2. Realiseerimisest

 

Peale kasutaja poolt sisestatud regulaaravaldise korrektsuse kontrolli teisendatakse see pööratud poola kujule, et oleks lihtne kindlaks teha peatehe ja operandid. Seejärel saab antud regulaaravaldisele moodustada vastava lõpliku automaadi, mis aktsepteerib sedasama keelt, mille defineerib regulaaravaldis.

 

Seda mismoodi regulaaravaldisele seatakse vastavusse automaat on kirjeldatud jaotises 1.4. Igale regulaaravaldises esineda võivale operatsioonile seatakse vastavusse lõplik automaat. Kogu avaldisele vastab lõplike automaatide lihtne kompositsioon. Korduvatele alamavaldistele seatakse vastavusse vastavalt mitu lõplikku automaati, mingit optimeerimist siin ei toimu.

Nii saadud lõplik automaat pole determineeritud, kuna me kasutame juba komponentideks olevates lõplikes automaatides mittedetermineeritust.

 

Vastavalt antud sõnale hakatakse automaati kui graafi sügavuti läbima. Kui jõutakse automaadi lõppolekusse vaadatakse, kas terve sõna on samuti lõpuni vaadeldud, kui on, siis sõna sobis, kui ei olnud, siis läbitakse automaat teist teed pidi. Kui kõik sõnaga sobivad teed on tulemuseta läbi vaadatud, siis sõna ei kuulu aktsepteeritavate hulka.


Kokkuvõte

 

Antud semestritöö on mõeldud kasutamiseks abivahendina regulaaravaldiste maailma tundma õppimisel, kus lisaks teoreetilisele osale on loodud võimalus kasutada veebirakendust regulaaravaldiste ja vastava regulaarse keele mõistmiseks.

 

Regulaaravaldis on matemaatiline konstruktsioon formaalsete keelte ja automaatide teooriast. Ta on sümbolite jada, mis kirjeldab ära sõnade hulga (regulaarse keele). Regulaarset keelt aktsepteerib lõplik automaat.

 

Regulaaravaldist võib vaadelda kui tekstilist mustrit, mida saab kasutada mallvõrdlemise vahendina. Regulaaravaldised on seotud peaaegu kõigi UNIX-laadsetel operatsioonisüsteemidel baseeruvate tekstiga manipuleerimisvahenditega.

 

Regulaaravaldisi kasutatakse peamiselt mingi stringi(de) otsimiseks tekstist vastava mustri alusel, mis seda stringi kirjeldab.


Kirjandus

 

1.      Regulaaravaldised.
http://kuutorvaja.eenet.ee/programmeerimine/regulaaravaldised.html - 05.02.2002

2.      Waclena, K. Regular Expressions.
http://www.lib.uchicago.edu/keith/tcl-course/topics/regexp.html - 20.02.2002

3.      Vaswani, V., Kamath, H. So What's A $#!%% Regular Expression, Anyway?!
http://www.devshed.com/Server_Side/Administration/RegExp/page1.html 05.02.2002

4.      Borsodi, J. Regular Expressions explained.
http://zez.org/article/articleview/11/ - 05.02.2002

5.      Roven, C. Geek Talk: The Regular Expression Rundown.
http://www.wired.com/news/topstories/0,1287,6254,00.html - 05.02.2002

6.      Mastering Regular Expressions.
http://www.oreilly.com/catalog/regex/desc.html - 05.02.2002

7.      Wildcards in Unix. http://help.acusd.edu/Articles/wildcards.shtml - 05.02.2002

8.      Franklin, C., Wisniewski, G. Perl Regular Expression Tutorial.
http://virtual.park.uga.edu/humcomp/perl/regex2a.html - 05.02.2002

9.      Chng, B. Matchmaking with regular expressions.
http://www.javaworld.com/javaworld/jw-07-2001/jw-0713-regex.html - 05.02.2002

10.  What is the origin of the name "grep"?
http://www.faqs.org/faqs/usenet/faq/part1/section-21.html - 05.02.2002

11.  UNIX�i manuaal: grep

12.  Procmail.
http://kuutorvaja.eenet.ee/kasutamine/suhtlus/email/procmail/procmailrc.html
05.02.2002

13.  Using the wild card (*).
http://help.altavista.com/adv_search/ast_ma_wildcard - 05.02.2002

14.  Optimize Your Search.
http://www.northernlight.com/docs/search_help_optimize.html - 05.02.2002

15.  Villems, A. Regulaarsed avaldised.
http://erasmus.cs.ut.ee/~jesmin/stuff/anne/E-reglaaravaldis2909.doc - 05.02.2002

16.  Matuszek, D. Regular expressions.
http://www.netaxs.com/people/nerp/automata/regexp0.html - 05.02.2002

17.  Roos, M. Regulaarsest avaldisest mittedetermineeritud automaadi moodustamine.
http://www.cs.ut.ee/~mroos/transl/ - 05.02.2002

18.  Ramsay, S. Using Regular Expressions.
http://etext.lib.virginia.edu/helpsheets/regex.html - 22.02.2002

19.  Sang, V. Regulaaravaldised. http://www.math.ut.ee/~veikos/regexp/


Regular Expressions

 

Veiko Sang

 

Abstract

 

A regular expression is a text pattern consisting of a combination of alphanumeric characters and special characters ( \|()[]{}^$*+.? ) known as metacharacters. A close relative is in fact the wildcard expression, which are often used in file management.

 

The pattern is used to match against text strings. The result of a match is either successful or not. Then we might substitute new text in the place of the text matched by a regular expression, save the matched text in a variable for later use, execute a new program when we see a correct match and so on.

 

Their use has become so widespread that they appear in configuration files, mail filters, text editors, and any number of programming languages. Any application that acts on text may very well harness their power.

 

Regular expressions constitute a syntax which many languages and tools (originally in UNIX) support. In this term paper there are introduced the syntax, how to build and how to use regular expressions.

 

There is also described the notation of regular expressions in the formal language theory and due to that an implementation (Java applet) is given for students to test themselves if they understood the subject-matter.


Lisa 1. Formaalsete keelte teoorias esinevate regulaaravaldiste poolt genereeritud keelt ära tundva Java rakendi lähtetekst

 

import java.util.Stack;

import java.util.Vector;

/*

Klass, kuhu isendeid ei looda ning mis sisaldab ainult klassimeetodeid,

mis on m6eldud tegutsema abimeetoditena, kontrollides kasutaja poolt

antud sisendit, parandades ja muutes seda edasi t88tlemiseks

vajalikule kujule. Samuti regulaarse avaldise poolt genereeritud

vastava automaadi leidmise ja antud sõna otsimise meetodid.

*/

public class AbiMeetod{

//-----------------------------------------------------------------------------

final static char KORRUTUSM2RK = '.';

final static char TYHI = '<';  //tyhikaar automaadis

final static char PUUDUB = '>';  //kaare puudumine automaadis

final static char TYHIS6NA = '#';

static int id;  //igale olekule automaatis oma unikaalne ID

/*

Automaadist tehtud otsingute ajalugu, kirjed kujul

'<id><sellest olekust otsitav s6na>', selleks, et samast kohast ei

otsitaks enam teist korda sama s6na

*/

static Vector tehtudOtsingud;

//-----------------------------------------------------------------------------

/*

Kasutaja poolt sisestatud reg.av kontrollimine. Tulemuseks veateade

v6i vastasel juhul "ok"+"ilma tyhikuteta sisend(regav)".

*/

public static String regavKontroll(String sisend){

  if (sisend.startsWith("+")||sisend.startsWith("*")||

    sisend.endsWith("+")) {

      return "Ootamatud sümbolid regulaaravaldise alguses/lõpus";

  }

  int suluLoendur = 0;

  for (int i=0;i<sisend.length();i++){

    char m2rk = sisend.charAt(i);

    if (Character.isWhitespace(m2rk)) {//tyhiku emaldamine

      sisend=new String(sisend.substring(0,i)+sisend.substring(i+1));

      i--;

      continue;

    }

    if (i>0) {//symbolid, mis ei saa k6rvuti olla

      String abi = new String(sisend.substring(i-1,i+1));

      if (abi.equals("()")||abi.equals("(+")||abi.equals("+)")||

          abi.equals("++")||abi.equals("**")||abi.equals("+*")||

          abi.equals("(*")

         ){

        return "Ootamatud sümbolid regulaaravaldises: "+abi;

      }

    }

    if (Character.isLetterOrDigit(m2rk)||m2rk==TYHIS6NA||

        m2rk=='*'||m2rk=='+')

      continue;//aktsepteeritud symbolite korral

    if (m2rk=='(') {

      suluLoendur++;

      continue;

    }

    if (m2rk==')') {

      suluLoendur--;

      if (suluLoendur<0)

        return "Sulgude paarsuse viga regulaaravaldises!";

      continue;

    }

    return "Ootamatu sümbol regulaaravaldises: "+(new

      Character(m2rk)).toString();

  }//for

  if (sisend.equals(""))

    return "Regulaaravaldist pole!!!";

  if (suluLoendur!=0)

    return "Sulgude paarsuse viga regulaaravaldises!";

  return "ok"+sisend;

}//regavKontroll() l6pp

//-----------------------------------------------------------------------------

/*

Kuna reg.avaldise analyysimiseks tuleb arvestada ka

korrutamistehetega, siis tuleb need 'k2sitsi' lisada, kuna

kasutaja neid sisestama ei pea. Tulemuseks korrutusm2rkidega

sisend(reg.av).

*/

public static String lisaKorrutusm2rgid(String sisend){

  for (int i=1;i<sisend.length();i++){

    char vasak = sisend.charAt(i-1);

    char parem = sisend.charAt(i);

    if ((vasak=='*'&&parem=='(')||(vasak==')'&&parem=='(')||

        ((Character.isLetterOrDigit(vasak)||vasak==TYHIS6NA)

          &&(Character.isLetterOrDigit(parem)||parem==TYHIS6NA))||

        (vasak=='*'&&(Character.isLetterOrDigit(parem)||

          parem==TYHIS6NA))||

        ((Character.isLetterOrDigit(vasak)||vasak==TYHIS6NA)&&

          parem=='(')||

        (vasak==')'&&

          (Character.isLetterOrDigit(parem)||parem==TYHIS6NA))

       ){

      String m=(new Character(KORRUTUSM2RK)).toString();

      sisend=new String(sisend.substring(0,i)+m+sisend.substring(i));

      i++;

    }

  }//for

return sisend;

}//lisaKorrutusm2rgid() l6pp

//-----------------------------------------------------------------------------

/*

Kas esimene tehe on 'k6vem' kui teine? ehk kas esimene tehe on

prioriteedilt eespool teisest. Siin ka sulud viidud tehetega samasse

prioriteedi j2rjekorda.

*/

public static boolean prioriteet(char esimene, char teine){

  if ((esimene=='*'&&teine==KORRUTUSM2RK)||

      (esimene=='*'&&teine=='+')||

      (esimene==KORRUTUSM2RK&&teine=='+')||

      (esimene==teine&&esimene!='(')||

      (esimene=='*'&&teine==')')||

      (esimene==KORRUTUSM2RK&&teine==')')||

      (esimene=='+'&&teine==')')

     ){

    return true;

  }

  return false;

}//prioriteet() l6pp

//-----------------------------------------------------------------------------

/*

Teisendab kasutaja poolt sisestatud infixkujus oleva reg.avaldise

postfixkujusse, selleks, et hiljem programselt teada saada peatehe ja

vastavad operandid. Algoritm aadressilt:

http://mail.tud.ttu.ee/material/taivo/Programmimine%20II/IDK3420-5.doc

*/

public static String infix_to_postfix(String infix){

  String postfix = new String(); //tulemus postfixkujus

  Stack tehteMag = new Stack(); //tehteid hoitakse magasinis

  char m2rk;

  char tipum2rk; //magasini tipus olev tehe v6i sulg

  for (int i=0;i<infix.length();i++){

    m2rk=infix.charAt(i);

    if(Character.isLetterOrDigit(m2rk)||m2rk==TYHIS6NA)

      postfix=new String(postfix+(new Character(m2rk)).toString());

    else{  //m2rk on tehe v6i sulg

      while (!tehteMag.empty()&&

             prioriteet(((Character)tehteMag.peek()).charValue(),m2rk)

            ){

        tipum2rk=((Character)tehteMag.pop()).charValue();

        postfix=new String(postfix+(new

                           Character(tipum2rk)).toString());

      }//while

      if (tehteMag.empty()||m2rk!=')')

        tehteMag.push(new Character(m2rk));

      else

        tipum2rk=((Character)tehteMag.pop()).charValue();

    }

  }//for

  while (!tehteMag.empty()){

    tipum2rk=((Character)tehteMag.pop()).charValue();

    postfix=new String(postfix+(new Character(tipum2rk)).toString());

  }//while

  return postfix;

}//infix_to_postfix() l6pp

//-----------------------------------------------------------------------------

/*

Teisendab postfixkujus oleva avaldise puukujule, sest seda on

lihtsam hiljem rekursiivselt l2bida ja teha vastavaid

t88tlusoperatsioone.

*/

public static Tipp tehaPuu(String postfix){

  Vector t88riba = new Vector(postfix.length());

  for (int i=0;i<postfix.length();i++){

    t88riba.addElement(new Character(postfix.charAt(i)));

  }

  char m2rk;

  Tipp lisatipp,vasak,parem;

  for (int i=0;i<t88riba.size();i++){

    m2rk = ((Character)t88riba.elementAt(i)).charValue();

    if (Character.isLetterOrDigit(m2rk)||m2rk==TYHIS6NA){

      t88riba.removeElementAt(i);

      t88riba.insertElementAt(new Tipp(m2rk,null,null),i);

    }

    else

      if (m2rk=='*'){//*-tehtel on vasakul 1 operand

        Tipp alluv=(Tipp)t88riba.elementAt(i-1);

        t88riba.removeElementAt(i-1);

        lisatipp=new Tipp(m2rk,alluv,null);

        t88riba.removeElementAt(i-1);

        i--;

        t88riba.insertElementAt(lisatipp,i);

      }

      else{//+ ja kor.tehtel on vasakul 2 operandi

        vasak=(Tipp)t88riba.elementAt(i-2);

        t88riba.removeElementAt(i-2);

        parem=(Tipp)t88riba.elementAt(i-2);

        t88riba.removeElementAt(i-2);

        lisatipp=new Tipp(m2rk,vasak,parem);

        i-=2;

        t88riba.removeElementAt(i);

        t88riba.insertElementAt(lisatipp,i);

      }

  }//for

  //t88ribale j22b nyyd ainult valmis puu juur

  return (Tipp)t88riba.elementAt(0);

}//tehaPuu() l6pp

//-----------------------------------------------------------------------------

/*

Saab ette reg.avaldisest tehtud puu, kus vahetippudes on tehted ja

lehtedes on t2hed, numbrid. Sellest tehakse mittedetermineeritud

automaat, mille l2bimisel saab leida antud reg.av poolt 2ra tuntavaid

s6nu. Algoritmi idee aadressilt:

http://www.cs.ut.ee/~mroos/transl/

*/

public static Automaat teeAutomaat(Tipp juur){

  Olek algus,l6pp;

  Automaat esimeneatm,teineatm;

  if (juur.votaNimi()==TYHIS6NA){

    l6pp=new Olek(id,PUUDUB,null,PUUDUB,null);

    id++;

    algus=new Olek(id,TYHI,l6pp,PUUDUB,null);

    id++;

    return new Automaat(algus,l6pp);

  }

  if (Character.isLetterOrDigit(juur.votaNimi())){

    l6pp=new Olek(id,PUUDUB,null,PUUDUB,null);

    id++;

    algus=new Olek(id,juur.votaNimi(),l6pp,PUUDUB,null);

    id++;

    return new Automaat(algus,l6pp);

  }

  if (juur.votaNimi()=='+'){

    esimeneatm=teeAutomaat(juur.votaEsimAlluv());

    teineatm=teeAutomaat(juur.votaTeineAlluv());

    algus=new

     Olek(id,TYHI,esimeneatm.votaAlgOlek(),TYHI,teineatm.votaAlgOlek());

    id++;

    l6pp=new Olek(id,PUUDUB,null,PUUDUB,null);

    id++;

    esimeneatm.votaL6ppOlek().paneEsimKaar(TYHI);

    esimeneatm.votaL6ppOlek().paneEsimOlek(l6pp);

    teineatm.votaL6ppOlek().paneEsimKaar(TYHI);

    teineatm.votaL6ppOlek().paneEsimOlek(l6pp);

    return new Automaat(algus,l6pp);

  }

  if (juur.votaNimi()==KORRUTUSM2RK){

    esimeneatm=teeAutomaat(juur.votaEsimAlluv());

    teineatm=teeAutomaat(juur.votaTeineAlluv());

    algus=esimeneatm.votaAlgOlek();

    l6pp=teineatm.votaL6ppOlek();

    esimeneatm.votaL6ppOlek().paneEsimKaar(

        teineatm.votaAlgOlek().votaEsimKaar());

    esimeneatm.votaL6ppOlek().paneEsimOlek(

        teineatm.votaAlgOlek().votaEsimOlek());

    if (teineatm.votaAlgOlek().votaTeineKaar()!=PUUDUB){

      esimeneatm.votaL6ppOlek().paneTeineKaar(

          teineatm.votaAlgOlek().votaTeineKaar());

      esimeneatm.votaL6ppOlek().paneTeineOlek(

          teineatm.votaAlgOlek().votaTeineOlek());

    }

    return new Automaat(algus,l6pp);

  }

  else {  // *-juhtum

    esimeneatm=teeAutomaat(juur.votaEsimAlluv());

    l6pp=new Olek(id,PUUDUB,null,PUUDUB,null);

    id++;

    algus=new Olek(id,TYHI,l6pp,TYHI,esimeneatm.votaAlgOlek());

    id++;

    esimeneatm.votaL6ppOlek().paneEsimKaar(TYHI);

    esimeneatm.votaL6ppOlek().paneEsimOlek(l6pp);

    esimeneatm.votaL6ppOlek().paneTeineKaar(TYHI);

    esimeneatm.votaL6ppOlek().paneTeineOlek(esimeneatm.votaAlgOlek());

    return new Automaat(algus,l6pp);

  }

}//teeAutomaat() l6pp

//-----------------------------------------------------------------------------

/*

Ette antakse 'algolek'(automaadi algolek,kust 's6na' otsimist

alustatakse). 'tee' on selle jaoks, et leida pikim sobinud alams6na

's6nast' juhul kui s6na ise tervikuna ei sobinud antud reg.avaldisega.

'tee' peab meeles siiamaani l2bitud tee (v.a tyhis6nad), otsimise

alguses tee=="".

*/

public static boolean otsi(Olek algolek, String s6na, String tee){

  String otsing=String.valueOf(algolek.votaid())+s6na;

  if (tehtudOtsingud.contains(otsing))

    return false;

  else{

    tehtudOtsingud.addElement(otsing);

    boolean tulemus = false;

    if (algolek.votaEsimKaar()==TYHI)

      tulemus=otsi(algolek.votaEsimOlek(),s6na,tee);//esimene haru

    else {

      if (algolek.votaEsimKaar()==PUUDUB){

        if (s6na.equals(""))

          return true;

        else

          return false;

      }

      else{//oli t2hega kaar

        if (s6na.equals(""))

          return false;

        else{

          if (s6na.charAt(0)==algolek.votaEsimKaar()){

            tee=new String(tee+(new

                     Character(s6na.charAt(0))).toString());

            if (tee.length()>RegexpApplet.pikimAlamS6na.length())

              RegexpApplet.pikimAlamS6na=tee;

          return otsi(algolek.votaEsimOlek(),s6na.substring(1),tee);

          }

        }

      }

    }

  if (tulemus==true)

    return true;

  if (algolek.votaTeineKaar()!=PUUDUB)

    return otsi(algolek.votaTeineOlek(),s6na,tee);//teine haru

  return false;//1. ega 2.harust ei saanud enam edasi minna

  }//else

}//otsi() l6pp

//-----------------------------------------------------------------------------

}//class AbiMeetod l6pp

###############################################################################

import java.awt.*;

import java.awt.event.*;

import java.applet.Applet;

import java.util.Vector;

 

public class RegexpApplet extends Applet implements ActionListener{

 

final static int PIKKUS = 40;//sisendi pikkus symbolites

static byte regavOk = 0;//kas reg.av sisest korrektselt:1-jah,2-ei

static String veateade = "";

static boolean ok;//kas s6na leidus reg.av-s,true-leidus

static String pikimAlamS6na = "";

static String p2risS6na = "";//kasutaja poolt sisest s6na

TextField regav;

TextField s6na;

AppletAla alumine;//appleti alumine, l6uendi piirkond

//-----------------------------------------------------------------------------

//Rakendi laadimisel tehtav töö (enne käivitamist).

public void init() {

  setLayout(new BorderLayout(0,15));

  setBackground(Color.white);

  Panel ylemine=new Panel(new GridLayout(2,2,0,10));

  Panel keskmine=new Panel(new GridLayout(1,2,200,0));

  alumine=new AppletAla();

  add(ylemine,BorderLayout.NORTH);

  add(keskmine,BorderLayout.CENTER);

  add(alumine,BorderLayout.SOUTH);

  Label silt=new Label("          Regulaaravaldis :");

  Font font1 = new Font("TimesRoman", Font.PLAIN,16);

  silt.setFont(font1);

  ylemine.add(silt);

  regav=new TextField("(a+20)c*01",30);

  regav.setFont(font1);

  regav.addActionListener(this);//syndmusi t88deldakse siin

  ylemine.add(regav);

  Label silt2=new Label("          Sõna :");

  silt2.setFont(font1);

  ylemine.add(silt2);

  s6na=new TextField("2001",30);

  s6na.setFont(font1);

  s6na.addActionListener(this);

  ylemine.add(s6na);

  Button otsinupp=new Button("Otsi sõna");

  otsinupp.addActionListener(this);//syndmusi t88deldakse siin

  keskmine.add(otsinupp);

  Button abinupp=new Button("Abi");

  abinupp.addActionListener(this);

  keskmine.add(abinupp);

}//init() l6pp

//-----------------------------------------------------------------------------

//Rakendi käivitamine veebilehele taasminemisel ehk vanade teadete kustutamine

public void start() {

  regavOk = 0;

  alumine.repaint();

}

//-----------------------------------------------------------------------------

public void actionPerformed(ActionEvent e){

  if (e.getActionCommand().equals("Abi")){

    new Abi();//ilmub uus aken abiks m6eldud tekstiga

  }

  else{//otsi s6na

    if ((regav.getText().length()>PIKKUS)||

        (s6na.getText().length()>PIKKUS)){

      regavOk=2;

      veateade="Kahtlaselt pikk sisend!!!";

      alumine.repaint();

    }

    else{//pikkus normaalne

      p2risS6na=s6na.getText();

      for (int i=0;i<p2risS6na.length();i++){

        if (Character.isWhitespace(p2risS6na.charAt(i))){

          p2risS6na=new

            String(p2risS6na.substring(0,i)+p2risS6na.substring(i+1));

          i--;

        }

      }

      if (p2risS6na.equals("")){

        regavOk=2;

        veateade="Sõna lahter on tühi!!!";

        alumine.repaint();

      }

      else{//tyhikutest puhas

        for (int i=0;i<p2risS6na.length();i++){

          if (p2risS6na.charAt(i)==AbiMeetod.TYHIS6NA){

            p2risS6na=new

              String(p2risS6na.substring(0,i)+p2risS6na.substring(i+1));

            i--;

          }

        }//for

        String kontroll = AbiMeetod.regavKontroll(regav.getText());

        if (kontroll.substring(0,2).equals("ok")){//reg.av oli ok

          String korrutisega=

               AbiMeetod.lisaKorrutusm2rgid(kontroll.substring(2));

          String postfix=AbiMeetod.infix_to_postfix(korrutisega);

          Tipp juur=AbiMeetod.tehaPuu(postfix);

          Automaat atm=AbiMeetod.teeAutomaat(juur);

          pikimAlamS6na=new String();

          AbiMeetod.tehtudOtsingud=new Vector(50,25);

          AbiMeetod.id=0;

          ok=AbiMeetod.otsi(atm.votaAlgOlek(),p2risS6na,new String());

          regavOk=1;

          alumine.repaint();

        }

        else {

          regavOk=2; //viga regulaaravaldises!!

          veateade=kontroll;

          alumine.repaint();

        }

      }//else;tyhikutest puhas

    }//else;pikkus normaalne

  }//else;otsi s6na

}//actionPerformed() l6pp

//-----------------------------------------------------------------------------

}//class RegexpApplet l6pp

###############################################################################

/*

Antud reg.avaldisest tehakse automaat ehk isend siia klassi. Selle

klaasi isendi puhul huvitab ainult automaadi alg-ja l6ppolek.

Privaatsete isendimuutujatega saab tegeleda avalike meetodite kaudu.

*/

public class Automaat{

private Olek algOlek;

private Olek l6ppOlek;

 

Automaat (Olek a,Olek b) {

  paneAlgOlek(a);

  paneL6ppOlek(b);

}

 

public void paneAlgOlek(Olek p) {

  algOlek = p;

}

public Olek votaAlgOlek() {

  return algOlek;

}

public void paneL6ppOlek(Olek p) {

  l6ppOlek = p;

}

public Olek votaL6ppOlek() {

  return l6ppOlek;

}

 

}//class Automaat l6pp

###############################################################################

/*

Antud reg.avaldisest tehakse automaat. Automaat koosneb olekutest

ehk selle klassi isenditest, mida iseloomustavad ID, kaare tähised

(max 2 kaart; tühi, puudub, tähestiku täht) ning teised olekud, kuhu

kaared "viivad". Privaatsete isendimuutujatega saab tegeleda avalike

meetodite kaudu.

*/

public class Olek{

private int id;

private char esimKaar;

private Olek esimOlek;

private char teineKaar;

private Olek teineOlek;

 

Olek (int id, char a, Olek b, char c, Olek d) {

  paneid(id);

  paneEsimKaar(a);

  paneEsimOlek(b);

  paneTeineKaar(c);

  paneTeineOlek(d);

}

public void paneid(int i){

  id = i;

}

public int votaid(){

  return id;

}

public void paneEsimKaar(char s) {

  esimKaar = s;

}

public void paneTeineKaar(char s) {

  teineKaar = s;

}

public char votaEsimKaar() {

  return esimKaar;

}

public char votaTeineKaar() {

  return teineKaar;

}

public void paneEsimOlek(Olek p) {

  esimOlek = p;

}

public Olek votaEsimOlek() {

  return esimOlek;

}

public void paneTeineOlek(Olek a) {

  teineOlek = a;

}

public Olek votaTeineOlek() {

  return teineOlek;

}

 

}//class Olek l6pp

###############################################################################

/*

Reg.valdise infixkujust saadav postfixkuju teisendatakse paremaks

edaspidiseks t88tluseks puukujule, mis koosneb tippudest ehk selle

klassi isenditest. Privaatsete isendimuutujatega saab tegeleda avalike

meetodite kaudu.

*/

public class Tipp {

 

// tippu identifitseeriv tehe v6i operand(t2ht)

private char nimi;

// viit tipu esimesele alluvale v6i null

private Tipp esimAlluv;

// viit tipu teisele alluvale v6i null

private Tipp teineAlluv;

 

// tipu konstruktor

Tipp (char s, Tipp a, Tipp b) {

  paneNimi(s);

  paneEsimAlluv(a);

  paneTeineAlluv(b);

}

public void paneNimi(char s) {

  nimi = s;

}

public char votaNimi() {

  return nimi;

}

public void paneEsimAlluv(Tipp p) {

  esimAlluv = p;

}

public Tipp votaEsimAlluv() {

  return esimAlluv;

}

public void paneTeineAlluv(Tipp a) {

  teineAlluv = a;

}

public Tipp votaTeineAlluv() {

  return teineAlluv;

}

 

}//class Tipp l6pp

###############################################################################

import java.awt.*;

/*

Piirkond appletil, kuhu kirjutatakse v2rviliselt s6naotsingu tulemused

ja veateated. P6hiline on paint() meetod.

*/

public class AppletAla extends Canvas{

 

AppletAla(){

  setSize(500,50);

}

 

//Graafilise konteksti kasutamine. g graafiline kontekst.

public void paint(Graphics g) {

  Font font1 = new Font("TimesRoman", Font.BOLD,16);

  Font font2 = new Font("TimesRoman", Font.ITALIC+Font.BOLD,16);

  Font font3 = new Font("TimesRoman", Font.ITALIC+Font.BOLD,14);

  if (RegexpApplet.regavOk==1){//kui reg.av sisestati korrektselt

    if (RegexpApplet.ok){//kui s6na leidus reg.avaldises

      g.setColor(Color.black);

      g.setFont(font1);

      try {Thread.sleep(100);}//kasutaja n2eks,et tuli ikka uus teade

      catch (InterruptedException except) {}

      g.drawString("Sõna on olemas antud keeles!",0,30);

    }

    else {//kui s6na ei leidunud reg.avaldises

      try { Thread.sleep(100); }

      catch (InterruptedException except) {}

      g.setColor(Color.red);

      g.setFont(font2);

      g.drawString("Vale sõna!!!",0,15);

      int laius=

          g.getFontMetrics().stringWidth(RegexpApplet.pikimAlamS6na);

      g.setColor(Color.blue);

      g.drawString(RegexpApplet.pikimAlamS6na,50,35);

      g.setColor(Color.red);

      g.drawString(RegexpApplet.p2risS6na.substring(

          RegexpApplet.pikimAlamS6na.length()),50+laius,35);

    }

  }

  if (RegexpApplet.regavOk==2){//kui sisend ei olnud korrektne

    g.setColor(Color.red);

    g.setFont(font3);

    g.drawString(RegexpApplet.veateade,0,30);

  }

}//paint() l6pp

 

}//class AppletAla l6pp

###############################################################################

import java.awt.event.*;

import java.awt.*;

 

//Abiks m6eldud tekstiga aken

public class Abi extends Frame{

 

Abi(){

  super("Programmist, regulaaravaldistest");

  setBackground(Color.white);

  setBounds(50,50,600,500);

  addWindowListener(new WindowAdapter(){

    public void windowClosing(WindowEvent e){

      dispose();

    }

  });

  String text = new String("\t\tVEEBILEHEST\n\n"+

"Siin veebilehel on võimalik saada vastus küsimusele:\n"+

"kas sõna on olemas antud regulaarsele avaldisele vastavas sõnade hulgas.\n"+

"Seda juhul kui sisestate mingi regulaaravaldise ja sõna ning vajutate\n"+

"nuppu \"Otsi sõna\".\n\n"+

"\tREGULAARAVALDISTEST\n"+

"Regulaaravaldistest on detailsemalt juttu allpool, aga lühidalt niipalju:\n"+

"regulaaravaldis on tekstina kirja pandud muster, mis koosneb tavalistest\n"+

"sümbolitest (nt täht 'a', numbrid) ja erisümbolitest (nt *,+).\n"+

"Muster kirjeldab ära sõnad, mis temaga sobivad. Regulaaravaldisi\n"+

"moodustatakse samamoodi nagu aritmeetilisi avaldisigi, kasutades\n"+

"mitmesuguseid operaatoreid (tehteid) ning kombineerides neid omavahel\n"+

"keerulisemateks avaldisteks.\n"+

"Regulaaravaldiste üles kirjutamisel saab siin kasutada kolme tehet:\n"+

"1)* -- kordus, mis tähendab, et sümbolile '*' eelnevat tähte (tähtede ühendit)\n"+

"võib selle regulaaravaldise poolt ära tuntavates sõnades sisalduda null kuni\n"+

"lõpmatu arv korda.\n"+

"2)+ -- valik, mis annab võimaluse valida kahe tähe (tähtede ühendi) vahel,\n"+

"millest üks või teine peab esinema selle regulaaravaldise poolt ära tuntavates\n"+

"sõnades antud positsioonil.\n"+

"3)konkatenatsioon (nagu ikka korrutusmärki matemaatikas vaikimisi ei kirjutata)\n"+

"määrab ära tähtede järjestuse selle regulaaravaldise poolt ära tuntavates\n"+

"sõnades.\n"+

"Tähestiku moodustavad inimkeele tähed ja numbrid. Tühja sõna tähistame: #.\n\n"+

"NÄITEID regulaaravaldistest ja neile vastavatest sõnadest:\n"+

"\tREG.AV\t\tSÕNAD\n"+

"\t(ab)*\t\t#,ab,abab,ababab,...\n"+

"\t(ab)*c\t\tc,abc,ababc,abababc,...\n"+

"\t(#+s)koor\t\tkoor,skoor\n"+

"\t(ab+d)*\t\t#,ab,abab,d,dd,abdddddddab,...\n"+

"\t(ab+d)c*\t\tab,abcccc,d,dccccccccccc,...\n"+

"\t(v+r)(edel+ool)\tvedel,vool,redel,rool.\n\n"+

"\tVEATEADE\n"+

"Kui sõna ei kuulu regulaaravaldise poolt genereeritud keelde, siis antakse\n"+

"väljundiks see mittesobinud sõna, kus sinise värviga on tähistatud see osa \n"+

"sõnast, mis sobis regulaaravaldise mustriga (maksimaalselt) ning punasega see\n"+

"osa, mis ei sobinud.\n\n"+

"\t\tREGULAARAVALDISTEST ÜLDISELT\n\n"+

"Regulaaravaldisi saab kasutada keele defineerimiseks. Regulaaravaldis\n"+

"esindab mustrit; sõnad, mis langevad mustriga kokku, kuuluvad sinna\n"+

"keelde, sõnad, mis ei sobi mustriga ei kuulu.\n"+

"Regulaaravaldisi pannakse kirja mitmel eri kujul. Siin pakutud süntaks\n"+

"on üks lihtsamaid.\n\n"+

"\tDEFINITSIOON\n"+

"Tähistame: #-tühisõna, O-tühi hulk, T-tähestik, .-konkatenatsioon.\n"+

"1)# ja O on reg.avaldised tähestikus T;\n"+

"2)suvaline täht a (tähestikust T) on reg.avaldis tähestikus T;\n"+

"3)kui R1 ja R2 on reg.avaldised, siis on ka (R1+R2), (R1.R2) ja (R1)* reg.avaldised.\n"+

"Punktides 1) ja 2) defineeritud regulaaravaldisi nimetatakse ka\n"+

"primitiivseteks regulaaravaldisteks. Seega, kui |T|=n, siis on tähestikus T\n"+

"defineeritud n+2 primitiivset regulaaravaldist.\n"+

"Seega võib reg.av koosneda \"sulgude hunnikust\", nt: (((((e.b).c)+a))*.d) .\n"+

"Reg.av lihtsamaks üles kirjutamiseks teeme kokkulepped:\n"+

"1. Operatsioonide prioriteet kahanevalt: *,.,+\n"+

"2. Sulud võib ära jätta, kui nad on üheselt taastatavad.\n"+

"3. Konkatenatsiooni '.' jätame kirjutamata.\n"+

"Seega saame ülaltoodud reg.av kirjutada lihtsalt: (ebc+a)*d\n\n"+

"\tREGULAARAVALDISE POOLT DEFINEERITUD KEEL\n"+

"Igale regulaarsele avaldisele R seatakse vastavusse sõnade hulk R' tähestikus T,\n"+

"järgmise definitsiooniga:\n"+

"1)kui R=#, siis R'={#}; kui R=O, siis R'={}.\n"+

"2)kui R=a (a kuulub T),siis R'={a}.\n"+

"3)kui R1 ja R2 on reg.avaldised ning R'1 ja R'2 neile vastavusse seatud hulgad,\n"+

"siis\n"+

"\tkui R=(R1+R2), siis R'=R'1 U R'2 (kus U-hulgateoreetiline ühend)\n"+

"\tkui R=(R1.R2), siis R'=R'1 . R'2 (kus .-kahe hulga konkatenatsioon)\n"+

"\tkui R=(R1)*, siis R'=R'1 = {#}U{x|x on R1 sõnade konkatenatsioon}\n\n"+

"NÄITEID regulaarsetest avaldistest ja neile vastavatest hulkadest:\n"+

"\tREG.AV\t\tKEEL\n"+

"\ta*\t\t{#,a,aa,aaa,...}\n"+

"\tabc\t\t{abc}\n"+

"\ta+b+c\t\t{a,b,c}\n"+

"\ta(bc+dc)\t\t{abc,adc}.\n");

  TextArea tekstiala=new TextArea(text);

  Font font1 = new Font("TimesRoman",Font.PLAIN,16);

  tekstiala.setFont(font1);

  tekstiala.setEditable(false);

  add(tekstiala,BorderLayout.CENTER);

  setVisible(true);

}//konstruktor Abi l6pp

 

}//class Abi l6pp