Kompilatorkonstruktion, våren 2001

CTH: TDA 280 (4.0p)

GU: INN 300 (5p)

Välkommen	Lärare	Kurslitteratur	Veckoschema	Kompilatorprojekt	Elrapport	Leksaker	Länkar
Preliminära läsanvisningar Allmänt För att få en uppfattning om vad som är viktigt i kursen är det lämpligt att titta på OH-bilderna från föreläsningarna och övningsuppgifterna från övningarna. Det finns länkar till dessa i veckoschemat. Tänk även på att det som presenterats på föreläsningar ingår i kursen även om det inte har ett motsvarande kapitel i boken! Kapitel i boken Detta avser kursboken Modern Compiler Implementation in ML, 1 Introduction Ger överblick och lägger grunden för resten av boken. Läs igenom. 2 Lexical Analysis Avsnitt: Lexical tokens. Regular expressions. Finite automata. Nondeterministic Finite Automata. Ska känna till reguljäruttryck, hur man skapar en ickedeterministik ändlig automat (NFA) och hur man gör om den till en deterministisk automat (DFA) mha delmängsmetoden (som vi använt på föreläsningar och övningar). Ska känna till hur man använder en lexikalanalysatorgenerator (t ex Alex). 3 Parsing Avsnitt: Context-free grammars. Predictive Parsing. LR Parsing. Using parser generators. Ska veta vad som menas med vänster(höger)rekursion, vänsterfaktorisering, LL(k), LR(k), SLR, LALR. Ska veta hur man genererar punktproduktionsmängder och LR-parsningstabeller Ska känna till hur man använder en parsergenerator (t ex Happy). Hoppa över avsnitten om felhantering (error recovery). 4 Abstract Syntax Avsnitt: Semantic actions. Abstract parse trees, ej "abstract syntax for TIGER" Ska veta hur man bygger abstrakta syntaxträd med en parsergenerator. 5 Type Checking Avsnitt: Symbol tables. Type-checking expressions. Type-checking declarations. Ej de delar som bara rör Tiger-kompilatorn. Dessutom TILLKOMMER det jag sagt om typsystem på föreläsning, se OH-bilderna för detta. 6 Activation Records VIKTIG! Skall ha ett gott grepp om vad en aktiveringspost är, varför den finns, vad den innehåller. 7 Translation to Intermediate Code Vi har inte använt metoden med att gå via en trädrepresentation av mellankoden, utan går direkt till stack eller 3-adresskod. Skumma kapitlet. Koncentrera er på att förstå och formulera kompilerings- schemor istället. 8 Basic Blocks and Traces Basic block är VIKTIGT! 9 Instruction Selection Läs igenom. Är rätt trivialt för moderna RISC-maskiner. 10 Liveness Analysis VIKTIG! Skall kunna, samt även veta vad resultatet kan användas till. 11 Register Allocation VIKTIG! Skall kunna graffärgningsalgoritmen. 12 Putting It All Together Skippa 13 Garbage collection Känna till begrepp, och ha en översikt. 14 Object-Oriented Languages Känna till begrepp, och ha en översikt. 15 Functional Programming Languages Känna till begrepp, och ha en översikt. 17 Dataflow Analysis VIKTIG! 18 Loop Optimizations VIKTIG! Behöver inte kunna alla algoritmer i deltalj, men känna till vad som finns och förklara vad de gör. 19 SSA Veta vad SSA är, varför det är bra. Förstå phi-noder, vad de gör och varför de behövs. 20 Pipelining and Scheduling Kommer troligtvis utlämnas ur kursen. Men hinner jag med det så ... 21 Memory Hierarchy Känna till hur minnet är organiserat (cache, primärminne disk). I övrigt mest översiktligt.

Välkommen

Preliminära läsanvisningar

Allmänt

För att få en uppfattning om vad som är viktigt i kursen är det lämpligt att titta på OH-bilderna från föreläsningarna och övningsuppgifterna från övningarna. Det finns länkar till dessa i veckoschemat.

Tänk även på att det som presenterats på föreläsningar ingår i kursen även om det inte har ett motsvarande kapitel i boken!

Kapitel i boken

Detta avser kursboken Modern Compiler Implementation in ML,

1 Introduction

Ger överblick och lägger grunden för resten av boken. Läs igenom.

2 Lexical Analysis

Avsnitt: Lexical tokens. Regular expressions. Finite automata. Nondeterministic Finite Automata.

Ska känna till reguljäruttryck, hur man skapar en ickedeterministik ändlig automat (NFA) och hur man gör om den till en deterministisk automat (DFA) mha delmängsmetoden (som vi använt på föreläsningar och övningar). Ska känna till hur man använder en lexikalanalysatorgenerator (t ex Alex).

3 Parsing

Avsnitt: Context-free grammars. Predictive Parsing. LR Parsing. Using parser generators.

Ska veta vad som menas med vänster(höger)rekursion, vänsterfaktorisering, LL(k), LR(k), SLR, LALR. Ska veta hur man genererar punktproduktionsmängder och LR-parsningstabeller Ska känna till hur man använder en parsergenerator (t ex Happy).

Hoppa över avsnitten om felhantering (error recovery).

4 Abstract Syntax

Avsnitt: Semantic actions. Abstract parse trees, ej "abstract syntax for TIGER"

Ska veta hur man bygger abstrakta syntaxträd med en parsergenerator.

5 Type Checking

Avsnitt: Symbol tables. Type-checking expressions. Type-checking declarations.

Ej de delar som bara rör Tiger-kompilatorn. Dessutom TILLKOMMER det jag sagt om typsystem på föreläsning, se OH-bilderna för detta.

6 Activation Records

VIKTIG! Skall ha ett gott grepp om vad en aktiveringspost är, varför den finns, vad den innehåller.

7 Translation to Intermediate Code

Vi har inte använt metoden med att gå via en trädrepresentation av mellankoden, utan går direkt till stack eller 3-adresskod. Skumma kapitlet. Koncentrera er på att förstå och formulera kompilerings- schemor istället.

8 Basic Blocks and Traces

Basic block är VIKTIGT!

9 Instruction Selection

Läs igenom. Är rätt trivialt för moderna RISC-maskiner.

10 Liveness Analysis

VIKTIG! Skall kunna, samt även veta vad resultatet kan användas till.

11 Register Allocation

VIKTIG! Skall kunna graffärgningsalgoritmen.

12 Putting It All Together

Skippa

13 Garbage collection

Känna till begrepp, och ha en översikt.

14 Object-Oriented Languages

Känna till begrepp, och ha en översikt.

15 Functional Programming Languages

Känna till begrepp, och ha en översikt.

17 Dataflow Analysis

VIKTIG!

18 Loop Optimizations

VIKTIG! Behöver inte kunna alla algoritmer i deltalj, men känna till vad som finns och förklara vad de gör.

19 SSA

Veta vad SSA är, varför det är bra. Förstå phi-noder, vad de gör och varför de behövs.

20 Pipelining and Scheduling

Kommer troligtvis utlämnas ur kursen. Men hinner jag med det så ...

21 Memory Hierarchy

Känna till hur minnet är organiserat (cache, primärminne disk). I övrigt mest översiktligt.

Ändrad senast Monday 2001-02-19 kl 18:15

Thomas Hallgren
Institutionen för Datavetenskap
Chalmers Tekniska Högskola

[

]