Kompilatorkonstruktion, våren 2001

CTH: TDA 280 (4.0p)
GU: INN 300 (5p)

Välkommen

Välkommen till kursen i Kompilatorkonstruktion! Eller, eftersom årets upplaga av kursen är slut, tack för i år!

Tentaresultaten anslogs på traditionellt vis, på plan 1 i MC, under GU, IN30-36. På webben kan man se poängfördelningen. Granskning av rättningen skedde tisdag 27/3 kl 12.45 på Thomas Hallgrens rum (5322, MC), eller enligt överenskommelse.

Omtentan är planerad att gå på förmiddagen lördagen den 25 augusti.

11 deltagare svarade på kursenkäten. Se vad de tyckte om kursen i sammanställningen av kursenkätsvaren.

Denna sida visar all information på en gång. Informationen finns även uppdelad på ett antal flikar, om du hellre vill se den i mindre doser.

Lärare på kursen

Thomas Hallgren
Telefon 031-772 5422
Rum 5322, Matematiskt Centrum
Föreläsningar, övningar, kursadministration, handledning
Josef Svenningsson Handledning, labrättning

Kurslitteratur

Kursbok
Andrew S. Appel, Modern Compiler Implementation in ML, Cambridge University Press, ISBN 0-521-58274-1 (hardback). Boken finns att köpa på Cremona för 486(?) kronor (paperback).

(Boken existerar även i en Java-version och en C-version. Vill ni hellre ha den, får ni skaffa den själva, t.ex. på nätet via bol.com eller WHSmith.co.uk. Normal leveranstid på bol.com är 5 dagar, enligt deras webbsidor.)

(Det finns även en äldre, mindre omfattande och något billigare utgåva av boken. Den heter Modern Compiler Implementation in ML: Basic Techniques. )

Lab-PM
I kursen ingår en laboration, ett kompilatorkonstruktionsprojekt. Lab-PM delas ut under första föreläsningen och kan även hämtas från kursens webbsidor.

Webbsidor
All kursinformation kommer även att finnas åtkomlig via kursens webbsidor. Dessa uppdaters med aktuell information under kursens gång.

Adressen till kursens hemsida är: http://www.cs.chalmers.se/Cs/Grundutb/Kurser/komp/

Läsanvisningar och gamla tentor

Extra läsning för intresserade

Simon Thompson: Regular Expressions and Automata using Haskell (2000) (29 sidor).
Går igenom reguljäruttryck, konvertering av reguljäruttryck till ickedeterministiska automater (NFA), konvertering av NFA till deterministiska automater (DFA), minimering av DFA. Med källkod i Haskell.
Hopcroft, Ullman, Motwani: Introduction to automata theory, languages and computation, ISBN 0-201-44124-1 (2001).
Allt om språk och grammatiker. Handlar även om beräkningsbarhet.
Urban Boquist: Code Optimisation Techniques for Lazy Functional Languages (1999)
Denna avhandling tar ett helhetsgrepp på kompilering av lata funktionella språk. Genom att kombinera ett antal tekniker, såsom en mellankodsform (kallad GRIN) väl lämpad för optimering, och global (interprocedurell) kontrollflödesanalys och registerallokering, så får man program som går 1.5-40 gånger snabbare än om de kompileras med andra kompilatorer (GHC och HBC) för lata funktionella språk.

Planerat föreläsnings- och övningsschema

Föreläsningarna är på onsdagar 8-10 i MD9 och torsdagar 13-15 i MD9. Övningarna är på fredagar 8-10 i MD9. (Se även Schema D3 lp3 (Valfria).)

OBS! Länkar inom parentes leder till information från förra året.
Länkarna uppdateras under kursens gång.
LvDagInnehållLänkar
.fm=FrameMaker 5.5
.ps=PostScript
.pdf=PDF (Acrobat)
.hs=Haskell
1 ons 17 jan Introduktion OH.fm OH.ps OH.pdf
tor 18 jan Språk & Grammatik OH.fm OH.ps OH.pdf
fre 19 jan Övning uppgifter.ps
lösningar.ps
2 ons 24 janLexikalanalys OH.ps
tor 25 jan Parsning, del 1 OH.ps
fre 26 janÖvning uppgifter.ps,
lösningar.ps
3 ons 31 jan Parsning, del 2, abstrakt syntax OH.ps
tor 1 feb Symboltabeller, semantisk analys, typkontroll OH.ps
Källkod till exempel: scopecheck.hs
fre 2 febÖvning uppgifter.ps,
lösningar.ps
4 ons 7 feb Inställd pga. CHARM-dag
tor 8 feb Körningsorganisation, kodgenerering för stackmaskin OH.fm OH.ps OH.pdf
fre 9 febÖvning, typkontroll uppgifter.ps,
lösningar.ps.
Nya lösningar till uppg 2 & 3:
Typer2.hs, Typer3.hs
5 ons 14 feb Kodgenerering för 3-operandsmaskin. Kodanalys. OH.fm OH.ps OH.pdf
tor 15 feb Kodanalys (forts). Registerallokering. Liten CPU beskrivning OH.fm OH.ps OH.pdf
fre 16 feb Övning, körningsorganisation se fre 9 feb.
6 ons 21 feb Optimering, del 1 OH.fm OH.ps OH.pdf
tor 22 feb Optimering, del 2 OH.fm OH.ps OH.pdf
OH2.fm OH2.ps OH2.pdf
Duff's Device
fre 23 febÖvning uppgifter.ps,
lösningar.ps
7 ons 28 feb Static Single Assignment (SSA),
Funktionella och Objektorienterade språk
SSA: OH.fm OH.ps OH.pdf
Fun&Obj: OH.fm OH.ps OH.pdf
tor 1 mars Funktionella och Objektorienterade språk (forts) se ovan
fre 2 marsÖvning. Gamla tentor?

