Automata, Languages and Compilers 2020/21 spring

Lihtne imperatiivne keel Imp

x = 5,
y = x + 1,
x = y + 1,

x

Imp keel on expr näidiskeele täiendatud variant, mis lisaks puhastele aritmeetilistele avaldistele võimaldab ka üht imperatiivsete programmeerimiskeelte konstruktsiooni: omistamist.

Keeles on järjest omistamislaused ja lõpuks on üks paljas avaldis, kus ei ole omistamist. Programmi tulemus ongi selle viimase avaldise väärtus, kui eelnevad read on järjest täidetud. Paremal on üks programm Imp keele (esialgses) süntaksis. Selle näidisprogrammi käivitamise tulemus on 7.

AST

Imp keele AST klassid paiknevad toylangs.imp.ast paketis. Expr keelest on üks-ühele (ümber nimetatuna) üle võetud järgmised avaldiste konstruktsioonid: ImpNum, ImpNeg, ImpAdd, ImpDiv.

Juurde on lisatud järgmised konstruktsioonid:

• ImpVar — avaldis, mis viitab muutujale;
• ImpAssign — tipp, mis tähistab muutujale antud avaldise väärtuse omistamist;
• ImpProg — tipp, mis tähistab terviklikku imp keele programmi, mis koosneb suvalisest arvust omistamistest ja täpselt ühest avaldisest (mis pole omistamine).

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

prog(
  var('x'),

  assign('x', num(5)), 
  assign('y', add(var('x'), num(1))), 
  assign('x', add(var('y'), num(1)))
)

Alusosa: ImpEvaluator

Imp keele väärtustaja tuleb implementeerida klassis ImpEvaluator. Expr keelest üle võetud avaldiskonstruktsioonide väärtustamine peab toimima samamoodi nagu expr keeles, st standardse aritmeetika järgi.

Lisatud konstruktsioonide väärtustamisele kehtivad järgmised nõuded:

1. Programmi väärtuseks on selle mitte-omistamisest avaldise väärtus.
2. Programmi omistamised tuleb teostada enne programmi avaldise väärtustamist, mis võib sisaldada viiteid omistatud muutujatele.
3. Programmi omistamised tuleb teostada selles järjekorras nagu nad listis on, kusjuures iga omistamise avaldis võib sisaldada viiteid eelnevalt omistatud muutujatele.
4. Esialgu pole defineeritud ühtegi muutujat. Defineerimata muutujate kasutamine peab viskama erindi.
5. Programmis on lubatud ühele muutujale omistada mitu korda, kusjuures muutuja väärtuseks on talle viimati omistatud avaldise väärtus.
6. Võib eeldada, et väärtustatav programm sisaldab ainult ühte ImpProg tippu, mis on kõige välimine, st ükski sisemine avaldis pole omakorda programm, millel on oma sisemised omistamised.

Lahendamise video: Imp alusosa.

Põhiosa: ImpAst

x = 5, y = 0,
y = x + - 1,
z = (-(y + x) / 2),
(x + 25) / -y

Imp keele grammatika tuleb implementeerida failis Imp.g4 ja parsepuust AST-i koostamine klassis ImpAst. Paremal on näide konkreetses süntaksis kirjutatud Imp programmist.

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. Muutujateks on üksikud ladina väike- ja suurtähed.
3. Operaatorid on järgmised: liitmine (binaarne +), jagamine (binaarne /) ja vastandarvu võtmine (unaarne -). Nende prioriteedid ja assotsiatiivsused on standardsed.
4. Avaldise ümber võivad olla sulud.
5. Omistamine koosneb muutujanimest, võrdusmärgist (=) ja avaldisest.
6. Programm koosneb omistamistest (mida võib olla ka null tükki) ja lõppavaldisest. Omistamised on omavahel ja lõppavaldisest eraldatud komadega (,).
7. Tühisümboleid (tühikud, tabulaatorid, reavahetused) tuleb ignoreerida.

Lahendamise video: Imp põhiosa.

Lõviosa: ImpCompiler

Imp keele CMa-sse kompilaator tuleb implementeerida klassis ImpCompiler. Kompileeritud programmi käivitamise tulemus peab olema sama nagu siis, kui seda ImpEvaluatoriga väärtustada, st kehtivad kõik ülaltoodud väärtustamisreeglid.

Kompileeritud programmidele kehtivad järgmised nõuded:

1. Programmi (st selle mitte-omistamisest avaldise väärtus) peab täitmise lõpuks olema stacki pealmine element.
2. Stacki kasutus peab olema mõistlik:
   1. Omistatud muutujate väärtused peavad paiknema stacki alguses omistamise järjekorras; st esimesena omistatud muutuja stacki aadressil 0, teisena omistatud muutuja stacki aadressil 1 jne.
   2. Samanimelisele muutujale uuesti omistamine 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 = 5,
y = x + 1,
x = y + 1,

x

Paremaloleva programmi kompileerimise ja saadud CMa programmi täitmise lõpuks peaks olema stack [7, 6, 7], kus esimesena on muutuja x väärtus, teisena muutuja y väärtus ja viimasena kogu programmi väärtus.

Lahendamise video: Imp lõviosa.