Arvutiteaduse instituut
  1. Esileht
  2. Automaadid, keeled ja translaatorid
EN
Logi sisse

Automaadid, keeled ja translaatorid

  • Üldinfo
  • Ajakava
  • Eksami näidised
  • Teemad
    • 1. Soojendus
    • 2. Regulaaravaldised
    • 3. Automaadid
    • 4. Avaldise struktuur
      • Avaldispuu läbimine
        • Pythoni avaldiste struktuur*
        • Java AST analüüs*
      • Eksami alusosa!
      • Regulaaravaldiste analüüs
      • Kodutöö
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Süvendus
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

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.

  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo