Upp till kursens hemsida.
Information om gamla kursomgången 2D1375, Programspråksimplementation 1996/97
Enkät
Resultaten från kursenkäten finns här.
Redovisningstider
Torsdag den 5 december var den sista schemalagda redovisningstiden.
Den som vill redovisa restlabbar ska ta kontakt med
Viggo.
Jag har rapporterat in slutbetyg för alla som redovisat labb 6. Den som
vill höja betyget genom att göra labb 7 och eventuellt en utvidgning är
välkommen att göra det.
Fel i adacs.l rättat
Den bortkommenterade C-koden i
/info/primp96/labb1/adacs.l
som stoppar in reserverade ord i symboltabellen innehöll tidigare en bugg
som mycket enkelt kan avhjälpas. Byt ut första förekomsten av raden
#define __rw_op(a,b,c) a,
mot
#define __rw_op(a,b,c) a##zz,
Däremot ska den andra förekomsten av samma rad (den som förekommer i
definitionen av rw_code) inte bytas ut.
Sänkning av betygskraven
Efter att ha fått in ett antal svar på kursenkäten och efter att ha talat
med några som håller på med labb 7 så har jag kommit fram till att
labbkraven är för höga. Därför minskas nu kraven ungefär ett betygssteg
på följande sätt.
- För betyg 3 (och G på SU) krävs bara labb 1-6 och därmed en kompilator
som kan syntaxkolla Ada/CS-program korrekt och ge vissa felmeddelanden. Testa
kompilatorn på testprogrammen på katalogen
/info/primp96/adacs-examples, men läs noterna till labb 6 nedan.
- För betyg 4 krävs labb 1-7.
- För betyg 5 krävs labb 1-7 samt två utvidgningar, där labb 8 får
räknas som en utvidgning.
- För betyg VG på SU krävs labb 1-7 samt en utvidgning (som antingen
är labb 8 eller någon annan utvidgning).
- Den som vill får ersätta labb 7 och en utvidgning med kodgenerering
för någon registerbaserad maskin (registeroptimering behövs då).
- Kursens slutbetyg är medelbetyg på tenta och labb avrundat uppåt.
Detta gör till exempel att den som fått 5 på tentan bara behöver
4 på labben för att få 5 i slutbetyg.
Jag beklagar att jag blev tvungen att ändra kraven i ett så här sent skede
av kursen, men eftersom det är första gången kursen ges och eftersom Java
och JVM fortfarande är så unga så hoppas jag ni har förståelse för detta.
Toba
Toba är en översättare från JVM till C. Den finns
på Nada och blir tillgänglig med
module add toba
Om du vill kan du alltså med Tobas hjälp få din kompilator att generera
C-kod också.
Labblydelser
Labblydelser till labb 8 (överlagring) och kompilatorutvidgningarna finns
på expeditionen. Samtliga labbar finns samlade här.
Noter till labbarna
Labb 1
I labben kommer man att behöva definiera prioritetsordningen för
ickeslutsymboler, vilket inte går att göra direkt med %left etc,
utan man måste använda %prec.
Labb 2
För att kunna implementera hoplänkningen av alla symboler som beskrivs i
avsnitt 3 (Symboltabellen) så inför du lämpligen en pekare
up i id_entry_t som pekar på föregående symbol i samma
symboltabell.
I avsnitt 5 (Programmeringsgränssnitt) står det att du ska leta efter
symboler med givna egenskaper. Vilka egenskaper det kan vara beror på
vilka möjligheter till överlagring du kommer att införa i språket.
Om du vill kan du för tillfället inskränka dej till att kunna söka på
namn och lexikal nivå. När du senare gör utvidgningar kan du då behöva
ändra i symboltabellsgränssnittet.
Den som vill använda den hashfunktion som beskrivs på näst sista sidan i
anteckningarna till lektion 3 behöver en array scatter med 256 tal.
Ett förslag till definition av scatter finns på filen
/info/primp96/labb2/256tal.h
Labb 3
Första delen av labb 4 är en ren fortsättning på labb 3. Den kan du alltså
börja med så fort du gjort labb 3.
Labb 4
Regeln TypeName : IdDotEtc ; i adacs.y kan tyckas egendomlig
eftersom typnamn som Integer.Float.Boolean inte borde tillåtas.
Enda tillfället då en (och endast en) punkt kan ingå i ett typnamn är när
den refererar till en typ som finns deklarerad i en annan modul (package).
Regeln borde därför logiskt sett istället vara
TypeName : Id | Id Dot Id ;
men detta ger upphov till en konflikt i grammatiken, något som beskrivs i
den inledande långa kommentaren i början av adacs.y.
Detta betyder att du bör göra en semantisk koll på att TypeName
bara är ett enkelt typnamn och ge ett felmeddelande om det inte är det.
Du behöver inte göra konstantuttrycksoptimering för alla typer av operander.
Det räcker till exempel om du optimerar heltals- och flyttalsoperationer.
Typen Boolean implementeras i Ada/CS som en uppräkningstyp. Eftersom
din kompilator inte behöver klara uppräkningstyper så behöver den heller inte
klara av att man deklarerar något av typen Boolean. Booleska värden
måste dock klaras av (annars kan man inte göra jämförelser).
Labb 5
Inga noter ännu.
Labb 6
Konstruktionen Id(NonMtExpList)(NonMtExpList) är inte felaktig
i alla sammanhang eftersom (Expression) kan utgöra ett arrayindex.
Om funktionen f tar två parametrar och returnerar en array kan man
alltså skriva f(1,2)(3) för att ange elementet med index 3 i
den returnerade arrayen.
På katalogen /info/primp96/adacs-examples finns diverse
Ada/CS-programexempel som du kan använda för att testa din
kompilator. Vissa av exemplen innehåller fel eller använder
delar av språket som din kompilator kanske inte har
implementerat (till exempel inre block, Boolean).
Filen README beskriver några av testfilerna.
Filen test2.adacs är mycket bra för att testa felhanteringen.
I många av filerna används konstruktionen Write(Next) som
enligt kursbokens avsnitt A.21 ska göra en radframmatning.
Labb 7
Labblydelsen finns att hämta på expeditionen
Avsnittet Compiling for the JVM från boken
The Java Virtual Machine Specification är bra att läsa.
Det delas ut på lektionen den 29 oktober och finns sedan på expeditionen.
En ordrikare beskrivning av klassfilsformatet (kapitel 4 från samma bok)
finns här.
Konstantpoolsgenereringshjälprutinerna
/info/primp96/labb7/jvm.c innehöll
en allvarlig bugg som nu rättats. Felet var att EnterIntoConstantPool
returnerade byteindex och inte konstantpoolindex.
JVM-interpretatorn java är uppenbarligen mycket känslig och
dessutom inte helt buggfri.
-
En klassfil måste heta
namn
.class där namn inte innehåller
någon punkt. Namnet ska vara samma som namnet på den klass som definieras.
Interpreteringskommandot blir sedan
java namn
alltså utan .class på slutet.
Om man försöker stoppa in en felaktig klassfil
får man felmeddelandet Can't find class xxx.
-
Använd en disassemblator för att avkoda en klassfil med buggar. Det
verkar som
/info/primp96/labb7/guava/bin/guavad namn.class
är att föredra framför
javap -p -c namn
-
Det kan också vara en god idé att testa att köra
toba på sina
klassfiler (se ovan), för den kan hitta ytterligare fel.
-
Det finns några krav på hur huvudprogrammets klassfil ska se ut:
-
Superklassen ska vara
java.lang.Object vilket i klassfilen skrivs
som java/lang/Object. Klassens åtkomstflaggor bör vara
ACC_PUBLIC och ACC_FINAL.
-
Koden för huvudprogrammet ska läggas i en metod med namnet
main,
returtypen void och parametern
java.lang.String []. Signaturen för metoden blir
därför ([Ljava/lang/String;)V.
-
Åtkomstflaggorna för
main ska vara ACC_STATIC och ACC_PUBLIC.
- max_locals och max_stack som ska anges i varje
metod bör inte ha onödigt stora värden, för då är det risk att
interpretatorn kraschar. Ett exempel på ett onödigt stort värde är 4711.
- Titta gärna noga igenom den kommenterade klassfilen som finns med i
anteckningarna till lektion 9 så kan du se hur den klassfil som kompilatorn
genererar bör se ut.
Det finns
dokumentation
av JVM-interpretatorn
java,
Javakompilatorn
javac,
och JVM-disassemblatorn
javap.
Det finns också diverse Javadokumentation på Nada.
Kompilatorn behöver inte klara av följande saker
- variabler deklarerade i inre block
- konstantdeklarationer
- variabelinitieringar (direkt i deklarationen)
- Heltalsdivision för negativa tal enligt AdaCS-specifikationen
(avsnitt A.11). JVMs vanliga variant går bra.
- Exponentiering, MOD och dom fördefinierade funktionerna i avsnitt A.25.
För att utföra in- och utmatning i JVM-kod behövs anrop till Javas
biblioteksrutiner. Hur man gör detta har Joachim beskrivit
här.
Ytterligare ett fel i jvm.c rättat
Konstantpoolsindexen uppdaterades inte två steg för CONSTANT_Long
och CONSTANT_Double (se avsnitt 2.3.5 i JVM Specification). Det
är nu rättat i /info/primp96/labb7/jvm.c
Dessutom har en oklarhet i
/info/primp96/labb7/opcodes.h
retts ut. Det är därför en god idé att hämta dom nya versionerna av
dessa två filer från kursbiblioteket.
Fel i specifikationen av JVM-instruktionen WIDE
Beskrivningen av WIDE i The Java Virtual Machine Specification
är felaktig. Den instruktion som WIDE opererar på ska stoppas in mellan
operationskoden för WIDE (196) och operanden (indexbyte2).
| WIDE |
| <opcode> |
| indexbyte1 |
| indexbyte2 |
För IINC-instruktionen är syntaxen lite annorlunda:
| WIDE |
| IINC |
| indexbyte1 |
| indexbyte2 |
| constbyte1 |
| constbyte2 |
Exempel: om man vill ladda in heltalsvariabeln på plats 300 skriver man
(eftersom 1*256+44=300):
Observera dock att Guavad tolkar koden enligt den gamla specifikationen,
och alltså gör fel för WIDE-instruktioner.
Tentor
Fiktiv tenta 1, 1996
Fiktiv tenta 2, 1996-10-11
Ordinarie tenta 1996-10-24
Viktiga nyheter kommer också att annonseras i kursens
nätnyttsgrupp.
Lärare
Kursledare och föreläsare är Rand Waltzman,
rand@nada.kth.se.
Mottagningstid är tisdagar klockan 14.00-15.15, telefon 08-790 62 92.
Ansvarig för labbarna är Joachim Hollman,
joachim@nada.kth.se.
Kurslitteratur
Kurslitteraturen ska läsas på egen hand parallellt med kursen. Lektioner
och laborationer täcker endast en del av kursmaterialet.
Det finns en läsanvisning inför tentan med
referenser till andra böcker om kompilatorkonstruktion.
Kursbok
Charles N. Fischer, Richard J. LeBlanc: Crafting a compiler with C,
Benjamin Cummings, 1991, ISBN 0-8053-2166-7. Boken kan köpas för 300 kr på
kårens bokhandel.
Kursbunt
- Kursprogram (i stort sett denna text).
- Laborationer (vissa labbar delas ut under kursens gång).
- Lektionsanteckningar (delas ut under kursens gång).
- Specifikation av Javas virtuella maskin.
- En exempeltenta.
Kursbunten kan köpas på första lektionen och därefter på Nadas
elevexpedition
för 20 kr.
Papper som delas ut under kursens gång finns också på expeditionen.
Schema
Kursen består av 14 lektioner och 12 terminalövningar
Schema för vecka 36-41, 1996
| Tid | Måndag | Tisdag | Onsdag | Torsdag | Fredag |
| 8 | | | | Lektion
D41 | |
| 9 | | | | | |
| 10 | | Lektion
K2 | | Terminalövning
Konsthallen | |
| 11 | | | | | |
| 12 | | | | | |
| 13 | | | | | |
| 14 | | | | | |
| 15 | | | | | |
| 16 | | | | |
| 17 | | | | | |
Schema för vecka 44-45, 1996
| Tid | Måndag | Tisdag | Onsdag | Torsdag | Fredag |
| 8 | | Lektion
D41 | | | |
| 9 | | | | | |
| 10 | | | | Terminalövning
Konsthallen | |
| 11 | | | | | |
| 12 | | | | | |
| 13 | | | | | |
| 14 | | | | | |
| 15 | | | | | |
| 16 | | | | |
| 17 | | | | | |
Schema för vecka 46-49, 1996
| Tid | Måndag | Tisdag | Onsdag | Torsdag | Fredag |
| 8 | | | | | |
| 9 | | | | | |
| 10 | | | | Terminalövning
Konsthallen | |
| 11 | | | | | |
| 12 | | | | | |
| 13 | | | | | |
| 14 | | | | | |
| 15 | | | | | |
| 16 | | | | |
| 17 | | | | | |
Detaljschema
Följande tabell visar vad som preliminärt kommer att behandlas
under lektionerna och terminalövningarna.
- vecka 36
- L1 hur en kompilator fungerar, olika typer av kompilatorer (kapitel 1)
L2 repetition av syntaxanalys, en enkel kompilator (kapitel 2-7)
TÖ1 labb 1: anpassning av ADA/CS-grammatiken till Yacc/Bison
- vecka 37
- L3 minneshantering vid kompilering och körning (kapitel 8-9)
L4 deklarationer (kapitel 10)
TÖ2 labb 2: implementation av en symboltabellsmodul i C
- vecka 38
- L5 uttryck, datastrukturer och styrstrukturer (kapitel 11-12.5)
L6 särfall, procedurer och funktioner (kapitel 12.6-13)
TÖ3 labb 3: deklarationer
- vecka 39
- L7 exempel på funktioner, attributgrammatik, intermediär representation
(kapitel 14)
L8 kodgenerering (kapitel 15)
TÖ4 labb 4: uttrycksträd
- vecka 40
- L9 Javas virtuella maskin
L10 optimering (kapitel 16)
TÖ5 labb 5: intermediär kod för styrstrukturer
- vecka 41
- L11 mer om optimering, länkning, runtimebibliotek, avlusning
L12 repetition, projektkompilatorn
TÖ6 labb 6: intermediär kod för funktioner
- vecka 43
- tenta
- vecka 44
- L13 automatisk skräpsamling
TÖ7 labb 7: kodgenerering
- vecka 45
- L14 kompilatorer för objektorienterade språk
TÖ8 arbete med labb 7
- vecka 46
- TÖ9 arbete med labb 7 och eventuell utvidgning
- vecka 47
- TÖ10 arbete med labb 7 och eventuell utvidgning
- vecka 48
- TÖ11 redovisning
- vecka 49
- TÖ12 redovisning
Kursregistrering
Alla som vill gå kursen måste registrera sej på den. Detta görs med
kommandot
res checkin primp97
på någon av Nadas unixdatorer. Svara 0 (eller vad som helst) på
frågan om övningsgrupp.
Registrera dej så snart som möjligt efter att kursen börjat!
Du bör också ge kommandot
course join primp97
Detta kommando gör tre saker:
- Du får se eventuella nya meddelanden från kursledaren varje gång du
loggar in.
- Du får kursens användarmiljö, dvs alla initieringar
som kursledaren tycker att kursdeltagarna bör ha görs vid varje inloggning.
- Du får en speciell kurshemsida som startsida i Netscape.
När du är klar med kursen ger du kommandot
course leave primp97
för att återställa allt.
Examination
Kursen består av en tenta (2 poäng) och en labbdel (2 poäng).
Laborationer
Labbkursen består av sju obligatoriska labbar och ett antal valfria labbar för
den som vill ha överbetyg på labbkursen. Alla labbarna hänger ihop och
slutresultatet efter den sjunde labben är en färdig kompilator (för
större delen av språket ADA/CS som definieras i appendix A i kursboken)
som genererar kod för Javas virtuella maskin.
Den som vill ha betyg 4 på labbkursen ska förutom labb 1-7 göra labb 8
(överlagring).
Den som vill ha betyg 5 på labbkursen ska förutom labb 1-8 göra två
utvidgningar av kompilatorn.
Den på SU som vill ha betyg VG på labbkursen ska förutom labb 1-8 göra en
utvidgning av kompilatorn. Förslag till utvidgningar är:
- implementering av utelämnade konstruktioner i språket
(resterande slingor, case-sats, subtyper, poster etc)
- särfall
- moduler
- optimering
Du får gärna föreslå andra utvidgningar. Alla utvidgningar måste
godkännas av någon av lärarna på kursen.
Labbarna ska göras i grupper om högst fyra personer. Eftersom labbarna
bygger på varandra måste dom redovisas i ordning.
Om du inte fullgör hela labbkursen inom ett år från kursens slut har
kursledaren rätt att kräva att du gör samtliga labbar i den nya
kursomgången.
Bonuspoäng
Vi tillämpar ett bonussystem för att uppmuntra eleverna att ligga i fas med
undervisningen. För varje obligatorisk labb som redovisas före ordinarietentan
erhålls en bonuspoäng. Summan av dessa poäng (alltså maximalt 7 poäng)
adderas till den på tentan uppnådda poängsumman.
Detta gäller ett kalenderår räknat från kursstart.
Bonuspoäng kan endast fås det året som labbresultatet rapporteras.
När du är inloggad kan du se vilka labbar du är godkänd på genom att ge
kommandot
res show primp97
Hederskodex
Grundregeln är att det jobb du gör i kursen (labbar, inlämningsuppgifter,
tentor m.m.) ska du göra själv.
I denna kurs tycker vi dock att det är rimligt att labbgrupperna får
diskutera olika tänkbara lösningar med varandra. Kopiering av programkod är
förstås inte tillåtet.
Tentamen
Tid och plats för ordinarietentan är torsdag den 24 oktober klockan 8.00-13.00
i sal F42-F43. Första omtentatillfälle är fredag den 10 januari klockan
8.00-13.00 i sal F11.
Inga hjälpmedel är tillåtna på tentan. Skrivtiden är fem timmar.
För godkänt krävs minst 25 poäng (inklusive maximala 7 poäng
labbonus) av 50 poäng.
Tentaresultatet anslås högst tre veckor efter tentan på institutionens
anslagstavla på plan 3 (rakt under elevexpeditionen).
Klagomål på rättning av tentan lämnas in skriftligen till kursledaren
inom tre veckor från det att tentaresultatet anslagits.
Anmälan till tentan
Du behöver inte anmäla dej till tentan.
(Tentaanmälan var tidigare obligatoriskt för D- och E-teknologer
men Nada använder sej inte av detta anmälningssystem.)
Slutbetyg
På både tentan och labbkursen ges betyg (3, 4, 5 på KTH och G, VG på SU).
Slutbetyget är medelvärdet av dessa två betyg, där avrundning görs så att
betyget på labbkursen väger tyngst.
Kurskatalog
Kursen har en katalog på Unixdatorerna:
/info/primp97.
På denna katalog finns textfiler, programskelett, program och liknande
som har med kursen att göra.
Köra hemma
Om du har en dator och ett modem hemma kan du
koppla upp dej med modem mot Nadas datorer hemifrån.
Information om hur du gör finns
här.
Synpunkter på kursen
Eftersom denna kurs kommer att ges för många elever under flera års
tid är vi tacksamma för synpunkter på kursen. En datorstödd
kursutvärdering kommer att göras.
Synpunkter kan också lämnas direkt till Viggo.
Diverse länkar
Upp till kursens hemsida.
Sidansvarig: <rand@nada.kth.se>
Senast ändrad 2 september 1997
Tekniskt stöd: <webmaster@nada.kth.se>