Automaadid, keeled ja translaatorid - Kursused

Olekutega programmeerimine

Teemat tutvustav video: Olekumasinatega programmeerimine.

Teoorias huvitavad meid peamiselt olekumasinad, mis vastavad jah/ei küsimusele: kas sõne kuulub regulaaravaldise poolt defineeritud hulka. Praktikas kasutatakse olekumasinaid, mis lisaks veel midagi teevad, aga käituvad erinevalt sõltuvalt oma seisundist. Üks standard selliste praktilisemate olekumasinate joonistamiseks on UML State Machine. Alustuseks on siin üks lihtne klassikaline näide olekupõhisest programmist. Edasi võib vaadata järgmisi materjale:

Esimese kodutöö saab väga ilusasti olekumasinatega lahendada.
Olekupõhist mõtlemisvõimet võib proovile panna teksti puhastamise ülesandega, FormatMachine.
Kui olekumasinad väga meeldivad, siis on meil üks tore lisaülesanne, et seda kõike teha formaalse Mealy masinaga.

HtmlStrip

Meie eesmärk on kirjutada meetod, mis eemaldab kujunduskäske (tags) HTML dokumendist. Proovime kõigepealt siis kirjutada sellise meetodi, mis kõige lihtsama sisendi puhul töötab:

Sisend: <b>foo</b>
Eeldatav väljund: foo

Meetodi signatuur võiks olla järgmine:

public class HtmlStrip {
    public static String removeHtmlMarkup(String s) {
        StringBuilder sb = new StringBuilder();
        // TODO: midagi peaks ilmselt tegema.
        return sb.toString();
    }
}

Kirjutame kohe ka esimese testi:

public class HtmlStripTest {
    @Test
    public void testRemoveHtmlMarkup() throws Exception {
        check("foo", "<b>foo</b>");
    }

    public void check(String expected, String input) {
        assertEquals(input, expected, HtmlStrip.removeHtmlMarkup(input));
    }
}

Alustame lihtsa ideega

Idee võiks olla selline, et loeme tähthaaval sisendit ja me lihtsalt kopeerime seda väljundisse (echo). Kui aga näeme märki <, siis lähme ignoreerimise režiimi. Seda ideed võib joonistada olekumasinana, mille põhjal saame järgmist koodi:

    public static String removeHtmlMarkup(String s) {
        StringBuilder sb = new StringBuilder();
        boolean tag = false;
        for (char c : s.toCharArray()) {
            if (c == '<') {
                tag = true;
            } else if (c == '>') {
                tag = false;
            } else if (!tag) {
                sb.append(c);
            }
        }
        return sb.toString();
    }

NB! Implementatsioon on pisut vigane, nimelt sisendi <b>f>5</b> puhul peaks väljund olema f>5, aga programm annab teise vastuse. Olekumasin (paremal) on siiski korrektne, seega ei tohiks liiga raske olla seda viga parandada. Palun tee seda! Nii, väga hea, aga meil on kahjuks suurem mure: <a href='>'>foo</a>. Selliste sisenditega me ei olnud arvestanud!

Natuke keerulisem sisend

Meil oleks uut olekut vaja, et vältida seda probleemi, kui sõnede sees esineb '>'. Kõigepealt lisame vajalike teste, sest meile ei meeldi pimedas programmeerida:

    @Test
    public void testRemoveHtmlMarkupWithQuotes() throws Exception {
        check("foo", "<a href='>'>foo</a>");
    }
    @Test
    public void testRemoveHtmlMarkupWithJustQuotes() throws Exception {
        check("'foo'", "'<b>foo</b>'");
        check("'foo'", "'foo'");
    }

Nüüd joonistame uue automaadi ja kirjutame ka sellele vastav kood:

    public static String removeHtmlMarkup(String s) {
        StringBuilder sb = new StringBuilder();
        boolean tag = false;
        boolean qte = false;
        for (char c : s.toCharArray()) {
            if (c == '<' && !qte) {
                tag = true;
            } else if (c == '>' && tag && !qte) {
                tag = false;
            } else if (c == '\'' && tag) {
                qte = !qte;
            } else if (!tag) {
                sb.append(c);
            }
        }
        return sb.toString();
    }

