Automata, Languages and Compilers - Courses - Institute of Computer Science

10. kodutöö: AKTK kompilaator

Viimases kodutöös tuleb kirjutada kompilaator (klassis AktkCompiler), mis loob etteantud AKTK programmi põhjal Java .class faili, mille main meetodi käivitamine teostab programmis näidatud operatsioonid.

AKTK programmide parsimise ja abstraktse süntaksipuu koostamise osa on ette tehtud. Sinu teha jääb abstraktse süntaksipuu põhjal Java klassi koostamine (meetod createClass).

ASM

Baitkoodi loomiseks soovitame kasutada ASMi.

Java baitkoodi ja ASMiga tutvumiseks on väga hea materjal ASMi juhend:

Soovitav on selle esimesed 64lk vähemalt läbi lapata.
Lehekülgedel 135-138 on lakooniline ülevaade JVM baitkoodidest — selle soovitame kodutöö lahendamise ajaks ligi võtta.
(Huvi korral saab kõige detailsemat infot Java virtuaalmasina spetsifikatsioonist.)

ASMi API on siin: http://asm.ow2.io/javadoc/overview-summary.html. Tähtsamad klassid selle kodutöö seisukohast:

ClassWriter: http://asm.ow2.io/javadoc/org/objectweb/asm/ClassWriter.html
MethodVisitor: http://asm.ow2.io/javadoc/org/objectweb/asm/MethodVisitor.html
Opcodes: http://asm.ow2.io/javadoc/org/objectweb/asm/Opcodes.html

Failist AsmDemo leiab näite, kuidas ASM teegi abil luua JVM class fail ning sinna lisada main meetod, mis sisuliselt realiseerib System.out.println("hello"). Selle demo käivitamisel tekib projekti juurkausta Kala.class, mida saab käivitada näiteks käsurealt käsuga java Kala.

Class failide vaatamiseks on IntelliJ-s mitu võimalust:

Vaikimisi IntelliJ dekompileerib baitkoodi ja üritab seda uuesti Javaks tagasi teisendada, küll aga teatud puudustega.
(ASM Bytecode Viewer pluginanga saab teha paremkliki ja valida "ASM Bytecode Viewer", mis näitab baitkoodi selle instruktsioonide jadana ja eraldi tab-il ka selle loomiseks vajalike ASM käskudega. Kahjuks on see plugin aegunud ja ei toeta viimaste Java versioonide baitkoodi. Lisades build.gradle faili rea java.sourceCompatibility = JavaVersion.VERSION_13 on seda siiski võimalik kasutada isegi Java 16 kompilaatoriga, kuid samas projektis olevad Java 14+ võimalused siis enam ei kompileeru.)

Lisamärkused

Ettantud mall kasutab 9. kodutööst AktkBinding klassi. Kui sul pole selle lahendust, siis kasuta näidislahendust või eemalda selle kasutus kompilaatoris.
Selles kodutöös tuleb AKTK väärtustest toetada vaid täisarve. Võib eeldada, et kompilaatori testimisel ei sisalda etteantud programmid sõneliteraale.
If ja while lause tingimusteks loeme tõeseks nullist erinevaid täisarve ja vääraks täisarvu 0.
Kõik AKTK programmides kasutatavad funktsioonid on antud klassi AktkCompilerBuiltins staatiliste meetoditena. Võib eeldada, et AKTK programmis funktsioone ei defineerita.
Pane tähele, et AKTK abstraktne süntaksipuu ühtlustab tavapärased infiksoperaatsioonid ja harilikud funktsiooni väljakutsed ühe nimetaja alla (FunctionCall) — baitkoodi kompileerimisel tuleks neil vahet teha. Selle tarvis on klassi FunctionCall lisatud abimeetodid isComparisonOperator ja isArithmeticOperation — kui need meetodid tagastavad false, on tegemist hariliku funktsiooniväljakutsega.

Lahenduse testimine

Lahenduse testimiseks kompileerib testimissüsteem klassi AktkCompiler abil mingi AKTK programmi, käivitab saadud .class faili ja kontrollib kas programmi väljund vastab oodatud väljundile. Kompileeritud klassi käivitamise protsess käsurealt näeks välja umbes selline:

 > java yks_pluss_yks
 2

Selleks, et Java leiaks üles AktkCompilerBuiltins klassi, on kõige lihtsam jooksvasse kausta tekitada kaust week10 ning kopeerida sinna vastav klassifail. Loomulikult võib nende asukoha näidata ka java -cp parameetriga (nt -cp .;build/classes/java/main).

Näiteprogrammid

Mõned AKTK näiteprogrammid, mille korrektse kompileerimisega peaks AktkCompiler hakkama saama:

Peaaegu kõige lihtsam programm, mis midagi teeb:

print(1+1)

Interaktiivne programm:

/* Küsib standardsisendist täisarvu ja väljastab selle märgi.
   Kordab seda niikaua kuni sisestatakse 0 */

var x = readInt();

while x != 0 do {
    if x > 0 then print(1) else print(-1);
    x = readInt()
};
print(x)

Suurima ühisteguri arvutamine kahel moel:

a = 234;
b = 12;

/* Arvutan suurima ühisteguri "standardteegi" abil */
print(gcd(a,b));


/* Nüüd arvutan sama asja aktk vahenditega */
var c;
while b > 0 do {
	c = a % b;
	a = b;
	b = c
};

print(a)

Vihjed

Ettevaatust! Järgnevatele linkidele klikkimine võib oluliselt vähendada selle kodutöö lahendamisest saadavat naudingut!

Vihje 1. Siin on ette tehtud klassi peaosa ning meetodi koodi genereerimise algus.
Vihje 2. Siin on lisaks ära toodud üks võimalik AST läbimise struktuur.

Video juhuks, kui jääd alustamisega hätta: AktkCompiler-i algus.