DD2488 Kompilatorkonstruktion 9,0 hp
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.
Välj termin och kursomgång
Välj termin och kursomgång för att se aktuell information och mer om kursen, såsom kursplan, studieperiod och anmälningsinformation.
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.
Kursupplägg
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.
Ytterligare information
Kurswebb
Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.
Kurswebb DD2488Ges av
Huvudområde
Utbildningsnivå
Påbyggnad
Kontaktperson
Övrig information
Den här kursen får inte räknas med i examen om studenten har läst ID1215 eller ID2202.
Kursen ges i mån av lärarresurser.
I denna kurs tillämpas EECS hederskodex, se:
http://www.kth.se/eecs/utbildning/hederskodex