Avaldise süntaksipuu läbimine
Teemat tutvustav video: Avaldispuu läbimine ja visitor.
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. Juurklassis ExprNode on ka main meetod, kus on järgnev näide. Selleks peame defineerima kõikides alamklassides eval meetodi.
public static void main(String[] args) {
Expression expr1 = div(add(num(5), add(num(3), neg(num(2)))), num(2));
System.out.println(expr1.eval()); // tulemus: 3
}
Kontrollimiseks võib käivitada VisitorIntroTest-i kahte esimest testi.
Puu väline analüüs: VisitorIntro
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. Klassis VisitorIntro on samuti eval meetod, mis võiks arvutada sama tulemuse ehk võiks kehtida expr.eval() == VisitorIntro.eval(expr).
Objektorienteeritud lähenemine
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. Selle asemel on parem puu läbimisel luua oma 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 evalWithVisitor(ExprNode expr) {
ExprVisitor<Integer> visitor = new ExprVisitor<Integer>() {
public Integer visit(Add node) {
return visit(node.getLeft()) + visit(node.getRight());
}
public Integer visit(Num node) {
return node.getValue();
}
// jne...
};
return expr.accept(visitor);
}
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 copy-paste abil implementeerida seda meetodit.
- Vaata BaseVisitor klassi implementatsiooni ja kasuta seda, et vältida koodi kordamist.
- Lõpuks võib proovida kõiki elemente lihtsalt ühte ja samasse hulka kokku koguda.
Kõige olulisem on siin see, et oskaksid ise selle puhta visitori abil neid ülesandeid lahendada. Eksamil ei ole isegi BaseVisitor olemas. Lubatud on ka instanceof-ahelad, aga me ei tahaks seda siiski julgustada.
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.
Funktsionaalne lähenemine
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.
Paketist week4.baselangs.rec leiad koopia ülalkäsitletud aritmeetiliste avaldiste keelest, mis on realiseeritud uusimate Java võimaluste abil. Kahjuks me AKT-s edaspidi neid võimalusi veel ei kasuta, aga neist tasub siiski teadlik olla, kuna neist on kasu ka väljaspool programmeerimiskeelte loomist.