Automata, Languages and Compilers 2017/18 spring

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

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. 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. IntelliJ-s klõpsata klassi ParseTree nimel ja vajutada Ctr+H, Eclipse'is tuleks võtta fookusesse klass ParseTree ja vajutada klahvi F4.

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 ArvuliteraalContext vastab grammatikas 
		// märgendile Arvuliteraal.
		// Siin tuleb lihtsalt küsida selle tipu tekst ja teisendada 
		// see täisarvuks
		if (tree instanceof ArvuliteraalContext) {
			...
		}

		// 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.