Automaadid, keeled ja translaatorid 2017/18 kevad

RegexAnalyzer

Vaatame klassi RegexAnalyzer, mis tuleb täiendada. Vaja on implementeerida kolm meetodit, mis võtavad argumendiks argumendiks regulaaravaldise süntaksipuu ja analüüsivad selle.

1. matchesEmptyWord kontrollib, kas tühisõne kuulub selle regulaaravaldise poolt defineeritud keelde.
2. matchesInfManyWords tagastab true, kui regulaaravaldise keel on lõpmatu.
3. getAllWords tagastab lõpliku keele korral hulga kõigi selle regulaaravaldisega sobivate sõnadega. Lõpmatu keele korral tuleb visata erind.

Regulaaravaldise puu klassid

Regulaaravaldise süntaksipuu on moodustatud paketis week5.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 klasside kasutamine näeks välja midagi sellist:

void teeMidagiRegulaaravaldisega(RegexNode node) {
	if (node instanceof Alternation) {
		// see tipp tähistab valikut
		Alternation altNode = (Alternation)node;
		teeMidagi(altNode.getLeft());
		teeMidagi(altNode.getRight());
	} else if (node instanceof Repetition) {
		...
	}
	...
}

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"}.

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