Automaadid, keeled ja translaatorid 2018/19 kevad

Eksami põhiosaks harjutamine

Eksami põhiosaks harjutamiseks lahendame 7. praktimumis tehtud KalaParser ülesande kasutades ANTLRi. Järgneb ka mõned ülesanded iseseisvaks lahendamiseks.

Kala grammatika

Me tahame esmalt kirjutada ANTLRi grammatika (faili Kala.g4) ning seejärel koostada ASTi (faili KalaAst.java) kasutades 7. praktikumis defineeritud KalaNode klasse.

Meeldetuletuseks: grammatika koosneb sulgudega ümbritsetud elementide listist, list võib olla ka tühi. Listi elemendid on omavahel eraldatud komaga, elementideks võivad olla väiketähtedest koosnev muutuja nimi, võtmesõna "null" või sulgudega ümbritsetud list. Lekseemide vahel ja ümber võib olla suvaline arv tühikuid ja tabulaatoreid. Korrektne sisend on näiteks (kala, (x,y , null, (), (kala,()) )).

Soovitatav on mõelda grammatika kirjelduse järgi ise välja, aga võib kasutada ka käsitsi parsimisel toodud grammatikat:

Peale grammatika loomist tuleb siis lasta ANTLR-l genereerida lekser ja parser ning seejärel täiendada KalaAst.java faili, et koostada AST. ASTi elemente saab luua staatiliste meetoditega mkNull, mkIdent ja mkList (failis KalaNode.java).

Loogika (eesti keeles)

Avaldis võib olla muutuja, literaal, tingimusavaldis, loogiline tehe või sulgudega ümbritsetud avaldis.

• Muutuja koosneb ühest või rohkemast ladina suur- või väiketähest.
• Literaaliks võib olla 1 või 0, 1 esindab tõest väärtust ja 0 väära väärtust.
• Tingimusavaldis algab võtmesõnaga KUI, millele järgneb avaldis, seejärel võtmesõna SIIS, millele omakorda järgneb avaldis. Seejärel võib tulla võtmesõna MUIDU ning avaldis. Tingimusavaldis on madalama prioriteediga kui loogiline tehe.
• Loogiline tehe koosneb kahest avaldisest, millede vahel on operaator (NING, VOI, JA, =), operaatorid on vasakassotsiatiivsed v.a. =, mis ei ole üldse assotsiatiivne (s.t. a = b = c ei ole lubatud). Kõige madalama prioriteediga on NING, seejärel kasvavas järjekorras VOI, JA, =. Sulud on kõige kõrgema prioriteediga.
• Avaldiste vahel ja ümber võib olla suvaline arv tühikuid ja tabulaatoreid.

Näited legaalsetest avaldistest:

1;   a;   kala JA 0;   1 = a VOI z VOI a = (1 JA a NING d); 
KUI a = b SIIS 1 MUIDU b JA c;   KUI a SIIS KUI c SIIS e MUIDU 1

AST moodustatakse LoogikaNode alamklassidest. Iga grammatikas kirjeldatud avaldise tüübi jaoks on oma AST klass. Loogilise tehte jaoks on kolm eraldi klassi: JaNode, VoiNode, VordusNode (eraldi klassi NING jaoks pole, kuna AST määrab üheselt ära tehete järjekorra ja tema tähendus on sama nagu JA). AST moodustamisel tuleb kasutada LoogikaNode.java staatilisi meetodeid (lit – literaali tipp, var – muutuja, ja, voi, vordus, kuiSiis).

Hulk programmid

Programm koosneb lausetest, mis paiknevad kõik omaette real. Tühje ridu ei ole. Lause võib olla kas omistamine või hulga muutmine. Iga lause lõpus võib olla püstkriipsuga eraldatud tingimus.

• Omistamislause algab hulgamuutujaga, järgneb :=, millele omakorda järgneb avaldis.
• Hulga muutmise lause algab hulgamuutujaga, järgneb kas <- (elementide lisamine hulka) või -> (elementide eemaldamine), millele järgneb üks või mitu komaga eraldatud elementi.
• Hulgamuutuja tähistatakse ühe ladina suurtähega, elementi ühe ladina väiketähega.
• Avaldiseks võib olla hulgamuutuja, hulgaliteraal, hulgatehe või sulgudega ümbritsetud avaldis.
• Hulgaliteraal koosneb loogeliste sulgude vahel asuvast komaga eraldatud elementidest (võib olla tühi), näiteks {a,b,c}.
• Hulgatehe koosneb kahest avaldisest, mille vahel on operaator. Operaatoriteks võivad olla + (ühend), & (ühisosa), - (vahe). Operaatorite prioriteedid on samad ning kõik on vasakassotsiatiivsed.
• Tingimus võib olla:
  • Elemendi sisaldumine hulgas, koosneb elemendist ja avaldisest, mille vahel on võtmesõna in.
  • Alamhulgaks olemine, koosneb kahest avaldisest, mille vahel on võtmesõna subset.
