ID3006 Kompilatorer och exekveringsmiljöer 7,5 hp

Compilers and Execution Environments

Kursen behandlar tekniker för implementation av programmeringsspråk med hjälp av kom­pilatorer, både for verkliga och virtuella exekveringsmiljöer.

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Kurstillfällen/kursomgångar

HT18 för programstuderande

  • Perioder

    HT18 P2 (7,5 hp)

  • Anmälningskod

    51468

  • Kursen startar

    2018-10-29

  • Kursen slutar

    2019-01-14

  • Undervisningsspråk

    Engelska

  • Studielokalisering

    Campus Kista

  • Undervisningstid

    Dagtid

  • Undervisningsform

    Normal

  • Antal platser

    Ingen begränsning

Information för forskarstuderande om när kursen ges

Varje år, period 2 tillsammas med ID2202.

Lärandemål

Det övergripande målet för kursen är att ge en förståelse för hur ett programmeringsspråk implementeras samt för de allmänna teorierna och forskningsframsteg som används och hur dessa kan appliceras. Kursen kommer att behandla tekniker för att läsa, förstå, översätta, förbättra, samt exekvera program.

Efter kursen skall studenten kunna:
 - förklara den övergripande strukturen av en kompilator.
 - beskriva reguljära uttryck och ändliga tillståndsmaskiner samt använda dessa för entydig lexikal analys; kombinera och använda tekniker för att konstruera deterministiska ändliga tillståndsmaskiner från reguljära uttryck.
 - beskriva kontext-fria grammatiker sam använda dem för att fånga vanliga konstrukter i programmeringsspråk; beskriva de grundläggande metoderna top-downsamt bottomupför syntaxanalys; konstruera syntaxanalyserare med hjälp av rekursiv medåkning, LL(1), LR(0), och SLR; identifiera huruvida grammatiker kan användas med en given metod för syntaxanalys.
 - lista och beskriva de uppgifter som utförs under den semantiska analys-fasen.
 - beskriva design-principerna för intermediärrepresentationer; förklara och använda metoder för att välja ut instruktioner; beskriva organsieringen i ett äctivation recordsamt identifiera effekten av olika designval för äctivation recordspå programmets exekvering.
 - definiera aktualitet ("liveness") för variabler samt beräkkna akualitetsinformation från kontrollflödesgrafen; precisera principen av konservativa uppskattningar för att analysera program; konstruera konfliktgrafer samt utföra fuillständing registerallokering för progam givet designen av äctivation records".
 - namge de viktigaste komponenterna i en exekveringsmiljö; beskriva enkla tekniker för att hantera dynamiskt minne samt skräpsamling (garbage collection"); identifiera den amorterade kostnaden för olika metoder av skräpsamling; lista vanliga tekniker för virtuella exekveringsmiljöer samt förklara deras egenskaper.
 - beskriva vanliga tekniker för programoptimering; identifiera loopar i program med hjälp av dominators; beskriva och använda tekniker för att optimera loopar och minnesåtkomster.
 - beskriva hur hårdvaruaktiekturers egenskaper influerar kompileringen av program; ge exempel på viktiga egenskaper.
 - beskriva och applicera nuvarande forskningstrender i komnpilatorer och exekveringsmiljöer i alla ovan nämnda områden.

Kursens huvudsakliga innehåll

Att läsa program: lexikalanalys och syntaxanalys. Ändliga tillståndsmaskiner, reguljära uttryck, LL- och LR-parsning.

Att förstå program: semantisk analys, typkontroll. Synlighetskontroll, deklarationer och uttryck.

Att översätta program: maskiner och instruktioner. Intermediärkod, instruktionsval, stackar och procedur-anrop.

Att exekvera program: virtuella exekveringsmiljöer och run-time system.Minneshantering, skräpsamling, att ladda och länka program, just-in-time kompilering. Hårdvaruarkitektursberoenden.

Att förbättra program: optimering. Maskinoberoende optimeringar (dataflödesanalys, styrkereduktion, ...). Maskinnära optimeringar (registerallokering, schemaläggning, förladdning, strömförbrukning, ...).

Forskningsöversikt: framträdande konferenser och tidskrifter.Nuvarande trender och kopplingar till andra forskningsområden.

Behörighet

Litteratur

Examination

  • EXA1 - Examination, 7,5, betygsskala: P, F

Godkänd skriftlig tentamina, godkända inlämningsuppgifter och godkänd tillämpning av nuvarande forskning (till exempel: användning i en forskningsartikel, forskningsreport, eller forksningsprojekt).

Krav för slutbetyg

Godkänd skriftlig tentamina, godkända inlämningsuppgifter och godkänd tillämpning av nuvarande forskning (till exempel: användning i en forskningsartikel, forskningsreport, eller forksningsprojekt).

Ges av

EECS/Programvaruteknik och datorsystem

Kontaktperson

Christian Schulte, cschulte@kth.se 087904264

Examinator

Christian Schulte <cschulte@kth.se>

Versionsinformation

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