Automaadid, keeled ja translaatorid

7. kodutöö: AKTK grammatika ja AST

See kodutöö keskendub ANTLR-iga töötamisele AKTK näitel ja koosneb kahest osast:

1. AKTK grammatika
2. AKTK AST

AKTK grammatika

Esimeses osas tuleb koostada ANTLR-i grammatika faili Aktk.g4, mis esitab meie AKTK nimelise keele järgmist etappi. Nüüd võtame keelde juurde muutujate deklareerimise, muutujale omistamise, if-laused, while-tsüklid, lausete järjendi, võrdlemisoperaatorid, unaarse miinuse, sõneliteraalid ning funktsioonide definitsioonid ja väljakutsed.

Näidisprogramm

Järgnev koodijupp (repos failis inputs/sample.aktk) on näide legaalsest AKTK programmist:

/* Muutujate deklaratsioonid */
var palk = -990; var nimi = "Teele";

/* Funktsiooni väljakutse */
print(nimi, palk);

n = int(input("sisesta arv"));

if n > 100 then {
    print("norrmaalne!")
} else {
    print("lahja!!")
};   /* NB! Ära unusta semikoolonit lausete vahel! */

var i = 0;

while i < n do {
    if (i > (3)) then print(i) else pass;
    i = i + 1
}; 

print("The End!") /* viimase lause lõpus pole semikoolonit */

Keele kirjeldus

