Kursprogram för 2D1375 Programspråksimplementation, hösten 2001

Mål

Kursens mål är att ge

- teorin bakom och principerna för konstruktion och implementation av kompilatorer och andra översättare,

- detaljförståelse för mekanismerna i programspråk och hur en kompilator kan realisera dem

för att studenterna ska

- kunna modifiera en existerande översättare,

- med hjälp av verktyg konstruera en kompilator från ett givet programspråk till maskinkod eller

ett annat programspråk.

Lärare

Kursledare och föreläsare är Leif Kusoffsky.

Jag kan nås med e-post lky@nada.kth.se eller på rum 1614, plan 6 på institutionen.

Mitt telefonnummer är 790 62 09 och jag har under kursens gång mottagning enligt överenskommelse.

Kurslitteratur och innehåll

Kursboken är

- Andrew W. Appel: Modern Compiler Implementation in Java,

Cambridge University Press, 1998, ISBN 0-521-58388-8

eller

- Andrew W. Appel: Modern Compiler Implementation in C,

Cambridge University Press, 1998, ISBN 0-521-58390-X.

eller

- Andrew W. Appel: Modern Compiler Implementation in ML,

Cambridge University Press, 1998, ISBN 0-521-58274-1.

Som synes finns det tre olika versioner av kursboken beroende på vilket språk man vill implementera kompilatorn i, Java, ML eller C. Det språk som kompilatorn kompilerar är samma i båda böckerna.

Ni får använda antingen Java- ML-eller C-boken, och ni får göra laborationerna i antingen Java, ML eller C. Kursledaren har alla tre böckerna på sitt arbetsrum, kom gärna förbi och titta i dem ifall ni har svårt att bestämma er för vilken av böckerna ni vill använda. Kursledaren har gjort laborationerna i Java, och av detta skäl och för att det troligen är lättare att klara kursen med Java rekommenderar jag att Java används.

Kursen behandlar 5<= kapitel <= 8 i boken och förutsätter kunskaper motsvarande 1<= kapitel <= 4. (Kursen i Artificiella språk och syntaxanalys ger dessa förkunskaper.)

Examination och betygssättning

Kursen ger fyra poäng och innehåller två olika moment, laborationer respektive muntlig tentamen, på två poäng vardera. Genom att göra vissa laborationer (se nedan) aspirerar ni på ett visst betyg. Om ni blir godkänd på den muntliga tentamen fastställs det betyget.

Laborationer

Appel går igenom ett antal kompilatormoduler i sin bok; kapitel 1 är en uppvärmning och kapitel 2-11 innehåller en modul vardera, och programmeringsuppgifterna i varje kapitel (under rubriken PROGRAM) utgör laborationsuppgiften i denna kurs. Programmeringsuppgifterna i kapitlen bygger alltså (fr o m kapitel 2) på vad som färdigställts i föregående kapitel.

Givet godkänd muntlig tentamen sätts betyg enligt följande för KTH-elever:

Avklarat kapitel 5 och 6 ger betyg 3.

Avklarat kapitel 5, 6 och 7 ger betyg 4.

Avklarat kapitel 5, 6, 7 och 8 ger betyg 5.

och enligt följande för SU-elever:

Avklarat kapitel 5 och 6 ger betyg G.

Avklarat kapitel 5, 6 och 7 ger betyg VG.

Det är tillåtet att arbeta i grupper om högst två personer. Båda personerna i gruppen får i sådant fall samma betyg.

För varje kapitel ska ni skriva en rapport som lämnas till kursledaren. De rapporten ska innehålla:

- En beskrivning av hur kursledaren ska göra för att kompilera och testköra programmet på 5-10 indata som visar att programmet fungerar som det ska. (Lämpligen läggs en kopia av källkoden i en katalog som kursledaren får skrivrättigheter i.)

- En övergripande redogörelse för hur ni har löst uppgiften. Om ni har gjort något annat designval än Appel, beskriv detta designval.

- Dessutom ska er källkod vara lättläst och välkommenterad.

De skrivna rapporterna måste lämnas in senast klockan 15:00 den 14 december 2001.

Eftersom kursen är en läskurs är inga terminalövningar schemalagda.Viss information finns också på