Tentamensdatum

Kompilatorprojektet

Projektet går ut på att konstruera en kompilator för det lilla språket Javalette.

Viktiga datum

Labschema

Följande labtider är bokade i labsal K i läsvecka 2-7. Bokningsschema finns på en anslagstavla i närheten av labsalen.
MåndagarTisdagarOnsdagarTorsdagarFredagar
- - 15-17 15-17 13-15

Handledning

Handledarna är tillgängliga för att svara på frågor under de schemalagda labbtiderna, men vi är kanske inte i labbsalen hela tiden. Skicka mail till Josef eller Thomas, så kommer vi ner!

Bra-att-ha-filer

I ~komp/files

Alex.hs (för Haskell 1.4) eller Alex98.hs (för Haskell 98).
Fil som man skall ha med i program som använder alex.
MachineS.hs
Datatyp för stackinstruktioner. Innehåller funktionen showStackIns :: [InsS] -> String
Machine3.hs
Datatyp för treoperandinstruktioner
Innehåller funktionen show3opIns :: [InsS] -> String
stackmachine.tar.gz och 3op2sparc.tar.gz
Källkod (i Haskell 98) till programmen stackmachine och 3op2sparc för dig som vill provköra hemma. (Den senare kräver förstås att man har en SPARC.)
example.sm och example.3m
Exempel på hur stackmaskinkoden respektive 3-operandskoden ska se ut. Använder man de ovan nämnda funktionerna showStackIns och show3opIns får koden automatiskt rätt utseende. (Lab-PM:et är lite bristfälligt i vissa detaljer om man vill göra sina egna show-funktioner.)

I ~komp/bin

stackmachine
Virtuell maskin för att köra stackmaskinkod. Använd -help för att få reda på hur den används.
3op2sparc
Översättare från 3-operandskod till SPARC-assembler. Använd -help för att få reda på hur den används.
3opln
Tar en SPARC-assemblerfil eller objektfil och länkar ihop den med javalettes runtime-system till en körbar fil.
testlab1
Testkör automatiskt en kompilator (om inget annat anges på kommandoraden testas ~/lab1/lab1) på alla testexempel som finns i katalogen ~komp/examples och kontrollerar att kompilatorns utskrift innehåller ERROR för felaktiga program och OK för korrekta program.

I ~komp/examples/good och ~komp/examples/bad

Exempel på korrekta och felaktiga Javalette-program.

Verktyg för Haskell

Alex

I /usr/src/cs/pd/alex/alex finns källkod, dokumentation och exempel till lexikalanalysatorgeneratorn alex.

Happy

Dokumentation, källkod, mm, för syntaxanalysatorn Happy finns på hemsidan för Happy.

Haskell-interpretatorer och kompilatorer

Redovisning av laborationer med elrapport-systemet

1. Det gamla systemet

för labredovisning innebär att man trycker ut programlistningar på papper och lämnar in den (eventuellt med ytterligare dokumentation) i ett skåp i någon korridor mellan labsalarna. Efter ett tag tittar man på en lista på en vägg i närheten av skåpen och där får man information om man är godkänd eller har fått retur.

2. Det nya systemet

innebär att man redovisar laborationen genom att ge ett kommando
> rapportera 1
för att tala om att man är färdig med den första laboration, t ex. Efter ett tag får man ett elektroniskt brev som talar om att man är godkänd eller har fått retur.

Fördelen med detta är att vi sparar skog och att man inte behöver springa ner Matematiskt Centrum för att rapportera sin lab om man inte vill. Sedan behöver man inte springa ner och kolla på listan stup i kvarten, det räcker med att invänta svarsbrevet.

Om man har glömt vilka labbar man har blivit godkänd eller fått retur på kan man ge kommandot

> rapportlista

Om man vill se hur många inlämnade laborationer som väntar på att bli rättade kan använda kommandot

> ejrättade

3. Detaljer

Den dokumentation som ni skulle ha skrivit ut och lämnat in skall ni istället lägga i en redovisningskatalog i ert hemmabibliotek, så att den som skall rätta er lab kan titta på den. För att göra det lätt för labrättaren att hitta har vi följande konventioner: Finns det fler laborationer dokumenteras de efterhand på samma sätt i ~/lab2, ~/lab3 osv.

Ändra inte läsrättigheterna för ert hemmabibliotek eller redovisningskatalogerna, för då kan labrättarna inte komma åt er dokumentation.

Har man fått retur på en laboration tre gånger så är man underkänd på laborationen.

Leksaker

Här finns ett par hemmagjorda småprogram som har anknytning till kursen.
RegToy
Detta är ett program som konverterar reguljäruttryck till ändliga automater. Det kan köras både från webben och med kommandot
regtoy "re"
(där re är ett reguljäruttryck) från labbkontona.
LRToy
Detta är ett program som generarar LR-parsningstabeller från givna BNF-grammatiker. Det visar också resultatet av operationerna Nullable, First och Follow på grammatikens icke-terminaler.
FlowToy
Detta är ett program utför några av de dataflödesanalyser som beskrivs i kursboken: levande variabler, definitionsanalys, tillgängliga uttryck och dominatorer.

Länkar

Angående kursen

Haskell-prylar!

För andra språk

Kompilatorer, allmänt

Ändrad senast Saturday 2004-09-18 kl 03:19

Thomas Hallgren
Institutionen för Datavetenskap
Chalmers Tekniska Högskola
[ Valid HTML? | Check Links ]