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?
Arutage paarilisega ja formuleerige oma ettepanek.
Analoogiline näide: aritmeetilised avaldised
Teeme nüüd läbi sellise harjutuse, kus esitame mõistlikul kujul aritmeetilise avaldise. Meil on näidiskeelte jaoks eraldi pakett toylangs, kus aritmeetiliste avaldiste süntaksipuu klassid asuvad pakettis expr. Juurklassis ExprNode on ka main meetod, kus on järgnev näide. Selleks peame defineerida kõikides alamklassides eval meetod.
public static void main(String[] args) {
Expression expr1 = div(add(num(5), add(num(3), neg(num(2)))), num(2));
Expression expr2 = div(div(num(8), num(2)), num(2));
Expression expr3 = div(num(8), div(num(2), num(2)));
System.out.println(expr1.eval()); // tulemus: 3
}
Puu väline analüüs: VisitorIntro.java
Kuna meie süntaksipuu klassid genereeritakse 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 seda 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 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 pruugi olla isegi BaseVisitor olemas. Lubatud on ka instanceof-ahelad, aga me ei tahaks seda siiski julgustada.
Listener
Kui me hakkame ANTLR'iga töötama, siis luuakse meile veel selline puu läbimise võimalus nagu sündmuste kuulajad. Seal siis läbitakse kõiki lapsi vasakult-paremale, aga selle 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ärgmisi meetodeid:
enter(node); // <-- võime enter meetodit implementeerida
visit(node.getLeft());
visit(node.getRight());
exit(node); // <-- või siis exit meetodit... (või mõlemad)