• Iga selle etapi AKTK programm koosneb ühest või rohkemast semikoolonitega eraldatud lausest. Viimase lause lõpus ei ole semikoolon lubatud.
• Lause võib olla muutuja deklaratsioon, omistamine, if-lause, while-tsükkel, funktsiooni definitsioon, tagastuslause, lihtsalt üks avaldis või loogelistes sulgudes olev lausete jada.
• Lausete jada on semikoolonitega eraldatud 1 või rohkem lauset. Viimase lause lõpus semikoolonit ei ole.
• Avaldis võib olla arvuliteraal, sõneliteraal, muutuja nimi, aritmeetiline tehe (liitmine (+), lahutamine (-), korrutamine (*), jagamine (/), jäägi võtmine (%)), võrdlustehe (==, !=, <=, >=, <, >) või funktsiooni väljakutse (nt. print("tere")).
  • Arvuliteraalid koosnevad numbritest. Esimene number võib olla 0 ainult siis, kui see on arvu ainuke number.
  • Sõneliteraalid algavad ja lõpevad jutumärgiga. Jutumärkide vahel võivad esineda suvalised sümbolid va. jutumärgid ja reavahetused.
    • NB! Kontrolli, et parser ei loeks "tere" kere" korrektseks sõneliteaaliks
    • Vihje: https://github.com/antlr/antlr4/blob/master/doc/lexer-rules.md#lexer-rule-elements
  • Muutuja nime esimene sümbol peab olema väike või suur ladina täht. Järgmistel positsioonidel võib esineda ka numbreid ja alakriipse.
  • Aritmeetiline tehe või võrdlustehe koosneb tehtemärgist ning sellele eelnevast ja järgnevast avaldisest.
    • Erijuhul, kui miinusmärk eelneb avaldisele (nt. -x) ja temast vasakul ei asu avaldis (nt. 3 + rr * -2), siis on tegemist unaarse miinusega. Unaarne miinuse prioriteet on kõrgem kui binaarsetel aritmeetilistel avaldistel (st. -x*3 tõlgendame kui (-x)*3. (Vihje: vasaku naabri mainimine ülalpool oli mõeldud lihtsalt situatsiooni kirjeldamiseks, parsimisel ei ole mõtet üritada unaarse miinust tuvastada vasaku naabri järgi. Piisab sellest, kui tehete prioriteedid on ilusti paigas.)
  • Funktsiooni väljakutse juurde kuulub alati funktsiooni nimi ning alustav ja lõpetav sulg. Sulgude sees võib olla komadega eraldatuna ükskõik kui palju avaldisi. Funktsiooni nimele kehtivad samad reeglid nagu muutuja nimele. NB! -int("3") tuleb mõista kui -(int("3"))!
  • Tehete prioriteet
    • Aritmeetiliste tehete prioriteet on tavapärane.
    • Funtsiooni väljakutsed on kõige kõrgema prioriteediga. Loengus kirjeldatud kihilise avaldisgramatika terminites tähendab see, et suurima prioriteediga tehte argumentideks võivad lisaks literaalidele ja muutujatele olla ka funktsiooni väljakutsed.
    • Kõik võrdlustehted on sama prioriteediga, mis on aritmeetiliste tehete prioriteedist madalam (nt. 3 * 4 > x+1 on sama mis (3 * 4) > (x+1)).
    • Võrdlustehteid ei või kasutada assotsiatiivselt, st. a < b < c või x == y+2 <= 3 ei ole lubatud. Samas lubame kirjutada nt. (a < b) < c või x == (y+2 <= 3).
  • Erinevatel andmetüüpidel me praegu vahet ei tee, st. on lubatud nt. "tere" - 34.
  • Iga (alam)avaldise ümber võib paikneda ükskõik kui palju paare ümarsulge.
• If-lause algab võtmesõnaga if, millele järgneb avaldis, seejärel võtmesõna then, seejärel lause, seejärel võtmesõna else ja selle järel jällegi lause.
• While-tsükkel algab võtmesõnage while, millele järgneb avaldis, seejärel võtmesõna do ja lõpuks lause.
• Muutuja deklaratsioon algab võtmesõnaga var, millele järgneb muutuja nimi. Sellele võib järgneda koolon ja muutuja tüüp. Eelnevatele võib järgneda võrdusmärk ja avaldis. Muutuja tüübile kehtivad samad reeglid nagu muutuja nimele. Avaldis võib esineda ka siis, kui tüüpi pole.
• Omistuslause koosneb muutuja nimest, võrdusmärgist ja avaldisest.
• Funktsiooni definitsioon algab võtmesõnaga fun, millele järgneb funktsiooni nimi. Sellele järgnevad sulgudes komadega eraldatud funktsiooni parameetrid. Sellele võib järgneda nool (->) ja tagastustüüp. Kõige lõpus on loogelistes sulgudes olev lausete jada.
  • Funktsiooni parameeter koosneb nimest, koolonist ja tüübist. Siin on tüüp kohustuslik.
• Tagastuslause koosneb võtmesõnast return ja avaldisest.
• Kommentaarid käivad märkide /* ja */ vahele. Kommentaari sisu osas mingeid kitsendusi ei ole (va. see, et kommentaar ei saa kunagi sisaldada sümbolite jada */).
  • Näide: programmi print("tere") /* kuvab "tere" */ ja lõpetab */ puhul peab parser lugema kommentaariks ainult /* kuvab "tere" */, sellele järgnev osa on süntaksiviga.
  • Vihje: http://www.rexegg.com/regex-greed.html
  • Kuidas panna parser kommentaare ignoreerima: https://github.com/antlr/antlr4/blob/master/doc/lexer-rules.md#skip
• Kõikide lekseemide vahel ning programmi alguses ja lõpus võib olla suvaline arv tühikuid, tabulaatoreid või reavahetusi.

Soovitused

• Ära unusta, et programm võib koosneda ka ainult ühest avaldisest, nt. 3 ja x on legaalsed programmid.
• Meil on olnud IntelliJ ANTLR pluginaga probleeme, kui lekseri või parseri reeglite nimedes on kasutatud täpitähti. Parem oleks neid vältida.
• Mitte kasutada parserireeglite nimesid "if", "while" jne, kuna need tekitavad ANTLR'i sees sisemisi konflikte. See väljendub selliste erroritena: symbol if conflicts with generated code in target language or runtime.
• Näiteprogrammides tunneme praegu huvi vaid süntaksi vastu, semantilised kontrollid (nt. see, kas kasutatakse ilma deklareerimata muutujaid) meid praegu ei huvita.

AKTK AST

Teises osas tuleb esimeses osas loodud grammatika ja ANTLR-i kaasabil defineerida klassi AktkAst meetod parseTreeToAst, mis annab AKTK programmile vastava abstraktse süntaksipuu, mida esitatakse klassi AstNode alamklassidega.

Selle saavutamiseks on vaja:

1. kirjutada ANTLR-i grammatika Aktk.g4 (kodutöö esimene osa);
2. genereerida ANTLR-i abil Aktk.g4 grammatikast AKTK lekser ja parser (koos abiklassidega);
3. kirjutada kood, mis genereeritud parseri abil teisendab sõnena esitatud programmi parse-puuks;
4. kirjutada kood, mis teisendab parse-puu abstraktseks süntaksipuuks (kodutöö teise osa tuum!).

Soovitused

• Vaata üle AST klasside kirjeldused (dokumentatsiooni leiad klasside ja meetodite päistest). Uuri ka klassihierarhiat (IntelliJ).
• AstNode.toString() näitab puu struktuuri tekstilisel kujul.
• AstVisualizer-i abil saab puu visuaalselt joonistada.
• Kui sulle ei meeldi parse-puus liikumine getChild indeksite järgi, siis uuri, milliseid kasulikke meetodeid on konkreetetel Context klassidel ja kuidas alamtippe saab ise nimetada.
• Võimaliku lahenduse alguse leiad siit.
• Näiteprogrammides tunneme praegu huvi vaid struktuuri vastu, semantilised kontrollid (nt. see, kas kasutatakse ilma deklareerimata muutujaid) meid praegu ei huvita.

Esitamine

• Esitada tuleb vähemalt järgmised failid:
  • Aktk.g4
    • Nagu failinimi juba viitab, peab grammatika nimeks olema Aktk.
  • AktkAst klass
• Esitada ei ole vaja:
  • Genereeritud klasse (AktkLexer.java, AktkParser.java, AktkListener.java, AktkBaseListener.java, AktkVisitor.java ja AktkBaseVisitor.java)
  • Genereeritud .token ja .interp laiendiga faile (Aktk.interp, Aktk.tokens, AktkLexer.interp ja AktkLexer.tokens)

Video juhuks, kui jääd alustamisega hätta: AktkAst-i algus.