Automata, Languages and Compilers 2018/19 spring

Plus-miinus avaldise olekumasinad

Selle esimese kodutöö juures võib kasutada olekumasinad mitmes kohas:

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

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 Java REPL, mis annab pythoniga sarnase käsurea interpretaatori. Sellega saab näiteks niimoodi katsetada:

Welcome to JavaREPL version 272 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0)
Type expression to evaluate, :help for more options or press tab to auto-complete.
java> "1 +  6+7".replace(" ","")
java.lang.String res0 = "1+6+7"
java> "1 +  6+7".replace(" ","").replace("+","!+!")
java.lang.String res1 = "1!+!6!+!7"
java> "1 +  6+7".replace(" ","").replace("+","!+!").split("!")
java.lang.String[] res2 = ["1", "+", "6", "+", "7"]

Samas on huvitab 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+"?). Kodutöö lahendamiseks peaks 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<String, Integer> env) {
        int sign = 1;
        int sum = 0;
        for (String token : tokens) {
            switch (token) {
                case "-":
                    sign *= -1;
                    break;
                case "+":
                    break;
                default:
                    sum += sign * getValue(token, env);
            }
        }
        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.

Ülesande kood on meie repos failis AktkMachines.java. Kõigepealt võiks tööle minna EvaluatorTest ja siis võiks proovida esimese nädala testikomplektiga AktkMachinesTest.java. Selleks peab olekumasinat nii täiendama, et ta jälgiks avaldise süntaktilist korrektsust. Seda saab teha ühe boolean muutujaga.