Genereeritud parseri kasutamine parse-puu saamiseks
Jätkame nüüd eelmise nädala kodutööga, kus arendasime grammatika Aktk.g4.
Järgnev materjal eeldab sol kataloogis oleva näidislahenduse kasutamist ja nimetusi. Esialgu võib olla mõistlik asendada enda grammatika sellega, sest näidises on reeglite alternatiivid märgendatud, mis teeb puu töötlemise lihtsamaks.
Kui Gradle'i käsk generateGrammarSource õnnestus, siis tekitatakse failid kataloogi src/gen/java/week8. Nüüd saame neid kasutama hakkata. Plaan on teha üks abimeetod, mis võtab argumendiks sõnena antud AKTK programmi, parsib selle ja tagastab parse-puu -- selle andmestruktuuri, mida ANTLR-i IntelliJ plugin sulle grammatikate testimisel graafiliselt näitas.
Kuna siin tuleb lihtsalt teada, kuidas ANTLR-i parserit käivitatakse, siis anname kogu vajamineva koodi ette:
private static ParseTree createParseTree(String program) {
AktkLexer lexer = new AktkLexer(CharStreams.fromString(program));
AktkParser parser = new AktkParser(new CommonTokenStream(lexer));
ParseTree tree = parser.programm();
System.out.println(tree.toStringTree(parser));
return tree;
}
Tegeliku parsimisprotsessi alustab parser.programm(), kõik muu on ettevalmistus. Kui sa oletad, et see programm() viitab samanimelisele reeglile AKTK grammatikas, siis on sul täiesti õigus. Tuleb välja, et ANTLR-i poolt genereeritud parseril on iga grammatika reegli kohta üks meetod, mõnesid kutsub välja parseri klient, mõnda kasutab parser ise teiste reeglite juures.
(Siin on paras hetk piiluda genereeritud klassi AktkParser sisse. Otsi näiteks üles meetod programm() või näiteks whileLause() ja kõrvuta selle meetodi sisu vastava reegliga grammatikas. Kas märkad mingit sarnasust sellega lähenemisega, kuidas me käsitsi parsereid kirjutasime?)
parser.programm() poolt tagastatav ParseTree on konkreetsest grammatikast sõltumatu andmestruktuur, mis sisaldab endas parsimise tulemust e. programmi struktuuri. Selle struktuuri suluesituse nägemiseks on toodud koodis olev print-lause meetodiga toStringTree().
Näidislahenduse parsepuu
Siin on AKTK programmi 5 + 2 *4 parse-puu graafiline esitus. Uuemad ANTLRi versioonid näitavad ka reeglite juures täpsemalt mitmes alternatiiv valiti (näiteks "avaldis5:2"). Me oleme näidislahenduses pannud alternatiividele märgendid ja plugin peaks seega näitama "avaldis5:TriviaalneAvaldis5". NB! Meil näitab ANTLRi IntelliJ plugin vasakrekursiivsetel reeglitel vale alternatiivi rakendamist, seega peate siin mingil määral ikkagi ennast usaldada. Parsepuu struktuur on siiski õige.
Kui me käivitame eelpool antud funktsiooni selle programmiga (st. createParseTree("5 + 2 *4")), siis me saame sama kujuga andmestruktuuri, mille klass on ParseTree.
ParseTree on ANTLR-isse sisseehitatud klass parse-puu (tipu) esitamiseks, millel on muuhulgas meetodid int getChildCount() ja ParseTree getChild(int childIndex). Nendest meetoditest piisaks puu läbimiseks, aga meid siiski huvitab iga tipu juures ka see, millist süntaktilist konstruktsiooni see tipp tähistab (kui vaatad parse-puu graafilist esitust siis on seal ju näha ka viited meie grammatikale -- programm, avaldis, avaldis5 jne).
Programmi struktuuri täpsemaks esitamiseks genereeris ANTLR koos parseriga ka meie grammatikale spetsiifilised ParseTree alamklassid. Kogu klassihierarhia on järgmine (kõik AKTK spetsiifilised klassid asuvad klassi AktkParser küljes):
- ParseTree
- RuleNode
- RuleContext
- ParserRuleContext
- ProgrammContext
- LauseContext
- LauseteJadaContext
- IfLauseContext
- WhileContext
- TagastuslauseContext
- OmistamineContext
- MuutujaDeklaratsioonContext
- FunktsiooniDefinitsioonContext
- AvaldisContext
- Avaldis5Context
- VordlemineContext
- TriviaalneAvaldis5Context
- Avaldis4Context
- LiitmineLahutamineContext
- TriviaalneAvaldis4Context
- Avaldis3Context
- KorrutamineJagamineContext
- TriviaalneAvaldis3Context
- Avaldis2Context
- UnaarneMiinusContext
- TriviaalneAvaldis2Context
- Avaldis1Context
- FunktsiooniValjakutse
- TriviaalneAvaldis1Context
- Avaldis0Context
- ArvuliteraalContext
- SoneliteraalContext
- MuutujaNimiContext
- SuluavaldisContext
- ParserRuleContext
- RuleContext
- RuleNode
Mõnede klassinimede puhul on selge, et need on tuletatud grammatika vastavate reeglite nimedest, aga selgitust vajavad nende klasside alamklassid (nt. VordlemineContext). Kui uurid grammatika faili, siis näed, et mõnede reeglite alternatiivide järel on kirjutatud mingi märgend (nt. #Vordlemine). Neid märgendeid kasutab ANTLR selleks, et anda parse-puu tippudele võimalikult täpsed tüübid. Näide: kui meil on tipp tüübiga Avaldis5Context, siis me teame, et see tipp on loodud grammatika reegli avaldis5 põhjal; kui me tahame teada ka seda, kumb selle reegli alternatiiv mängus oli, tuleb kontrollida (nt. intanceof-ga) kas tipp on VordlemineContext või TriviaalneAvaldis5Context tüüpi.
Kui tahta grammatika näidislahenduse asemel hiljem ikkagi kasutada enda kirjutatud grammatikat, siis peaks ka seda sobivate alternatiivide märgenditega täiendama, et sellest saadavat puud sama mugavalt töödelda saaks.
Kõik AKTK programmide parsimisel tekkinud parse-puu tipud kuuluvad mõnda nendest klassidest. Need klassid on meile puu läbimisel teetähiseks: visitoriga parse-puud läbides saame iga süntaktilist konstruktsiooni soovitud viisil käsitleda.
Seda klassihierarhiat on võimalik vaadata ka IDE-st lahkumata. IntelliJ-s klõpsata klassi ParseTree nimel ja vajutada Ctrl+H, Eclipse'is tuleks võtta fookusesse klass ParseTree ja vajutada klahvi F4.
Parse-puu läbimine Visitoriga
ANTLRi visitorid
ANTLR genereerib soovi korral koos parseriga veel ühe liidese ja ühe klassi, mis realiseerivad varemnähtud visitor mustri meie grammatika parsepuu jaoks. AKTK puhul on nendeks AktkVisitor ja AktkBaseVisitor. Nende genereerimiseks on juba build.gradle faili lisatud generateGrammarSource reegli juurde vastav käsureaparameeter.
Liides AktkVisitor sarnaneb väga varemnähtud visitor liidestele: siin on meetod iga grammatika reegli ja iga sildi jaoks. Meetod saab argumendiks vastava tüübiga parse-puu tipu ning peab ka midagi tagastama, sõltuvalt visitori enda tagastustüübist.
Alati pole vaja kõikvõimalikke parse-puu tipuklasse eraldi käsitleda, vaid piisab kui teeme midagi sisulist ainult antud ülesannet puudutavate tipuklasside puhul ning ülejäänud vahetippude puhul lihtsalt liigume allapoole. Liidese AktkVisitor implementeerimisel nõuavad Java reeglid aga kõigi meetodite realiseerimist. Selleks, et ka siin programmeerijate vaeva vähendada, genereeris ANTLR koos selle liidesega ka ühe klassi, AktkBaseVisitor, mis implementeerib antud liidese selliselt, et iga tiputüübi juures delegeeritakse töö alluvatele, kui neid on. Seega, kui me tahame teha midagi spetsiifilist vaid üksikute tiputüüpide puhul, siis ei ole meil mõtet mitte implementeerida liidest AktkVisitor, vaid luua alamklass klassile AktkBaseVisitor, kus vaid teatud meetodid on ülekaetud.
Näide (ParseTreeDemo)
Parse-puuga harjumiseks vaatame ühte näidet, kus üritatakse puud läbides arvutada välja aritmeetilise avaldise väärtus. Lihtsuse mõttes eeldab see funktsioon, et etteantud programm (mis on juba parse-puu kujule viidud) sisaldab ainult ühte lauset, see lause koosneb avaldisest ja selles avaldises esinevad vaid aritmeetilised tehted ja täisarvulised konstandid.
private static int evaluate(ParseTree tree) {
AktkBaseVisitor<Integer> visitor = new AktkBaseVisitor<Integer>() {
// Tipp tüübiga ArvuliteraalContext vastab grammatikas
// märgendile Arvuliteraal.
// Siin tuleb lihtsalt küsida selle tipu tekst ja teisendada
// see täisarvuks
@Override
public Integer visitArvuliteraal(ArvuliteraalContext ctx) {
...
}
// Järgmise juhtumi mõistmiseks otsi grammatikast üles
// sildid KorrutamineJagamine ja LiitmineLahutamine --
// loodetavasti on siis arusaadav, miks siin just nii toimitakse.
@Override
public Integer visitKorrutamineJagamine(KorrutamineJagamineContext ctx) {
return binaarneOperatsioon(ctx);
}
@Override
public Integer visitLiitmineLahutamine(LiitmineLahutamineContext ctx) {
return binaarneOperatsioon(ctx);
}
private Integer binaarneOperatsioon(ParserRuleContext ctx) {
...
}
// Ülejäänud juhtumid käsitleb AktkBaseVisitor automaatselt
// visit-ides kõiki alamtippe, sh neid mis antud ülesande
// puhul tähtsat rolli ei mängi. Vaata jälle näidisavaldise
// parse-puu graafilist esitust -- kui me alustame juurtipust,
// siis me peame nende vahetippude (lause, avaldis, avaldis5, jne)
// kaudu jõudma millegi huvitavani. Õnneks saame
// kõiki neid käsitleda vaikimisi skeemiga.
};
return visitor.visit(tree);
}
Katseta seda funktsiooni: kasuta kõigepealt eespool antud funktsiooni createParseTree, et saada mingile AKTK avaldisele (nt. 5 + 2 *4) vastav ParseTree ning ürita seda selle funktsiooniga väärtustada.