Automata, Languages and Compilers 2017/18 spring

Plus-miinusavaldise 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 funktsioon public static List<String> tokenize(String input), mis tükeldab sõne juppideks. Lihtsam variant on nüüd siin java abiks kutsuda ja selle töö meie eest ära teha. 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 oleks siis tähthaaval koguda ehk akkumuleerida tähti (acc), kuni oleme valmis neid ühe juppina lisada (push). Lisaks tuleb plus ja miinus lihtsalt eraldi juppina 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ärgmise ü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.

Ülesanne 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 olekumasina nii täiendada, et ta jälgiks avaldise süntaktilist korrektsust. Seda saab teha ühe boolean muutujaga.