Kursplan för Kompilatorteknik I

Compiler Design I

Det finns en senare version av kursplanen.

Kursplan

  • 5 högskolepoäng
  • Kurskod: 1DL321
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Datavetenskap G2F, Teknik G2F

    Förklaring av koder

    Koden visar kursens utbildningsnivå och fördjupning i förhållande till andra kurser inom huvudområdet och examensfordringarna för generella examina:

    Grundnivå

    • G1N: har endast gymnasiala förkunskapskrav
    • G1F: har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav
    • G1E: innehåller särskilt utformat examensarbete för högskoleexamen
    • G2F: har minst 60 hp kurs/er på grundnivå som förkunskapskrav
    • G2E: har minst 60 hp kurs/er på grundnivå som förkunskapskrav, innehåller examensarbete för kandidatexamen
    • GXX: kursens fördjupning kan inte klassificeras

    Avancerad nivå

    • A1N: har endast kurs/er på grundnivå som förkunskapskrav
    • A1F: har kurs/er på avancerad nivå som förkunskapskrav
    • A1E: innehåller examensarbete för magisterexamen
    • A2E: innehåller examensarbete för masterexamen
    • AXX: kursens fördjupning kan inte klassificeras

  • Betygsskala: Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
  • Inrättad: 2012-03-08
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 02, 2012
  • Behörighet: 60 hp varav minst 15 hp matematik inklusive Automatateori och 30 hp datavetenskap inklusive Operativsystem och fortsättningskurs i programmering eller Processorienterad programmering.
  • Ansvarig institution: Institutionen för informationsteknologi

Mål

För godkänt betyg ska studenten förstå hur enkla imperativa programspråk kan kompileras till maskinkod för RISC-liknande maskiner.

Efter godkänd kurs ska studenten kunna

  • strukturera en kompilator som en sekvens av distinkta översättningsteg
  • använda reguljära språk för att beskriva ett programspråks lexikaliska element
  • beskriva lexikalisk analys med en ändlig automat
  • använda kontextfria språk för att beskriva ett programspråks syntaktiska struktur
  • använda parsningsmetoderna top-down (recursive descent) och bottom-up (LR)
  • använda abstrakta syntaxträd för att representera resultatet av den syntaktiska analysen
  • bryta ner satser och uttryck till enklare konstruktioner, och översätta syntaxträd till mellankod
  • beskriva hur rekursiva proceduranrop kan implementeras med hjälp av stackar, aktiveringsposter och maskinregister
  • översätta ett programs förenklade mellankod till maskinspecifika instruktioner

Innehåll

Lexikalisk analys (scanning).
Syntaktisk analys (parsning).
Programrepresentation i Abstrakta Syntax-Träd (AST).
Symboltabeller och scoperegler för C-liknande språk.
Typcheckning för C-liknande språk.
Olika former av mellankod (IR).
Generering av mellankod.
Anropsstackar och aktiveringsposter.
Kodgenerering för RISC-liknande maskiner.
Basblock, kontrollflödesgrafer, liveness-analys, registerallokering.

Undervisning

Föreläsningar, laborationer.

Examination

Kursen examineras med skriftlig tentamen (4 hp) och uppgifter (1 hp).

Versioner av kursplanen

Litteratur

Litteraturlista

Gäller från: vecka 02, 2012

I bibliotekets söktjänst kan du se om en titel finns elektroniskt.

A.W. Appel: Modern compiler implementation in ML, Cambridge University Press, 1998.
eller
A.W. Appel: Modern compiler implementation in Java, Cambridge University Press, 1997.

Referenslitteratur

Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen: Modern Compiler Design, John Wiley&Sons, Ltd, 2000.
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools, Addison-Wesley, Reading, MA, 1986.