Ma ei ole veel päris kindel...

See kood arenes üsnagi katse-eksitus meetodil. Ma ei tea, mis ta täpselt teeb, sest need kõrvaltingimused on päris keerulised. Me peame sõltuvalt sisendist ja automaadi olekust mingi otsuse tegema. Siiamaani oleme põhiliselt sisendi järgi hargnenud ja siis oleku peale mõelnud. Kirjutame nüüd aga rohkem olekumasina vaatevinklist:

    public static String removeHtmlMarkup(String s) {
        final int INI = 0;
        final int TAG = 1;
        final int QTE = 2;
        StringBuilder sb = new StringBuilder();
        int state = INI;
        for (char c : s.toCharArray()) {
            switch (state) {
                case INI:
                    if (c == '<') state = TAG;
                    else sb.append(c);
                    break;
                case TAG:
                    if (c == '>') state = INI;
                    if (c == '\'') state = QTE;
                    break;
                case QTE:
                    if (c == '\'') state = TAG;
                    break;
            }
        }
        return sb.toString();
    }

Selle implementatsiooni suur eelis on see, et on palju kergem veenduda, et kood vastab mudelile. Eelmine lahendus läbib ka minu teste, aga kes teab... Viimase koodi suhtes olen palju optimistlikum! Samas, alati ei pruugi oleku järgi hargnemine olla kõige mugavam. Järgnev ülesanne on näiteks selline, kus minu jaoks oli mugavam sisendi järgi ikkagi hargneda. Alati on aga abiks olekumasina välja joonistamine paberil!

Harjutusmasinate liides

Kirjutame siin ülaloleva koodi ümber formaadis, mis on rohkem olekumasina moodi. See on meil tegelikult ainult selleks oluline, et kui lahendad iseseisvalt meie harjutusi sellel teemal, siis see julgustab Sind tõesti tähthaaval sõne läbida. Näitame siin ka sellise lahenduse, kus hargneme põhiliselt tähtede järgi (nii on mõnikord mugavam), aga ikkagi on kasutatud paberil joonistatud automaati, et paremini aru saada toimuvast. Olekud on seetõttu mõistlikumad: nad ei ole eraldi muutujates hajutatud. Tuleb implementeerida klass HtmlStripMachine, millel on meetod process ja raamistik hoolitseb selle eest, et tähthaaval sisendit sellele sööta:

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

Kui olekumasina joonist vaadata, siis on selge, et väljastamine toimub ainult algseisundis, kui sisendtäht ei ole <, seetõttu võime kõigepealt otsustada, kas on vaja midagi väljastada või mitte. Me peame seda kohe algul otsustama, kuna seisund võib pärast muutuda. Salvestame otsuse tulemust muutujas echo. Ülejäänud loogika on üsna otse joonise pealt tulnud:

import static week3.machines.HtmlStripMachine.State.*;

public class HtmlStripMachine {
    enum State {
        INI, TAG, QTE
    }
    private States state = INI;

    public String process(char c) {
        boolean echo = state == INI;
        switch (c) {
            case '<':
                if (state == INI) state = TAG;
                return ""; // Seda ei väljastata!
            case '>':
                if (state == TAG) state = INI;
                break;
            case '\'':
                if (state == QTE) state = TAG;
                else if (state == TAG) state = QTE;
                break;
        }
        return echo ? Character.toString(c) : "";
    }
}

Sinu kord

Võiks proovida, et ka tavaliste jutumärkidega töötaks. Siis peab olema nii, et kui alustame ühte tüüpi jutumärkidega, siis lõpetame ainult sama tüüpi jutumärgiga: "John's" ja 'Ta ütles, "Tere!"'. Vajalikud testid on failis HtmlStripMachineTest.java.

Automaadid, keeled ja translaatorid 2020/21 kevad