Kompilatorteori, cdt301

Mål:

Studenten ska efter kursen kunna konstruera kompilatorer som översätter program skrivna i ett högnivåspråk till assemblerprogram.
Detta innebär att studenten specifikt ska kunna:

Formulera en sammanhangsfri grammatik utifrån en informell beskrivning av ett sammanhangsfritt språk, med hjälp av BNF.
Skapa en rekursiv top-down kompilator utifrån en sammanhangsfri grammatik.
Använda verktyg för automatgenererade kompilatorer. Detta inkluderar att kunna tolka felmeddelanden från verktyget.
Hantera syntaxdriven översättning för typanalys.
Visa vilken roll en aktiveringspost har under körning av ett program som består av fler än en funktion.

Kurstillfällen:

Vårterminen 2010, lp 2
Kursansvarig: Linus Källberg
Dagtid, för alla utbildningsprogram inom IDE och fristående.
Vårterminen 2009, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för alla utbildningsprogram inom IDE och fristående.
Höstterminen 2007, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för alla utbildningsprogram inom IDE och fristående.
Höstterminen 2006, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för alla utbildningsprogram inom IDE och fristående.
Höstterminen 2005, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för Dataingenjörsprogrammet 2003, Datalogiprogrammet 2003, Civilingenjörsprogrammet i datateknik o elektronik 2003 och fristående.
Höstterminen 2004, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för Datateknikprogrammet 2002, Datalogiprogrammet 2002 m.fl.
Höstterminen 2003, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för Datateknikprogrammet 2001, Datalogiprogrammet 2001 m.fl.
Höstterminen 2002, lp 2
Kursansvarig: Lars Bruce
Dagtid, för Datateknikprogrammet 2000, Datalogiprogrammet 2000 m.fl.
Höstterminen 2001, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för Datateknikprogrammet-99, Datalogiprogrammet-99 m.fl.
Höstterminen 2000, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för Datateknikprogrammet-98, Datalogiprogrammet-98 och fristående.
Höstterminen 99, lp 2
Kursansvarig: Christer Sandberg
Dagtid, för Datateknikprogrammet-97, Datalogiprogrammet-97 och fristående.
Höstterminen 98, lp 2
Kursansvarig; Jacek Malec
Dagtid, för Datateknikprogrammet-97, Datalogiprogrammet-97 och fristående.
Höstterminen 97
Kursansvarig: Christer Eriksson/Jukka Mäki-Turja

Varför "grotta sig" i kompilatorer?

Det är väl ändå lite udda?! Kanske tänker du: "Men jag ska inte börja på Microsoft och utveckla kompilatorer..." - OK, men den här kursen är antagligen för dig ändå! Teorierna som ligger till grund för en kompilator är generella och kan tillämpas i de mest skilda sammanhang där någon form av översättning behövs, och tillämpningarna blir allt fler.
Exempel på översättare:

Tolkning av script, kommandotolkar, "kommandofiler", etc.
Spel: användarmodifierade banor, objekt etc. Direkttolkning av optioner.
Web: databasportering /tolkning
Översättning från C till Java?!
Systemspecifik preprocessor
"Pretty printers", t.ex. att presentera innehållet i en C-fil med syntax highlight i html-format.
... eller varför inte nämna Latex, html, PS mm är dokument med inbäddade kommandon - alltså ett formellt språk en tolkning av texten behövs alltså även om slutresultatet inte ska bli maskinkod.
Portering: Ett företag kan behöva översätta en stor del av sin kod från ett språk till ett annat.
- Exempel 1: Fortrankod motsvarande 10 manår finnes. Önskas: all denna kod i C. Vad behövs? - En kompilator!
- Exempel 2: 1GB CF-baserade hemsidor finnes. önskas: Samma hemsidor baserade på PHP. Vad behövs? - En kompilator!
...och så programspråk, förstås! (interpretering, kompilering förkompilering, etappvis kompilering), OBS: när det gäller inbyggda system kan det ofta finnas behov av lokala anpassningar, den övervägande delen av alla datorsystem är något helt annat än PC!

Användningsområdet är alltså betydligt bredare än vad namnet "Kompilatorteori" antyder. Under kursen kommer vi dock att fokusera på just "vanliga kompilatorer" då detta ger en stor täckning av problemen (t.ex. så inrymmer en pre-processor bara en delmängd av de problem som en kompilator får tackla).
Vi jobbar med konstruktioner från ett C-liknande programmeringsspråk som input och översättning till en "abstrakt maskinkod", men för att förstå det senare måste du vara familjär med någon processormodell (kunna de enklare instruktionerna som move, push, pop, call och att använda stacken för parameteröverföring).
Kursen har ett stort inslag av labbar. Labbarna är direkt kopplade till teorin.
Du får lära dig jobba med utvecklingsverktygen Bison och Flex (Yacc och Lex), som är vanliga vid utveckling av kompilatorer. Du får också lära dig teorin bakom dessa verktyg. Bison och flex är fria program, det finns gott om fria C-kompilatorer. Du kan alltså göra alla dina labbar hemma om du vill.
Förkunskaper: Helst "auber" i nödfall: God uppfattning om DFA:er och reguljära språk från diskmatten.
Vardaglig beskrivning av kursen:
Massor av häftiga och kluriga algoritmer, svåra men roliga labbar.
Har du inte hunnit vänja dig vid rekursion i tanke och programmering? - Nu kommer du att bli van!

Kurslitteratur

Den i sammanhanget klassiska "drake"-boken: "Compilers: Principles, Techniques and Tools",
av Alfred V. Aho, Monica S. Lam, Ravi Sethi och Jeffery D. Ullman, (Addison-Wesley). ISBN: 978-0-321-49169-5

[Senast uppdaterad 10-03-21] [506 accesser]