Behörighetskrav

Matematik 10 p/15 hp inkl. Automatateori. Datavetenskap 20 p/30 hp inkl. en fortsättningskurs i programmering och Operativsystem.

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.

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
• 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).