Automaadid, keeled ja translaatorid

Avaldise süntaksipuu läbimine

Milleks puu?

Kuidas oleks hea esitada regulaaravaldist arvutiprogrammis, kui me tahaksime küsida selle kohta midagi taolist:

• Kas regulaaravaldise poolt esitatud keel on lõplik? Kui jah, siis mitu sõna kuulub keelde?
• Kas tühi sõna kuulub keelde?
• Kas sõna "kalamari" kuulub keelde?
• Kas avaldist saab lihtsustada? Kuidas?

Mõelge selle üle ja formuleerige oma ettepanek.

Analoogiline näide: aritmeetilised avaldised

Teeme nüüd läbi sellise harjutuse, kus esitame mõistlikul kujul aritmeetilise avaldise. Paketis week4.baselangs.expr asuvad aritmeetiliste avaldiste süntaksipuu klassid. Juurliideses ExprNode on ka main meetod, kus on järgnev näide. Selleks peame defineerima kõikides alamklassides eval meetodi õigesti.

    static void main() {
        ExprNode expr = div(add(num(5), add(num(3), neg(num(2)))), num(2));
        System.out.println(expr.eval()); // tulemus: 3
    }

Kontrollimiseks võib käivitada ExprEvaluatorTest-i esimest testi.

Puu väline analüüs

Kuna meie süntaksipuu klassid genereeritakse hiljem automaatselt ANTLRi poolt, siis ei ole väga mõistlik hakata neid redigeerima. Mõnikord on ka mugavam, kui kogu funktsiooni loogika on ühes kohas. Seetõttu defineerime siin ka eval meetodi väliselt.

Funktsionaalne lähenemine: ExprEvaluator

Klassis ExprEvaluator on samuti mõned eval meetodid, mis võiks arvutada sama tulemuse.

instanceof

Üks võib-olla tuttav võimalus on kasutada instanceof operaatorit, nii nagu seda on tehtud rekursiivses evalInstanceof meetodis. Siin on vaja ainult üks väike parandus teha, et päriselt kehtiks expr.eval() == ExprEvaluator.evalInstanceof(expr). Kontrollimiseks võib käivitada ExprEvaluatorTest-i teist testi.

Mustrisobitus

Kui oled tubli objektorienteeritud programmeerija, siis instanceof kasutamine võib üsna häiriv olla. Java tüübikontroll ja arenduskeskkond ei ole siis ka väga abiks. Viimastesse Java versioonidesse (eriti Java 21-te) on lisatud funktsionaalprogrammeerimise keeltest pärit võimalusi, mis muuhulgas oluliselt lihtsustavad avaldispuude defineerimist ja nende väärtustamist.

ExprNode ongi juba realiseeritud uusimate Java võimaluste abil. ExprEvaluator.eval meetodis on neid võimalusi ka ära kasutatud, et kirjutada elegantsem meetod kui eelmine. Seal tuleb ka üks väike parandus teha ning seda võib ExprEvaluatorTest-i kolmanda testiga kontrollida.

Objektorienteeritud lähenemine: ExprVisitorEvaluator

Edaspidi üldiselt kasutamegi neid uusimaid Java võimalusi, aga kõikjal seda kahjuks siiski teha ei saa. Eelkõige käib see hiljem ANTLR-iga genereeritud süntaksipuu klasside kohta. Nende töötlemiseks (ilma instanceof-ita) tuleb kasutada külastaja disainimustrit (visitor design pattern).

Teemat tutvustav video: Avaldispuu läbimine ja visitor.

Puhas visitor

Visitor on üsna kuulus disainimuster ja sellel on palju erinevad variante. Mõnikord fikseerib raamistik tippude läbimise strateegia, aga kasutame siin sellist üldist visitori, mis sisuliselt ainult lahendab selle tüübiteisenduste probleemi ja ise kutsume visit meetodit tipu alluvate peal, et edasi puud läbida. Me saame (aga ei pea) siseklassidena implementeerida oma visitori alamklassi ja seda kohe rakendada:

    public static int eval(ExprNode node) {
        ExprVisitor<Integer> visitor = new ExprVisitor<>() {
            public Integer visit(ExprNum num) {
                return num.value();
            }

            public Integer visit(ExprNeg neg) {
                return -visit(neg.expr());
            }

            // jne...
        };
        return node.accept(visitor);
    }

Proovi visitori abil realiseerida ExprVisitorEvaluator.eval meetod ja testi seda (nüüd siis ExprVisitorEvaluatorTest-iga).

Kõige olulisem on siin see, et oskaksid ise rekursiooni ja mustrisobituse abil neid ülesandeid lahendada. Eksami keeltes pole visitore isegi olemas. Lubatud on ka instanceof-ahelad, aga me ei tahaks seda siiski julgustada.

BaseVisitor

See võib tüütuks muutuda, kui peab pidevalt ise hoolitsema alluvate külastamise eest. Oletame, et me tahame implementeerida meetodi getAllValues, mis tagastab kõikides lehtedes esinevad arve. See on ju lihtne meetod ja siin ei ole oluline, kas tegemist on liitmise või jagamise vahetipuga.

• Proovi kõigepealt harjutamiseks implementeerida ExprEvaluator.getAllValues ilma visitorita.
• Siis proovi sama asja teha visitoriga meetodis ExprVisitorEvaluator.getAllValues.
• Vaata ExprVisitor.BaseVisitor klassi implementatsiooni ja kasuta seda, et vältida koodi kordamist meetodis getAllValuesAggregate.
• Tegelikult võib hoopis kõiki elemente lihtsalt ühte ja samasse hulka kokku koguda nagu seda on tehtud meetodis getAllValuesImperative.

Listener

Kui me hakkame ANTLRiga töötama, siis luuakse meile veel selline puu läbimise võimalus nagu sündmuste kuulajad (listener). Sellega läbitakse kõiki alamtippe vasakult-paremale ja liidese kasutaja võib teatud külastussündmustele reageerida. Sündmused toimuvad enne ja pärast tipu külastamist, aga muidugi ei pea kõikidele sündmustele reageerima. Näiteks liitmise tipu külastamisel kutsutakse välja järgmised meetodid:

                enter(node); // <-- võime enter meetodit implementeerida
                visit(node.getLeft());
                visit(node.getRight());
                exit(node);  // <-- või siis exit meetodit... (või mõlemad)

Täpsemalt me listenere siin aines ei vaata ega kasuta.