Automata, Languages and Compilers 2017/18 spring

3. kodutöö

Selle lahendamiseks tasub kõigepealt natukene tutvuda meie abimaterjalidega JFLAP ja olekumasina kohta, sest siin on mõned uued teemad ja tahame ka Java lahendust teatud kujul.

1. JFlap harjutused (5p)

Koosta JFLAP-is järgenevatele kirjeldustele vastavad lõplikud automaadid ja lae failid Moodle'isse.

Kasuta failinimesid kujul yl<ülesande nr>.jff nt. yl1.jff.

1. Sõnad üle tähestiku {a,b}, mis algavad või lõppevad tähega 'a'.
2. Sõnad üle tähestiku {a,b}, mis algavad ja lõppevad tähega 'a', muuhulgas "a" ise.
3. Sõnad üle tähestiku {a,b}, mis sisaldavad vähemalt üks 'a'.
4. Sõnad üle tähestiku {a,b}, mis sisaldavad vähemalt üks 'a' ja täpselt üks 'b'.
5. Sõnad üle tähestiku {a,b}, mis sisaldavad vähemalt üks 'a' ja paaritu arv 'b'-sid.

2. Olekumasin (5p)

Selle kodutöö eesmärk on kirjutada olekumasin, mis aitab meid teksti korrastamisega. Sisendiks saame näiteks sellise tekstijuppi:

This     text (all of it   )has occasional lapses .. .in
  punctuation( sometimes,pretty bad ; sometimes ,not so).

( Ha ! )Is this  :fun ! ? !  Or   what  ?

Ja me tahaks, et tulemuseks oleks ilus korrastatud tekst:

This text (all of it) has occasional lapses... in
punctuation (sometimes, pretty bad; sometimes, not so).

(Ha!) Is this: fun!?! Or what?

Korrastatud tekst vastab järgmistele nõuetele:

• Sõnade vahel on täpselt üks tühik.
• Kirjavahemärkidena arvestame selles kodutöös järgmiseid: koma, koolon, semikoolon, punkt, hüüumärk ja küsimärk. Eraldi käsitleme ka sulgusid.
• Sõna ja temale järgneva kirjavahemärgi vahel ei ole tühikut, aga kirjavahemärgi ja temale järgneva sõna vahel on: "Tere, Maailm!"
• Kirjavahemärkide vahel ei ole tühikut, näiteks "Mis asja?!".
• Avav sulg käitub vastupidiselt teistele kirjavahemärkidele: sellel on ees tühik, aga järel mitte.
• Lõppev sulg käitub põhimõtteliselt nagu teised kirjavahemärgidki.
• Rea algul ei ole ühtegi tühikut! (Uue rea sümbol on \n). NB! Ka esimesel real ei tohiks olla algul ühtegi tühikut.

Esitamine

FormatMachine.java tuleb esitada siin.

Kuidas seda lahendada

Me oleme ainult paari miljoni euro eest saanud sellise üldise raamistiku seda tüüpi ülesannete lahendamiseks. Raamistiku töö on sisendit kuskilt lugeda ja tähthaaval meie olekumasinale sööta. Meie olekumasin annab iga tähe jaoks vastuseks sõne (mis võib ka olla tühi), millega tuleks antud tähe asendada. Raamistiku kood on järgmine:

import week3.FormatMachine;

public class FormatText {
    public static String cleanUp(String s) {
        StringBuilder sb = new StringBuilder();
        FormatMachine machine = new FormatMachine();
        for (char c : s.toCharArray()) {
            sb.append(machine.process(c));
        }
        return sb.toString();
    }

    // Meetodi käivitame näiteks nii:
    public static void main(String[] args) {
        String input =
                "This     text (all of it   )has occasional lapses .. .in\n" +
                "  punctuation( sometimes,pretty bad ; sometimes ,not so).\n" +
                "\n" +
                "( Ha ! )Is this  :fun ! ? !  Or   what  ?";
        System.out.println(cleanUp(input));
    }
}

Me oleme väga tänulikud, sest nüüd jääb ainult implementeerida olekumasin "FormatMachine", mis sisulise töö ära teeb. See peab siis vastama järgmisele mallile:

package week3;

public class FormatMachine {
    public String process(char c) {
        // TODO: Asendada millegagi, mis midagi asjaliku teeb.
        return "" + c; //  ehk Character.toString(c)
    }
}

Kui raamistiku kirjeldus on segane, siis proovige kõigepealt katsetamise teel aru saada, mis ta teeb. Käivitage ülalolev kood, kui process on täpselt nii nagu ta üleval on. Tehke siis väiksed muudatused. Proovige näiteks, mis juhtub, kui process teeb ainult return " " + c;, jne. Oluline on kõigepealt aru saada raamistikust, sest me oleme sinna palju raha investeerinud ja seda enam muuta ei saa. Teie saate ainult FormatMachine koodi üles laadida!

NB! Kui ülesanne ise tundub raske, siis alustage ikkagi lihtsamate testjuhtumitega:

Üks kaks  kolm   neli    viis

Tere , maailm  !

Tere ,maailm !  !

Järgmisena proovige mõned testid sulgudega. Ja lõpuks peab reavahetust käsitlema ('\n'), et meie esialgne näide ka töötaks.

Kui ka peale pikemat pusimist jääd hätta, siis loe vihjeid.

Allikas

Ülesanne on inspireeritud Victor Eijkhout'i juhendist "A Lex Tutorial". Võib-olla seal olev lahendus on abiks, aga sealsest kontekstist aru saamine võib rohkem aega nõuda, kui ülesanne otse lahendada.