Automaadid, keeled ja translaatorid 2016/17 kevad

Genereeritud parseri kasutamine parse-puu saamiseks

Jätkame nüüd eelmise nädala kodutööga, kus arendasime grammatika AKTK.g4. (Kui endal on jäänud tegemata, siis võib kasutada näidislahendus sol kataloogist. Praktikumide jaoks on sellest lahendusest koopia failis AKTKDemo.g4, et see teie enda tööd ei segaks.) Kui gradle'i käsk generateGrammarSource õnnestus, siis tekitatakse failid kataloogis gen/java/kodu8. 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:

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
        • OmistamineContext
        • MuutujaDeklaratsioonContext
        • AvaldisContext
        • Avaldis5Context
          • VordlemineContext
          • TriviaalneAvaldis5Context
        • Avaldis4Context
          • LiitmineLahutamineContext
          • TriviaalneAvaldis4Context
        • Avaldis3Context
          • KorrutamineJagamineContext
          • TriviaalneAvaldis3Context
        • Avaldis2Context
          • UnaarneMiinusContext
          • TriviaalneAvaldis2Context
        • Avaldis1Context
          • FunktsiooniValjakutse
          • TriviaalneAvaldis1Context
        • Avaldis0Context
          • ArvuliteraalRContext
          • SoneliteraalRContext
          • MuutujaNimiRContext
          • SuluavaldisContext

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 lisaks veel VordlemineContext või TriviaalneAvaldis5Context tüüpi.

Kõik AKTK programmide parsimisel tekkinud parse-puu tipud kuuluvad mõnda nendest klassidest. Klassinimed on meile puu läbimisel teetähiseks -- instanceof abil konkreetse tipu klassi kontrollides saame teada, millist süntaktilist konstruktsiooni me parasjagu vaatame.

Seda klassihierarhiat on võimalik vaadata ka IDE-st lahkumata. Eclipse'is tuleks võtta fookusesse klass ParseTree ja vajutada klahvi F4, IntelliJ-s klõpsata klassi ParseTree nimel ja vajutada Ctr+H.

Parse-puu "käsitsi" läbimine

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. Kui etteantud programm on keerulisem, siis anname lihtsalt vea.

	static int evaluate(ParseTree tree) {

		// Tipp tüübiga ArvuliteraalRContext vastab grammatikas 
		// märgendile ArvuliteraalR.
		// Siin tuleb lihtsalt küsida selle tipu tekst ja teisendada 
		// see täisarvuks
		if (tree instanceof ArvuliteraalRContext) {
			...
		}

		// Järgmise juhtumi mõistmiseks otsi grammatikast üles 
		// sildid KorrutamineJagamine ja LiitmineLahutamine -- 
		// loodetavasti on siis arusaadav, miks siin just nii toimitakse.
		else if (tree instanceof KorrutamineJagamineContext
				|| tree instanceof LiitmineLahutamineContext) {

			...
		}

		// Järgmine juhtum käsitleb vahetippe, 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 on kõigil nendel tiputüüpidel
		// (lihtsate programmide) puhul täpselt 1 alluv ja seetõttu saame
		// kõiki neid käsitleda sama skeemiga.
		else if (tree.getChildCount() == 1) {
			return evaluate(tree.getChild(0));
		}

		// Kui me satume mingi muu tipu juurde, siis anname praegu vea,
		// sest antud ülesandes ei üritagi me toetada kõiki legaalseid
		// AKTK programme.
		else {
			throw new UnsupportedOperationException
				("Selle tiputüübi väärtustamine ei ole praegu toetatud");
		}
	}

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.