Automaadid, keeled ja translaatorid

Dialektiline tingimuskeel Dialoog

x on int!
Arvuta: 
  Kas 5 + 5 on 10? 
    Jah: Oota 2 + x Valmis * 5
    Ei: 100 
  Selge 

Keel Dialoog koosneb deklaratsioonidest ja ühest avaldisest. Tegemist on täiesti tavaliste avaldistega, seega abstraktne süntaks on sisuliselt väike fragment Java omast. Süntaks on aga parandatud, et programmeerimine oleks lihtinimesele palju intuitiivsem! Paljude inimeste arvates võikski algõpe üle minna Dialoog keelele.

AST

Keele AST klassid asuvad paketis toylangs.dialoog.ast. Keele struktuuri esitamiseks kasutame järgmised DialoogNode alamklasse:

• DialoogProg — terve programm, mis sisaldab muutujate deklaratsioonide listi ja ühte avaldist;
• DialoogDecl — muutuja deklaratsioon: muutuja nimi ja tüüp (täisarv/tõeväärtus).
• DialoogLitBool (tõeväärtusliteraal), DialoogLitInt (täisarvliteraal) ja DialoogVar (muutuja);
• DialoogUnary (unaarsed), DialoogBinary (binaarsed) ja DialoogTernary (ternaarsed) — need esitavad kõik aritmeetilisi, loogilisi ja võrdlevaid tehteid.

Ainsaks ternaarseks tehteks on Javast tuttav tingimusavaldis (b?e1:e2), aga teisi tehteid on meil siin väga palju! Aja kokkuhoidmiseks on DialoogBinary ja DialoogUnary klassides defineeritud enum-klassid, millel on kasulikke abimeetodeid tehete loomiseks, näiteks

• Operaatori rakendamine Java koodis: DialoogAdd.toJava().apply(5,10).
• Teisendamine CMa käsuks: DialoogAdd.toCMa() (ilmub repos lõviosa ajaks).
• Vastava AST tipu loomine sümboli põhjal: DialoogNode.binop("+", e1, e2).

Ülesandeid saab ka ilma nendeta lahendada, näiteks saab kirjutada switch-lause üle kõikide operaatorite, aga see on muidugi väga tüütu! Klassis DialoogNode on väga palju staatilised abimeetodid, millega saab AST lugavalt luua. Näiteks vastab ülalolevale näitele järgmine AST:

prog(
  decls(iv("x")), 
  ifte(
    eq(add(num(5), num(5)), num(10)), 
    mul(add(num(2), var("x")), num(5)), 
    num(100)
  )
)

Seal on ternaarse operaatori jaoks kasutatud abimeetod ifte (if-then-else) ja binaarsete jaoks tavapärasemad nimed. Kõik need sünonüümid on DialoogNode klassis defineeritud.

Alusosa: DialoogEvaluator

Väärtustamise meetod eval tuleb defineerida klassis DialoogEvaluator. Kui vaadata ülevalt ainult ASTi, siis on keele allolev struktuur täiesti standardne (igav), aga võrreldes siaamaani nähtud näidiskeeltega on üheks erinevuseks see, et tulemuseks võib olla nii täisarv kui ka tõeväärtustüüp. Tagastada tuleb seega Object klassi isend!

1. Literaalide tulemuseks tuleb tagastada vastavalt täisarv int või tõeväärtustüüp bool.
2. Muutuja väärtus tuleb otsida keskkonnast env. Kui programmis kasutatakse deklareerimata muutujat, siis tuleks visata UndeclaredVariableException, mis on DialoogEvaluator klassis juba defineeritud. Seda tuleb teha isegi siis, kui muutuja väärtus on keskkonnas olemas!
3. Binaarsete ja unaarsete tehete jaoks on võimalik kasutada ülevalmainitud toJava meetodit.
4. Ainsaks ternaarseks tehteks on meile juba tuttav tingimusavaldis. See käitub siin täpselt nagu Javas: kui esimene avaldis on tõene, siis on tulemuseks on teine avaldis; vastasel korral tagastatakse kolmandat.
5. Muutuja deklaratsiooni korral midagi ei taastata, aga muutuja nime peab meelde jätta, et saaks kontrollida muutujate kasutust.
6. Terve programmi täitmisel tuleb lihtsalt läbida deklaratsioone ja siis tagastada programmi avaldise tulemuse. (ANTLRi vaikeimplementatsioon läbib kõik lapsi ja tulemuseks on viimane — äkki see ongi täpselt see, mis vaja?)

Põhiosa: DialoogAst

a on bool! x on int!
Arvuta: 
  2 * Oota 2 + 2 Valmis -
  Kas 5 + 5 on 10? 
    Jah: Kas 5 + 5 on 10? 
           Jah: 35 * x
           Ei: 100 
         Selge 
    Ei: 100 
  Selge 
+ 30 + Kas jah & a?
            Jah: 10
            Ei: 300
       Selge

Dialoog keele grammatika tuleb implementeerida failis Dialoog.g4 ja parsepuust AST-i koostamine klassis DialoogAst. Siin on pikem näide selles keeles kirjutatud programmist. Keel on niivõrd intuitiivne, et selgituste lisamine tundub kuidagi kohatu, aga kuna kõik ei pruugi mõelda nii maalähedaselt, siis proovime natuke formaalsemalt.

