Automaadid, keeled ja translaatorid

Eesti loogikute keel Estolog

x := 0;
y := 1;
a := (x JA y);
b := (x VOI y);

(KUI (x = y) SIIS a MUIDU b)

Estolog on tõeväärtustega arvutamise keel, kus saab lisaks kontrollida võrdust, moodustada tingimusavaldisi ning defineerida muutujaid. Seda kõike saab teha imeilusas eesti keeles! Keele abstraktne süntaks on rahvusvaheline (ehk suhteliselt igav), aga küll saame eesti keele omapäraga tegeleda põhiosa ülesandes...

Paremal on üks programm estologi (konkreetses) süntaksis. Selle näidisprogrammi käivitamise tulemus on true. Estolog oleks muidugi vastanud eesti keeles, aga kuna implementeerime Javas, siis saame tulemuseks Java tõeväärtustüüpi väärtuse.

AST

Estologi AST klassid paiknevad proovieksam.ast paketis. Keele konstruktsioone esitavad järgmised EstologNode alamklassid:

• EstologLiteraal, EstologMuutuja — tõeväärtusliteraal ja muutuja;
• EstologJa, EstologVoi — konjunktsiooni ja disjunktsiooni operaator;
• EstologVordus — kahe avaldise võrdsuse kontrollimise operaator;
• EstologKui — tingimusavaldis (ternaarne operaator);
• EstologDef — muutuja definitsioon;
• EstologProg — terviklik programm, mis koosneb definitsioonidest ja kehast ehk täpselt ühest avaldisest (mis pole definitsioon).

Klassis EstologNode on staatilised abimeetodid, millega saab mugavamalt abstraktse süntaksipuu luua. Nende abil saab ülaloleva näidisprogrammile vastava süntaksipuu ise ehitada:

prog(
    kui(vordus(var("x"), var("y")), var("a"), var("b")),

    def("x", lit(false)),
    def("y", lit(true)),
    def("a", ja(var("x"), var("y"))),
    def("b", voi(var("x"), var("y")))
)

Alusosa: EstologEvaluator

Väärtustamisele kehtivad järgmised nõuded:

1. Binaarsed operaatorid jälgivad standardseid loogikareegleid.
2. Tingimusavaldis on samuti standardne: sõltuvalt tingimuse väärtusest tuleb kasutada ühe või teise haru avaldise väärtust.
3. Tingimusavaldise muidu-haru võib puududa (st on null). Kui sellise tingimusavaldise tingimus on väär, siis on tingimusavaldis tervikuna tõene.
4. Programmi väärtuseks on selle keha (mitte-definitsioonist avaldise) väärtus.
5. Programmi definitsioonid tuleb väärtustada enne programmi avaldise väärtustamist, mis võib sisaldada viiteid defineeritud muutujatele.
6. Programmi definitsioonid tuleb teostada selles järjekorras nagu nad listis on, kusjuures iga definitsiooni avaldis võib sisaldada viiteid eelnevalt defineeritud muutujatele.
7. Esialgu pole defineeritud ühtegi muutujat. Defineerimata muutujate kasutamine peab viskama NoSuchElementException-i.
8. Programmis on lubatud üht muutujat defineerida mitu korda, kusjuures muutuja väärtuseks on tema viimati defineeritud avaldise väärtus.
9. Võib eeldada, et väärtustatav programm sisaldab ainult ühte EstologProg tippu, mis on kõige välimine, st ükski sisemine avaldis pole omakorda programm, millel on oma sisemised definitsioonid.

Lahendus esitada Moodle'isse.

Põhiosa: EstologAst

a := kala JA lind;   
b := 0 = (kass VOI a NING kala); 
c := KUI a = b SIIS 1 MUIDU b JA c;
KUI a SIIS KUI c SIIS kala MUIDU hiir

Estolog keele grammatika tuleb implementeerida failis Estolog.g4 ja parsepuust AST-i koostamine klassis EstologAst. Paremal on natuke pikem näide süntaktiliselt korrektsest programmist. Mõned muutujad on defineerimata, aga see ei ole süntaksanalüsaatori mure.

Süntaksile kehtivad järgmised nõuded:

1. Literaaliks võib olla 1 või 0, 1 esindab tõest väärtust ja 0 väära väärtust.
2. Muutuja koosneb ühest või rohkemast ladina suur- või väiketähest.
3. Binaarne operaator 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, =. Pane tähele, et NING on madalama prioriteediga kui VOI, aga loogiline tähendus on tal sama kui JA-l.
4. 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 binaarsed operaatorid. Mitmesuse korral on muidu-haru seotud kõige viimase KUI-lausega (täpselt nagu Java if-laused).
5. Avaldistes võib kasutada sulge, mis on kõige kõrgema prioriteediga.
6. Definitsioon koosneb muutujanimest, võtmesõnast := ja avaldisest.
7. Programm koosneb definitsioonidest (mida võib olla ka null tükki) ja lõppavaldisest. Definitsioonid on omavahel ja lõppavaldisest eraldatud semikoolonitega (;).
8. Tühisümboleid (tühikud, tabulaatorid, reavahetused) tuleb ignoreerida.

Lahendus esitada Moodle'isse.

Lõviosa: EstologCompiler

Estolog keele CMa-sse kompilaator tuleb implementeerida klassis EstologCompiler. Kompileeritud programmi käivitamise tulemus peab olema sama nagu siis, kui seda EstologEvaluatoriga väärtustada, st kehtivad kõik ülaltoodud väärtustamisreeglid. Tõeväärtused teisendame täisarvudeks CMaUtils.bool2int abil.

Kompileeritud programmidele kehtivad järgmised nõuded:

1. Programmi (st selle mitte-definitsioonist avaldise väärtus) peab täitmise lõpuks olema stacki pealmine element.
2. Stacki kasutus peab olema mõistlik:
   1. Defineeritud muutujate väärtused peavad paiknema stacki alguses defineerimise järjekorras; st esimesena defineeritud muutuja stacki aadressil 0, teisena defineeritud muutuja stacki aadressil 1 jne.
   2. Samanimelisele muutujale uuesti defineerimine peab väärtuse salvestama selle muutuja olemasolevale stacki aadressile, mitte kasutusele võtma uut.
   3. Programmi täitmise lõpuks ei tohi olla stackis muid üleliigseid väärtusi.
3. Programmi täitmise algul on stack tühi. Defineerimata muutujate kasutamine peab viskama NoSuchElementException-i kompileerimise ajal.

x := 0;
y := 1;
a := (x JA y);
b := (x VOI y);

(KUI (x = y) SIIS a MUIDU b)

Paremal oleva programmi kompileerimisel saadud CMa koodi täitmise lõpuks peaks olema stack [0, 1, 0, 1, 1], kus esimesena on muutuja x väärtus, teisena muutuja y väärtus, kolmandana muutuja a väärtus, neljandana muutuja b väärtus ja viimasena kogu programmi väärtus.

Lahendus esitada Moodle'isse.