Regulaaravaldise struktuuri esitamine ja uurimine
Mõtteharjutus
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
Teeme nüüd läbi selline harjutus, kus esitame mõistlikul kujul aritmeetilist avaldist. Proovige defineerida eval meetod, mis väärtustab avaldist.
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: ExprAnalyzer
Kuna meie süntaksipuu klassid genereeritakse automaatselt ANTLRi poolt, siis ei ole väga mõistlik hakkata neid redigeerima. Mõnikord on ka mugavam, kui kogu funktsiooni loogika on ühes kohas. Seetõttu defineerime siin ka eval meetod väliselt. Klassis ExprAnalyzer on samuti eval meetod, mis võiks arvutada sama tulemus ehk võiks kehtida expr.eval() == ExprAnalyzer.eval(expr).
(Optional) Objektorienteeritud lähenemine
Kui oled väga palju OO propagandat ära söönud, siis instanceof kasutamine võib üsna häiriv olla. Siin on siis kaks objekt-orienteeritud lähenemist ka lisatud, mida võib tulevikus kasutada. Sellel praktikumil aga taame, et selline basic funktsionaalne lähenemine oleks kõigil selge.
- Listener. Eriti soblik, kui tahame süntakspuu elementidele lihtsalt reageerida. Oletame, et taheme kõik avaldises esinevad täisarvud ühte hulka kokku koguda. Seda on väga mugav listeneriga teha. Tulemuse tagastamise asemel peab ise seisundit jälgima, mistõttu avaldiste väärtustamine ei ole sellega kõige mugavam.
- Visitor. Laseb meil puud läbida ja väärtust tagastada. Põhimõtteliselt hoolitseb siis lihtsalt nende cast'ide eest ja meil jääb ainult loogikat defineerida. Sellega on ideaalne eval implementeerida.
Listener
Listener idee on see, et läbitakse puu tippe selliselt, et külastatakse kõik 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 järgmised meetodid:
enterAdd(node); // <-- võime seda implementeerida
visit(node.getLeft());
visit(node.getRight());
exitAdd(node); // <-- või siis seda... (või mõlemad)
Repositooriumis on näide, kuidas kokku koguda kõik avaldises esinevad väärtused. Selleks peab ainult exitNum juures väärtus meie hulka lisada. Me saame ka väärtustamist implementeerida, aga selleks peame ise argumente magasini peal arvutama.
Visitor
Visitor on üsna kuulus disainimuster ja sellel on väga palju erinevad variante. Mõnikord fikseerib raamistik tipude läbimise strateegia, aga kasutame selline üldine visitor, mis sisuliselt ainult lahendab seda tüübiteisenduste süntaksit. Me kutsume ise välja visit meetod. Me saame (aga ei pea) siseklassidena implementeerida oma visitorid:
public static int eval(ExprNode expr) {
ExprVisitor<Integer> visitor = new ExprVisitor<Integer>() {
public Integer visitAdd(Add node) {
return visit(node.getLeft()) + visit(node.getRight());
}
public Integer visitNum(Num node) {
return node.getValue();
}
// jne...
};
return expr.accept(visitor);
}
Kõikide nende erinevate enter/exit ja visit meetoditel, mis erinevad ainult sisendtüübi järgi, võib kasutada sama nimi. Kui tahad kasutada eksamil Listener/Visitor, siis ole selleks valmis, et erinevatel AST klasside generaatoritel on natuke erinevad nimetamise konventsioonid.