kursens hemsida . (http://www.nada.kth.se/kurser/kth/2D1375/).

Appel har en webbplats (http://www.cs.princeton.edu/~appel/modern/) med information rörande boken. Dessutom finns det filer med given kod nedkopierade till kurskatalogen. Den katalog som i läroboken betecknas med $TIGER är

/info/primp00/java/tiger respektive /info/primp00/c/tiger

beroende på vilken version av boken ni använder. Den givna koden är ca 2 500 rader och innehåller en del av de klasser som behövs, mest mer triviala klasser som t ex de klasser som specificerar datastrukturerna för gränsnittet mellan kompilatorklasserna Det man skall skriva själv blir ungefär lika mycket.

I underkataloger (tex /info/primp00/java/extras/chap4/Parse/ ) till katalogerna

/info/primp00/java/extras/

finns både mina lösningar (med 00 inamnet) och lösningar från förra året (med 99 i namnet) i Java till kapitlen före kapitel 5.

I under kataloger till katalogen

/info/primp00/c/extras

finns lösningar från förra året i C till kapitlen före kapitel 5.

Att själv göra även programmeringsuppgifterna i de första kapitlen rekommenderas dock varmt, eftersom man då lär sig Tiger-språket (det språk som skall översättas), den abstrakta syntaxen som är gränsittet mot uppgiften i kapitel 5 osv. Av de totala arbetet att lösa alla uppgifterna t o m kapitel 8 är arbetet med de inledande kapitelet en mindre del, kanske 10 %.

Det verkar finnas några fel i de Java-filer som Appel tillhandahåller på sin webbplats; diff-fil med rättelser (http://www.nada.kth.se/kurser/kth/2D1375/java-diffs.txt )

Vissa rättelser finns på kursens hemsida.

Om man gör laborationerna i Java behöver man köra »module add java» och sedan lägga till katalogen /info/primp00/java/classes till sin CLASSPATH om man inte kopierar filerna.

Detta har jag inte kontrollerat, kopierat från fjolårets kursprogram: Laborerar man i C måste man se till att använda rätt C-kompilator. En kompilator som fungerar får man med »module add workshop». Dessutom måste man lägga till /usr/ccs/bin till sin PATH för att få tillgång till lex och yacc. Allt detta görs automatiskt varje gång ni loggar in om ni kör »course join primp99».

Vill man laborera i C hemma borde det gå bra att använda gcc, flex och bison, men då måste man ändra lite i Make-filerna.

Muntlig tentamen

Den muntliga tentamen går ut på att kursledaren ställer frågor på de kapitel i boken som svarar mot de laborationer ni har gjort samt på era laborationslösningar. Förutom konkreta frågor om sina egna lösningar ska man alltså kunna svara även på sådant som rör given kod i de olika laborationerna, bakgrund och lösningsmetoder. Appel diskuterar normalt flera olika lösningsmetoder i varje kapitel. Endast en av dem används på laborationen, men ni ska naturligtvis kunna redogöra för hur alla metoderna fungerar. Vissa kapitel i boken har ett litet laborationsmoment; där är det naturligtvis större tyngd på de teoretiska bitarna.

Ni måste ha klarat av den muntliga tentamen senast klockan 17:00 den 25 januari 2001. Man kan inte gå upp på den muntliga tentamen förrän man har lämnat in laborationsrapporterna.

Rekommenderad studiemetod

Läs kapitel 1 i läroboken. Gör programmeringsuppgiften som svarar mot kapitel 1 i läroboken.

Läs kapitel 2 i läroboken. Gör, med hjälp av den färdiga koden i kurskatalogen, programmeringsuppgiften som svarar mot kapitel 2 i läroboken.

Läs kapitel 3 i läroboken. Gör, med hjälp av den färdiga koden i kurskatalogen, programmeringsuppgiften som svarar mot kapitel 3 i läroboken.

Läs kapitel 4 i läroboken. Gör, med hjälp av den färdiga koden i kurskatalogen, programmeringsuppgiften som svarar mot kapitel 4 i läroboken.

Läs kapitel 5 i läroboken. Gör programmeringsuppgiften som svarar mot kapitel 5 i läroboken. Kontrollera lösningen mo testfallen i $TIGER.

Läs kapitel 6 i läroboken. Gör programmeringsuppgiften som svarar mot kapitel 6 i läroboken. Kontrollera lösningen mot testfallen i $TIGER.

Läs kapitel 7 i läroboken. Gör programmeringsuppgiften som svarar mot kapitel 7 i läroboken. Kontrollera lösningen mot testfallen i $TIGER.

Läs kapitel 8 i läroboken. Gör programmeringsuppgiften som svarar mot kapitel 8 i läroboken. Kontrollera lösningen mot testfallen i $TIGER.

Fortsättningskurser

Det finns inga direkta fortsättningskurser till denna kurs, men de som är intresserade av att göra en färdig kompilator kan få tillgodoräkna sig detta som kursen

Avancerad individuell kurs i datalogi (http://www.nada.kth.se/kurser/kth/2D1465)

Kontakta kursledaren angående fler detaljer.