Automata, Languages and Compilers 2018/19 spring

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 sellise harjutuse, kus esitame mõistlikul kujul aritmeetilise avaldise. Proovige defineerida eval meetod, mis väärtustab avaldise.

    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 meetodi väliselt. Klassis ExprAnalyzer on samuti eval meetod, mis võiks arvutada sama tulemuse ehk võiks kehtida expr.eval() == ExprAnalyzer.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 tipude 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 seda implementeerida
                visit(node.getLeft());
                visit(node.getRight());
                exit(node);  // <-- või siis seda... (või mõlemad)