Automaadid, keeled ja translaatorid 2020/21 kevad

Nulliga jagamist salliv Safdi

Safdi on aritmeetiliste avaldiste keel, millele on lisatud võimalus nulliga jagamise korral toibuda ja vea asemel väärtustada teine avaldis, mida siin nimetame taastumisavaldiseks (recover expression). Näiteks avaldise x + y / z recover 1 väärtustamise tulemuseks on x + 1, kui z = 0; muidu on see lihtsalt x + y / z.

AST

Keele AST klassid paiknevad toylangs.safdi.ast paketis ja nende ülemklassiks on SafdiNode:

• SafdiNum – arvliteraal;
• SafdiVar – muutuja;
• SafdiNeg – vastandarvu võtmine (unaarne miinus);
• SafdiAdd, SafdiMul – liitmise ja korrutamise binaarsed operaatorid;
• SafdiDiv – jagamise operaator (nulliga jagamise taastumisavaldisega).

Klassis SafdiNode on staatilised abimeetodid, millega saab mugavamalt abstraktseid süntaksipuid luua. Ülalolev avaldis moodustatakse järgmiselt:

add(var("x"), div(var("y"), var("z"), num(1)))

Alusosa: SafdiEvaluator

Klassis SafdiEvaluator tuleb implementeerida meetod eval, mis väärtustab avaldise etteantud väärtuskeskkonnas. Väärtustamisele kehtivad järgmised nõuded:

1. Literaalid, muutujad ja kõik aritmeetilised operaatorid käituvad standardselt. Keele tuumaks on tavalised aritmeetilised avaldised.
2. Defineerimata muutuja väärtustamisel visatakse SafdiException.
3. Kui jagamisel on nimetaja väärtus null ja taastumisavaldist ei ole, siis tuleb samuti visata SafdiException.
4. Kui jagamisel on nimetaja väärtus null, aga taastumisavaldis on olemas, siis tuleb tagastada taastumisavaldise väärtus.
5. Kui nimetaja on null, siis tulemus ei sõltu lugejast. Kui nimetaja ei ole null, siis tulemus ei sõltu taastumisavaldisest. Neid ei tohiks väärtustada ja nendes esinevad vead ei tohiks väärtustamist segada, näiteks viga/0 recover 1 tulemuseks on 1.

Põhiosa: SafdiAst

Failis Safdi.g4 tuleb implementeerida grammatika ja klassis SafdiAst tuleb implementeerida meetod parseTreeToAst, mis teisendab parsepuu AST-iks. Süntaksile kehtivad järgmised nõuded:

1. Arvuliteraalid koosnevad numbritest. Esimene number tohib olla 0 ainult siis, kui see on arvu ainuke number.
2. Muutuja koosneb vähemalt ühest ladina tähest (suured ja väiksed).
3. Aritmeetilised operaatorid on unaarne miinus (-), liitmine (+), korrutamine (*) ja jagamine (/). Nende puhul kehtivad aritmeetiliste tehete standardsed prioriteedid ja assotsiatiivsused.
4. Jagamisele (ja ainult jagamisele) võib järgneda võtmesõna recover ja taastumisavaldis. Oluline on taastumisavaldise korral ka säilitada operaatorite prioriteedid ja assotsiatiivsused (vt. näited allpool ja meie testides).
5. Avaldistes võib kasutada sulge, mis on kõige kõrgema prioriteediga.
6. Tühisümboleid (tühikud, tabulaatorid, reavahetused) tuleb ignoreerida.

Siin on taastumisavaldisega prioriteetide ja assotsiatiivsuste kohta paar näidet, kus on paremal nendega samaväärne (s.t. sama süntakspuuga) avaldis

x / y / z recover 0		(x / y) / z recover 0
x / y recover 0 / z		(x / y recover 0) / z

See tähendab ka seda, et x/y*z järel ei tohi olla taastumisavaldis, aga x/(x*z) järel võib!

NB! ANTLRi vasakrekursiooni elimineerimise maagia nõuab, et binaarne operatsioon algaks ja lõpeks rekursiivsete kutsetega (expr … expr). Taastumisavaldisega jagamine otseselt sellisel kujul ei ole. Meil õnnestus see lõpuni lahendada ainult kihilise avaldisgrammatikana.

Lõviosa: SafdiCompiler

Klassis SafdiCompiler tuleb implementeerida meetod compile, mis kompileerib avaldise CMa programmiks. Kompileerimisele kehtivad järgmised nõuded:

1. Muutujate väärtused antakse stack’il etteantud järjekorras.
2. Programmi täitmise lõpuks peab stack’i pealmine element olema avaldise väärtus, mis on sama nagu SafdiEvaluator-iga väärtustades.
3. Programmi veatu täitmise lõpuks tohivad stack’il olla ainult etteantud muutujate algsed väärtused ja arvutatud avaldise väärtus.
4. Vea korral lõpetatakse programmi töö koheselt (HALT instruktsioon). Sel juhul peavad stack’ile alles jääma ka vahetulemused. Nulliga jagamine tuleb avastada enne lugeja väärtustamist, seega add(num(5), div(num(2), num(0))) korral lõpetab töö stack’iga, kuhu on lisatud arv 5 (aga mitte 2).

PS. Jagamise juures võib olla vajalik jagajat kaks korda väärtustada – see on okei.