• Avaldiste vahel ja ümber võib olla suvaline arv tühikuid ja tabulaatoreid.

Näited legaalsetest lausetest:

A := B
A := {x, y, z} + A
B := A & (B - C) & {}
A := A + {x, y} | x in A + B
A <- x | {x} + {y} subset A
A -> a, b, c

AST moodustatakse HulkNode alamklassidest. Iga AST algab HulkProgramm tipuga, mis sisaldab listi HulkLause tippudega. HulkLause esindab omistamist, koosneb hulgamuutuja nimest (millele omistatakse), avaldisest (mida omistatakse) ning tingimusest (kas omistatakse). HulkAvaldiseks võivad olla HulkMuutuja, HulkLiteraal (elementide list) ja HulkTehe (ühend, ühisosa, vahe). HulkTingimus koosneb alamavaldisest ja ülemavaldisest.

AST moodustamisel tuleks kasutada HulkNode.java staatilisi meetodeid. Pane tähele, et elementide lisamise/eemaldamise jaoks eraldi lauseliiki ei ole, mõtle kuidas teisendada see tavaliseks omistamiseks nii, et hulga sisu oleks siiski sama. Samuti pole eraldi tippe mõlema tingimusliigi jaoks, mõtle kuidas elemendi sisalduvust esitleda alamhulgaks olemise kaudu.

Let-sidumisega avaldised

Avaldiseks võib olla täisarv, muutuja nimi, lahutamine, sidumisega avaldis, summeerimine või sulgudega ümbritsetud avaldis.

• Muutuja nimi koosneb ühest või rohkemast ladina suur- ja/või väiketähest.
• Lahutamine koosneb kahest avaldisest, mille vahel on miinusmärk. Lahutamine on vasakassotsiatiivne ning suurema prioriteediga kui sidumine või summeerimine.
• Sidumisega avaldis algab võtmesõnaga let, millele järgneb muutuja nimi, seejärel võrdusmärk, millele järgneb avaldis (taolisi muutujale omistamisi võib järjestikku olla rohkem kui üks, sellisel juhul on nad üksteisest semikoolonitega eraldatud). Sidumine lõpeb võtmesõnaga in, mille järel tuleb avaldis.
• Summeerimine algab võtmesõnaga sum, millele järgneb muutuja nimi, võrdusmärk, avaldis, võtmesõna to, avaldis (jällegi võib taolisi omistamisi olla rohkem kui üks, sel juhul semikoolonitega eraldatud). Summeerimine lõpeb jällegi võtmesõnaga in ning sellele järgneva avaldisega.
• Avaldises võib olla suvalisel kohal tühikuid, tabulaatoreid ja reavahetusi. Avaldiste näidiste jaoks uuri teste.

Näited legaalsetest avaldistest:

a - (10 - TtU)
let x=1-1 in x-17
sum x=1 to 4 in x
let x = 1;y = 2 in 1
let x = 666 in (sum i = 0 to 3; j = 0 to i in i-j) - 1

AST moodustatakse LetAvaldis alamklassidest. Avaldiseks võib olla: täisarv (LetArv); muutuja (LetMuutuja); kahe avaldise vahe (LetVahe); muutuja sidumisega avaldis (LetSidumine, koosneb seotava muutuja nimest, muutujale omistatavast avaldisest ning avaldise kehast); summeeriv avaldis (LetSumma, koosneb muutuja nimest, muutuja algväärtus avaldisest, muutuja lõppvääärtus avaldisest ning avaldise kehast).

AST moodustamisel võib kasutada LetAvaldis.java staatilisi meetodeid. Pane tähele, et sidumise ja summerimise klassides on ainult üks muutuja nimi, aga grammatikas on lubatud semikoolonitega omistada mitmele muutujale. Siinkohal tuleks tõlgendada, et let x=1; y=2 in x-y on samaväärne avaldisega let x=1 in (let y=2 in x-y). Mõtle, mis järjekorras oleks siin kõige mõtekam omistamisi läbi käia.