Automata, Languages and Compilers 2019/20 spring

MiniAKTK kodutöö olekumasinad

Esimese kodutöö juures võib kasutada olekumasinad mitmes kohas:

1. Sisendi tükeldamine juppideks.
2. Tulemuse arvutamine juppide põhjal.

Nende jaoks vaatame klassi MiniAktkMachines.

Juppideks tükeldamine (raskem)

Tahame funktsiooni public static List<String> tokenize(String input), mis tükeldab sõne juppideks. Lihtsam variant on nüüd siin java abiks kutsuda, mis selle töö meie eest ära teeb. Selliste asjadega katsetamiseks on üsna kasulik kasutada jshell-i, mis annab pythoniga sarnase käsurea interpretaatori. Sellega saab näiteks niimoodi katsetada:

|  Welcome to JShell -- Version 11.0.6
|  For an introduction type: /help intro

jshell> "1 +  6+7".replace(" ","")
$1 ==> "1+6+7"

jshell> "1 +  6+7".replace(" ","").replace("+","!+!")
$2 ==> "1!+!6!+!7"

jshell> "1 +  6+7".replace(" ","").replace("+","!+!").split("!")
$3 ==> String[5] { "1", "+", "6", "+", "7" }

Olekumasinaga

Samas on huvitav seda ise teha. Idee on siis tähthaaval koguda ehk akumuleerida tähti (acc), kuni oleme valmis neid ühe jupina lisama (push). Lisaks tuleb plus ja miinus lihtsalt eraldi jupina lisada (echo):

Implementeerime automaadi järgmiselt:

    public static List<String> tokenize(String input) {
        List<String> tokens = new ArrayList<>();
        StringBuilder currentToken = new StringBuilder();         // Tühi sõne => ￢TOK
        for (char c : input.toCharArray()) {
            if (c == '+' || c == '-' || c == '=' || c == ' ') {   // lisame siia '=' ja tühikud.
                if (currentToken.length() != 0) {
                    tokens.add(currentToken.toString());          // push
                    currentToken = new StringBuilder();
                }
                if (c != ' ') tokens.add(Character.toString(c));  // echo (v.a. tühikud)
            } else {
                currentToken.append(c);                           // acc
            }
        }
        // Ja lõpuks EOF puhul ka push seisundis TOK:
        if (currentToken.length() != 0) tokens.add(currentToken.toString());
        return tokens;
    }

Siin on väga kasulik vaadata, mis on selle koodi ja masina vastavus ja mille poolest erineb implementatsioon olekumasinast. (Kuidas käitub masin versus kood, kui sisend on "5+"?). Esimese kodutöö lahendamiseks peaks võib-olla ka kommentaaridest jagu saama, aga kõigepealt tasub järgmine ülesanne ära teha, sest arvutamisel on ka viga sisse jäänud.

Ülesanne: väärtustamise olekumasin

Ükskõik, kuidas me tükeldame, siis väärtustamine on kõige mõistlikum teha just olekumasina abil. Selliselt saame ka väärtustada kõik võimalikud Javas lubatud plus-miinus avaldised, näiteks 5 + - - 7. Lisaks on see kood väga lihtne:

    public static int compute(List<String> tokens, Map<Character, Integer> environment) {
        int sign = 1;
        int sum = 0;
        for (String token : tokens) {
            switch (token) {
                case "-":
                    sign *= -1;
                    break;
                case "+":
                    break;
                default:
                    sum += sign * getValue(token, environment);
            }
        }
        return sum;
    }

Ainus mure on see, et see tegelikult ei tööta. Mõned testid ei lähe läbi ja selleks ongi Sinu abi vaja:

• Joonista kõigepealt olekumasin, mis vastab ülalolevale koodile.
• Joonista õige olekumasin ja leia koodis viga üles.

Kõigepealt võiks tööle minna MiniAktkEvalTest ja siis võiks proovida esimese nädala testikomplekti MiniAktkMachinesTest. Selleks peab olekumasinat nii täiendama, et ta jälgiks avaldise süntaktilist korrektsust. Seda saab teha ühe boolean muutujaga.