1. Programmi üldine struktuur on deklaratsioonide jada, millele järgneb sõne Arvuta: ja üks avaldis.
2. Deklaratsioon koosneb muutuja nimest (üks või enam ladina väiketähte), märksõna on ja siis tüübi nimi, mis on kas tõeväärtustüüp (bool) ja täisarvutüüp tõeväärtustüüp (int). Selleks, et keelt oleks võimalik kasutada ka lasteaias programmeerimise õpetamisel, osutus kasulikuks lubada nende sõnede järele ladina väiketähti lisada. Seega ka näiteks intike ja boolakas on vastavalt täisarvu- ja tõeväärtustüübi tähised. Väga oluline on see, et iga deklaratsioon lõpeb ühe hüüumärgiga!.
3. Avaldis on täiesti tavaline aritmeetiline avaldis (ülesehituse poolest). Literaalideks on täisarvud ja tõeväärtusliteraalid. Täisarvud on täiesti tavalised täisarvud, aga tõeväärtusliteraalideks on meil väikeste tähtedega sõned jah ja ei võõrsõnade true ja false asemel.
4. Lisaks literaalidele on avaldises ka muutujad (ühest või rohkemast ladina väiketähest koosnevad sõned).
5. Siis on terve hunnik unaarsed ja binaarsed operatsioone, mille süntaks on imekombel jäetud ilustamata.
   • Lubatud unaarsed operatsioonid on eitus (!) ja vastandarvu (-) võtmine.
   • Binaarsed operatsioonid, alustades kõige kõrgemast prioriteedist, on korrutamine/jagamine, liitmine/lahutamine, võrduse kontroll (operaatoriks on sõne on), loogiline konjunktsioon (&) ning disjunktsioon (|). Erinevalt Javast on viimased sümbolid ainult ühekordselt.
   • Ternaarse tingimusavaldise süntaks on eriti loomulik: see algab sõnega Kas, millele järgneb avaldis ja küsimärk ?. Seejärel on märksõna Jah: koos avaldisega ja märksõna Ei: koos oma avaldisega. Märksõnad on mõlemad suure algustähega. Konstruktsioon lõpeb märksõna Selge, sest nii ongi.
6. Iga avaldise ümber võib panna sulud, et muuta süntakspuu struktuuri. Sulgude tähisteks selles keeles on Oota ja Valmis. See teeb asja veel selgemaks.
7. Kõiki tühisümboleid (tühikuid, tabulaatoreid, reavahetusi) võib ignoreerida. Joondamine on ülalolevas näites ainult koodi struktuuri veelgi selgemaks tegemiseks. Keele ametlikus stiilijuhendis soovitatakse just nii indenteerida, aga kompilaator lubab ka teistmoodi. Ainsad erandid: koolon kuulub märksõna juurde; kahe ladinatähtedest koosneva keelestruktuuri osa vahel peab olema vähemalt üks tühik (x on bool! mitte xonbool!).

Lõviosa: DialoogCompiler

Selles osas on kõigepealt vaja genereerida masinkood (meetod compile). Sellega peaks iga lõvi hakkama saama ilma suurema abita. Muutujate väärtused antakse magasinis ette samas järjekorras nagu on programmis deklareeritud. Tõeväärtusmuutujate argumente teisendame täisarvudeks CMaUtils.bool2int abil.

Lisaülesanded: DialoogMaster

Soojenduseks implementeerime järgmised meetodid:

• unusedVars tagastab hulga deklareeritud muutujatest, mida ei ole programmi kehas kuskil kasutatud. (Siin peame silmas ainult tekstuaalset esinemist programmi koodis. Te ei pea analüüsima, kas programmi täitmisel läheb muutujat vaja või mitte.)
• typecheck on igati loomulik meetod. Siin tuleb tagastada TInt või TBool sõltuvalt programmi avaldise tulemustüübist. Kui meil on tüübiviga, siis tuleb visata RuntimeException. Peamine on siin see, et typecheck oleks eval suhtes korrektne: kui typecheck lubab, et tulemustüüp on TInt, siis see peab tagama, et väärtustamisel ei visata ClassCastExceptionit ning kui tulemus tagastatakse, siis on see tõesti Integer tüüpi isend. (Tingimuse korral nõuame, et mõlemad harud oleks sama tüüpi. Sellega keelame mõned korrektsed programmid, aga Java ka ei luba selliseid lauseid nagu int x = true ? 5 : false, kuigi tulemuseks on alati täisarv.)

Ja nüüd meistriülesandeks tuleb implementeerida meetod symbex, mis tagastab etteantud programmi kohta sellise tingimuse, mille korral esialgne programm viskaks erindi defineerimata muutuja tõttu. Testides kasutame ainsa defineerimata muutujana muutujat nimega „error“ ja vaatame mõned näited (Java süntaksiga), et ideest aru saada.

error
5 + 5
x == 10 ? error : 5
x == 10 ? 5 : error
x == 10 ? (x == 11 ? 5 : error) : 5
x == 10 ? (x == 11 ? error : 5) : 5
(x == 10 ? error : 5) + (x == 10 ? 5 : error)

true
false
x == 10
x != 10
x == 10
false
true

Ülesande teeb lihtsamaks see, et tegelikult ei pea nii ilusat tingimust tagastama, vaid piisab mõnest loogiliselt samaväärsest avaldisest. Me testime seda meetodit nii, et väärtustame sisendavaldist teatud väärtuste keskkonnaga ja kui sellega viskab väärtustaja erindi, siis peab tagastatud ebaõnnestumise tingimuse väärtustamisel sama keskkonnaga tagastama true. Kui väärtustamisel ei tule erindit, siis peab tingimuse väärtustamine tagastama false.