DD2488 Kompilatorkonstruktion 9,0 hp
Denna kurs är under avveckling.
Sista planerade examination: HT 2024
Avvecklingsbeslut:
Kursen avvecklas vid utgången av HT 2024 enligt skolchefsbeslut: J-2023-1526.
Beslutsdatum: 2023-06-12
Kursen gavs sista gången HT 2022. Sista möjlighet till examination i kursen ges HT 2024.
Studenter som vill slutföra kursen efter att den getts för sista gången ska kontakta examinator.
En kompilator är ett stort och fascinerande program. Den som ska konstruera en kompilator måste behärska en mängd områden, komplicerade algoritmer och datastrukturer, syntaxanalys och detaljer i datorns arkitektur och instruktionsuppsättning.
Efter att ha förstått hur kompilatorn fungerar kan du inte bara konstruera en egen kompilator, utan du har också insett varför programspråk ser ut som dom gör och har lättare att förstå vilka möjligheter och begränsningar som finns vid programspråksutformning.
Den största uppgiften i kursen är att skriva en hel kompilator för ett litet men kraftfullt programspråk.
Innehåll och lärandemål
Kursinnehåll
Beskrivning av programspråk och andra formella språk med reguljära uttryck och grammatiker.
Metoder för att utföra lexikal- och syntaxanalys, och deras relationer till beräkningsmodeller såsom ändliga automater och stackautomater. Syntaxanalys med LL- och LR-analys. Verktyg i form av scanner- och parsergeneratorer.
Semantisk analys och översättning till intermediärkod. Instruktionsselektion och registerallokering.
Lärandemål
Studenten ska
- kunna redogöra för de olika stegen i kompileringsprocessen, från källkod till maskinkod,
- kunna tolka en given grammatik eller ett reguljärt uttryck för att avgöra vilka strängar som tillhör motsvarande formella språk,
- kunna skriva reguljära uttryck och grammatiker för olika formella språk, exempelvis programmeringsspråk,
- välja lämplig formell notation för att beskriva ett givet formellt språk,
- kunna förklara såväl LL- som LR-analys,
- kunna använda verktyg för att generera lexikal- och syntaxanalysatorer,
- känna till och kunna redogöra för en dators eller virtuell maskins arkitektur i de avseenden som är relevanta för kompileringsprocessen,
- kunna skriva program som utför olika steg i kompileringsprocessen.
Kurslitteratur och förberedelser
Särskild behörighet
För fristående kursstuderande krävs:
SF1671 Matematik, baskurs, med diskret matematik, DD1337 Programmering, DD1338 Algoritmer och Datastrukturer, DD1352 Algoritmer, Datastrukturer och Komplexitet, IS1200 Datorteknik eller motsvarande kurser.
Rekommenderade förkunskaper
Programmeringsfärdigheter i Java. IS1200 Datorteknik och DD1352 Algoritmer, datastrukturer och komplexitet eller motsvarande kurser.
Utrustning
Kurslitteratur
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
Examination
- PRO1 - Projekt, 5,0 hp, betygsskala: A, B, C, D, E, FX, F
- TEN1 - Tentamen, 4,0 hp, betygsskala: A, B, C, D, E, FX, F
Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.
Examinator får medge annan examinationsform vid omexamination av enstaka studenter.
Möjlighet till komplettering
Möjlighet till plussning
Examinator
Etiskt förhållningssätt
- Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
- Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
- Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.