Automata, Languages and Compilers 2018/19 spring

8. kodutöö: AKTK grammatika

Selles kodutöös tuleb koostada ANTLR-i grammatika, mis esitab meie AKTK nimelise keele järgmist etappi.

Keele kirjeldus

Selles etapis võtame keelde juurde kommentaarid, muutujate deklareerimise, olemasolevale muutujale omistamise, if-laused, while-tsüklid, lausete järjendi, võrdlemisoperaatorid, unaarse miinuse, sõneliteraalid ning funktsioonide väljakutsed ja definitsioonid.

Järgnev koodijupp 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 */

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

NB! Ära unusta, et programm võib koosneda ka ainult ühest avaldisest, nt. 3 ja x on legaalsed programmid.

NB! Meil on olnud IntelliJ ANTLR pluginaga probleeme, kui lekseri või parseri reeglite nimedes on kasutatud täpitähti. Parem oleks neid vältida

NB! 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

NB! Näiteprogrammides tunneme praegu huvi vaid süntaksi vastu, semantilised kontrollid (nt. see, kas kasutatakse ilma deklareerimata muutujaid) meid praegu ei huvita.

Tingimused

• Esitada tuleb vaid ANTLR-i grammatika fail Aktk.g4.
• Nagu failinimi juba viitab, peab grammatika nimeks olema Aktk.
• Grammatikas peab olema reegel nimega programm, mis aktsepteerib ülalpool defineeritud keele programme. Teiste reeglite nimetamise osas kitsendusi pole.
• Grammatikat testitakse erinevate programmidega. Mida rohkem legaalseid programme antud grammatika aktsepteerib ja mida rohkem mittelegaalseid programme tagasi lükkab, seda rohkem punkte lahendus annab.