Behörighetskrav

Matematik 10 p/15 hp inkl. Automatateori. Datavetenskap 15 p/22,5 hp inkl. Programmeringsteknik MN2, Algoritmer och Datastrukturer DV1 eller motsvarande kunskaper. Algoritmer och Datastrukturer DV2 och Operativsystem rekommenderas.

Mål

För godkänt betyg ska studenten förstå hur enkla

imperativa programspråk motsvarande C kan kompileras

till maskinkod för RISC-liknande maskiner.

Specifikt ska studenterna 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
• implementera 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
• använda hashtabeller för att hantera information om variabelbindingar i språk med statiska och nästlade synlighetregler
• bryta ner satser och uttryck till enklare konstruktioner, och översätta syntaxträd till mellankod
• implementera rekursiva proceduranrop med hjälp av stackar, aktiveringsposter och maskinregister
• översätta ett programs förenklade mellankod till maskinspecifika instruktioner

Innehåll

Teori:

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

Projekt:

Studenterna utför ett projekt i vilket de implementerar en

kompilator från en liten delmängd av C till en RISC-maskin.

Projektet är uppdelat i etapper, vilka redovisas separat.

Undervisning

Föreläsningar, laborationer, projekt.

Examination

Kursen examineras med skriftlig tentamen (3 hp) och uppgifter inom projektet (4,5 hp).