Kompilatorkonstruktion, våren 2001

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

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

• Läsanvisningar.
• 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

Tentamensdatum

• Ordinarie tenta: torsdag 8 mars, eftermiddag
• Omtenta: lördag 25 augusti, förmiddag

Kompilatorprojektet

• Lab-PM för kompilatorprojektet (PostScript).

Viktiga datum

• Fredag 16/2: sista inlämningsdag för "etapp 1". Inlämning görs med kommandot rapportera 1.
• Fredag 2/3: sista inlämningsdag för hela labben. Inlämning görs med kommandot rapportera 2.
• Månddag 19/3: sista godkännandedag för hela labben.

Labschema

Handledning

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

Verktyg för Haskell

Alex

Happy

Haskell-interpretatorer och kompilatorer

• Hugs: kommandot hugs startar det interaktiva Hugs-systemet. Kommandot runhugs fil.hs kör funktionen main i fil.hs utan att starta det interaktiva systemet.
• Kompilatorn GHC: det bekvämaste är att kompilera med hmake. För att få en körbar fil ska man ge namnet på filen som innehåller funktionen main, utan avslutande .hs-suffix.
• Kompilatorn HBC: börjar bli lite gammal...

Redovisning av laborationer med elrapport-systemet

1. Det gamla systemet

2. Det nya systemet

> rapportera 1

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

• Dokumentationen till den första laborationen läggs i katalogen ~/lab1. Där lägger man all källkod och kanske resultat från körningar (~ är er hemmakatalog.)
• Det skall finnas en speciell fil som heter ~/lab1/Dokumentation. I denna fil talar ni om vad som finns i de övriga filerna i redovisningskatalogen och eventuellt hur man bär sig åt för att köra programmet. Detta är den första fil som labrättaren tittar i.
• Endast filer som är relevanta för redovisningen skall ligga i ~/lab1.

Ä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

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

• Kursplan.
• Schema läsperiod III D3 00/01 (valfria 1)
• Läsanvisningar.
• Gamla tentor.
• Kompilatorkonstruktion vt00. Information från förra året.

• Kurskatalog D.
• Kurser i Datalogi.
• Tentamensschema

Haskell-prylar!

• Haskells hemsida.
• Haskell Bookshelf. Här finns mycket intressant att läsa, t ex What the hell are Monads?, som visar hur monader kan förenkla programmeringen.
• Libraries and Tools For Haskell. Länkar till bland annat Happy och Alex.

För andra språk

• C: Flex, Bison. flexbisonwin32 (diskussion om Flex/Bison i Windows-miljö)
• Java: JLex, CUP. The Java Language Specification.

Kompilatorer, allmänt

• Nyhetsgruppen comp.compilers
• Kategorin Compilers i dmoz open directoty.
• www.compilerconstruction.org, kan det vara nåt?
• The Great Computer Language Shootout. Jämför hur snabb kod ett 20-tal olika kompilatorer (gcc, g++, ghc, smlnj, ocaml, java, ...) producerar för ett antal små testprogram. Haskell-kompilatorn GHC ligger mycket bra till på flera av testen!

[ | ]