Automata, Languages and Compilers 2019/20 spring

Regulaaravaldiste analüüs

Regulaaravaldise puu klassid

Regulaaravaldise süntaksipuu on moodustatud paketis week4.regex oleva RegexNode klassi alamklasside isenditest. Konkreetsemalt, huvipakkuvad klassid on:

• Alternation – valik kahe alternatiivi (getLeft() ja getRight()) vahel
• Concatenation – kahe regulaaravaldise (getLeft() ja getRight()) konkatenatsioon
• Repetion – regulaaravaldise (getChild()) kordamine 0 või enam korda
• Letter – kindla tähega (getSymbol()) sobituv regulaaravaldis
• Epsilon – tühja sõne tähistav regulaaravaldis

Nende läbimiseks on jällegi olemas RegexVisitor.

Regulaaravaldiste analüsaator

Enne kodutöö lahendamist oleks hea regulaaravaldise süntaksipuu peal ülesandeid lahendada. Vaatame klassi RegexAnalyzer, mis tuleb täiendada. Vaja on implementeerida kolm meetodit, mis võtavad argumendiks regulaaravaldise süntaksipuu ja analüüsivad selle.

1. matchesEmptyWord kontrollib, kas tühisõne kuulub selle regulaaravaldise poolt defineeritud keelde.
2. getFirst tagastab regulaaravaldise põhjal kõik tähed, millega regulaaravaldisele vastav keel võib alata. Näiteks "(a|b)*cd" puhul on esimesed tähed 'a', 'b' ja 'c'. Selleks on väga abiks eelmine funktsioon, sest konkatenatsiooni puhul peab jälgima, kas esimene osa võib olla tühi või mitte.
3. getAllWords tagastab lõpliku keele korral hulga kõigi selle regulaaravaldisega sobivate sõnadega. Lõpmatu keele korral tuleb visata erind.

NB! Antud ülesande testid on kõik avalikud, aga kontrolltöö ajal võib avalike testide hulk olla piiratud ning lünklik.

getAllWords: abimeetod combine

Alamülesandena soovitame realiseerida meetodi combine, mis võtab kaks sõnede hulka ja tagastab uue sõnede hulga, mis sisaldab kõiki esimese ja teise hulga sõnede kombinatsioone, nii et esimese hulga sõne on konkateneeritud teise hulga sõnega. Näide pseudokoodis:

	RegexAnalyzer.combine({"kala", "äri"},  {"mees", "naine", ""}) 

peaks tagastama

	{"kalamees", "kalanaine", "kala", "ärimees", "ärinaine", "äri"}.

matchesEmptyWord ja getFirst korraga

Kui oled matchesEmptyWord ja getFirst implementeerinud eraldi, siis proovi getFirst arvutada niimoodi, et ei peaks kogu aeg uuesti arvutama, kas alampuu võib olla tühi. Kuna me esimese meetodi vahetulemusi ei salvestata, siis võib teda kutsuda välja mitu korda. Siin aines me üldiselt ei muretse efektiivsuse pärast, aga oluline on aru saada, kus võib halvasti minna. Siin on asi tõsine! Esimene meetod arvutab ju ka oma lapsi iga kord uuesti, et koos võivad need meetodid külastada sügavusel d tipu äärmisel juhul d² korda.

Proovi implementeerida need kaks meetodit korraga. Selleks on siis vaja tagastada kahte väärtust korraga ja Java nõuab selleks oma klassi loomist. See on hea harjutus, sest kodutöös pead ka oma tulemustüübi looma.