DD2488 Kompilatorkonstruktion 9,0 hp

Compiler Construction

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.

  • Utbildningsnivå

    Avancerad nivå
  • Huvudområde

    Datalogi och datateknik
  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

HT19 komp19 för programstuderande

  • Perioder

    HT19 P1 (4,5 hp), P2 (4,5 hp)

  • Anmälningskod

    50292

  • Kursen startar

    2019-08-26

  • Kursen slutar

    2020-01-14

  • Undervisningsspråk

    Engelska

  • Studielokalisering

    KTH Campus

  • Undervisningstid

    Dagtid

  • Undervisningsform

    Normal

  • Antal platser

    Ingen begränsning

  • Planerade moduler

    P1: I1, D2, F2. P2: I1, D2, F2. mer info

  • Kursansvarig

    Philipp Haller <phaller@kth.se>

  • Målgrupp

    Studenter antagna på ett masterprogram.

  • Del av program

HT18 komp18 för programstuderande

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.

Kursens huvudsakliga innehå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.

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.

Litteratur

I en liknande kurs användes: A.W. Appel, Modern compiler implementation in Java, second edition.

In a similar course used: A.W. Appel, Modern compiler implementation in Java, second edition.

Examination

  • PRO1 - Projekt, 5,0, betygsskala: A, B, C, D, E, FX, F
  • TEN1 - Tentamen, 4,0, betygsskala: A, B, C, D, E, FX, F

I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex.

Ges av

EECS/Datavetenskap

Kontaktperson

Philipp Haller (phaller@kth.se)

Examinator

Philipp Haller <phaller@kth.se>

Ö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.

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.