Nada

Aktuell information om 2D1373, Artificiella språk och syntaxanalys

I kurs-pm:et står det att man får ha med sig föreläsningsanteckningar på tentan. Det är egentligen en kvarleva från förra året, då Viggo kopierade upp föreläsningsanteckningar. Eftersom det står kvar i pm:et gäller det naturligtvis fortfarande; det är tillåtet att ta med sig sina anteckningar från föreläsningarna. Det är inte tillåtet att ta med sig övningshäftet eller extentor med lösningar.

Lärare

Kursledare och föreläsare är Lars Engebretsen, <enge@nada.kth.se>, rum 1443. Telefonnumret dit är 790 68 09 och han har under kursens gång mottagningstid tisdagar 15.30--16.30 samt enligt överenskommelse.

Kurslitteratur

Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar, övningsuppgifter och laborationer täcker endast en del av kursmaterialet.

Kursbok

"T W Parsons: Introduction to compiler construction", Computer Science Press, New York, 1992, ISBN 0-7167-8261-8. Pris: 395 kronor i kårbokhandeln. Det finns tyvärr ett antal tryckfel i boken, både i den första tryckningen (1992) och den andra tryckningen (1997).

Kursbunt

Kursbunten kan köpas på första föreläsningen och därefter på Nadas elevexpedition för 20 kronor. Papper som delas ut under kursens gång kommer att finnas i en pärm i hyllan utanför expeditionen.

Det har tyvärr visat sig att det finns tryckfel i både labbhäftet och övningshäftet. Jag har också lagt upp en sida med frågor och svar till uppgift 5 i labbhäftet.

Läsanvisning

Kursboken skall läsas enligt följande:
KapitelNivå
kapitel 1-5Ingår i detalj.
kapitel 6-8Ingår inte alls.
appendix AIngår i detalj.
appendix BLäs översiktligt, inga tentafrågor.
Dessutom ingår övningshäftet.

Ett alternativ till kursboken Parsons är att läsa den så kallade drakboken, dvs "Aho, Sethi, Ullman: Compilers, principles, techniques, and tools", Drakboken har tidigare år använts som kursbok i kursen Översättarteknik som från och med 1996 ersatts av Artificiella språk och syntaxanalys.
Avsnitt i Parsons Motsvarande i drakboken Nivå
kapitel 1 kapitel 1 Ingår i detalj.
- kapitel 2 Läs översiktligt, inga tentafrågor.
kapitel 2 kapitel 3 Ingår i detalj.
kapitel 3-4 kapitel 4 Ingår i detalj.
kapitel 5 kapitel 5 Ingår i detalj.
appendix B.1 (Lex) avsnitt 3.5 Läs översiktligt, inga tentafrågor.
appendix B.2 (Yacc) avsnitt 4.9 Läs översiktligt, inga tentafrågor.
- kapitel 6-12 Ingår inte alls.
I drakboken ska alltså kapitel 1-5 läsas.

Schema

F ti 13-15   v 3-8        K2
F on 08-10   v 3-8        E2

Ö to 08-10   v 3-8        F31

L to 10-12   v 4-8        Spel,Sport
L må 15-17   v 9,11,12    Spel,Sport

Följande tabell visar vad som preliminärt kommer att behandlas under föreläsningarna. Angivelser inom parentes svara mot avsnitt i kursboken. För övningarna och terminalövningarna anges rekommenderade uppgifter i övningshäftet respektive labbhäftet.

vecka 3
F1 hur en kompilator fungerar i stort (1.1-1.10)
F2 ändliga automater, DFA=NFA, minimal DFA (2.1-2.5, appendix A)
Ö1 automater (uppgift 1.1-1.7)
vecka 4
F3 formella språk, reguljära uttryck, RE=DFA, reguljära uttryck i Unix. (2.6-2.10)
F4 Lex, hur Lex fungerar (appendix B.1)
Ö2 reguljära uttryck, Lex (uppgift 2.1, 2.2, 2.5, 2.7)
TÖ1 labb 1: simulering av NFA
vecka 5
F5 grammatik, syntaxträd, BNF, grammatik för naturliga språk (3.1.1-3.1.5)
F6 stackautomat (PDA), Turingmaskin (TM), Chomskyhierarkin (3.1.6-3.1.8)
Ö3 grammatiker, PDA, TM (uppgift 1.8, 1.9, 3.1, 3.3-3.5)
TÖ2 labb 2: lexikal analys med Flex
vecka 6
F7 uppifrån-och-ner-syntaxanalys, rekursiv medåkning (3.2-3.5)
F8 botten-och-upp-syntaxanalys, Bison (4.1, appendix B.2)
Ö4 LL-analys, Bison (uppgift 4.1, 4.2, 4.3, 4.5, 5.4)
TÖ3 labb 3: rekursiv medåkning
vecka 7
F9 hur Bison fungerar, LR(k), LALR(1) (4.2-4.4)
F10 avancerad Bison (appendix B.2)
Ö5 LR-analys, Bison (uppgift 5.1-5.3, 5.7)
TÖ4 labb 4: reguljära uttryck med Flex och Bison
vecka 8
F11 intern representation, kodgenerering, optimering, språkkonstruktion (5.1-5.3)
F12 attributgrammatik, felhantering, fortsättningskurser (5.4-5.8)
Ö6 attributgrammatik (uppgift 5.5, 5.8, 5.9)
TÖ5 arbete med labb 5: en valfri översättare
vecka 9
TÖ6 arbete med och redovisning av labb 5: en valfri översättare
vecka 11
TÖ7 arbete med och redovisning av labb 5: en valfri översättare
vecka 12
TÖ8 arbete med och redovisning av labb 5: en valfri översättare

Nedan anges mycket kort vad som verkligen hänt:

vecka 3
Allmän introduktion. Dessutom definierade jag DFA och NFA, gick igenom exempel 1.1 i exempelsamlingen och visade att DFA:er och NFA:er känner igen precis samma mängd språk. Som avslutning nämnde jag två tillämpningar av DFA:er: KMP-automater (exempel 1.2) och BDD:er. Jag hann inte med att beskriva algoritmen som minimerar en DFA. På övningen fick jag frågan vad man menar när man skriver att "x tillhör {0,1}*". Det betyder helt enkelt att x är en sträng som består av noll eller flera tecken ur {0,1}.
vecka 4
Jag definierade reguljära uttryck, och visade att RE och DFA känner igen exakt samma mängd av språk. Ena halvan av detta bevis finns i kursboken och andra halvan finns nedskriven i övningshäftet (uppgift 2.4). Därefter gick jag igenom grunderna i Flex.
vecka 5
Jag pratade om grammatiker, definierade dem och beskrev hur man härleder strängar av slutsymboler från produktionerna i en grammatik. Dessutom definierade jag automattyperna DPDA och NPDA och visade att DPDA är strikt kraftfullare än NFA. Jag definierade begreppet kontextfri grammatik och påstod att NPDA och kontextfria grammatiker är lika kraftfulla, men att NPDA är strikt kraftfullare än DPDA. Dessutom nämnde jag att turingmaskinen är strikt kraftfullare än NPDA:n och visade en algoritm som givet en sträng och en kontextfri grammatik avgör om strängen kan genereras av grammatiken.
vecka 6
Jag gick igenom rekursiv medåkning, som heter recursive descent på engelska, applicerat på programmet i laboration 3. Därefter definierade jag First-mängder noggrant och Follow-mängder mer intuitivt. Sedan använde jag dessa begrepp för att diskutera hur rekursiv medåkning kan automatiseras till tabellstyrd uppifrånochneranalys. Avslutningsvis gick jag igenom grunderna i Bison, och hur Bison samarbetar med Flex för att producera en syntaxanalysator.
vecka 7
Jag gick igenom LR-analysatorn på det klassiska sättet: LR(0) till SLR(1) till LALR(1) till LR(1). Sedan diskuterade jag varför vänsterrekursion är att föredra vid LR-analys samt hur konflikter i LR-tabellen kan uppkomma och lösas. Till sist visade jag hur man kan få Bison att producera spårutskrifter.
vecka 8
Jag gick igenom attributgrammatiker, syntetiserade och ärvda attribut, vad som händer när man tar bort vänsterrekursioner i en attributgrammatik, samt hur LL- och LR-analys kan hantera attribut. Sedan pratade jag om olika intermediärrepresentationer och nämnde lite om maskinoberoende optimering. Vi avslutade med en liten utvärdering.

Kursregistrering

Om du vill gå kursen ska du anmäla det i förväg till kansliet/studievägledningen för ditt utbildningsprogram. Ingen förhandsanmälan ska göras till Nada. Det finns ingen platsbegränsning.

Så snart kursen börjat måste du registrera dig på den. Detta görs med kommandot res checkin syntax98 på någon av Nadas unixdatorer. Registrera dig så snart som möjligt efter att kursen börjat!

För din egen skull bör du också ge kommandot course join syntax98 Detta kommando gör tre saker:

När du är klar med kursen ger du kommandot course leave syntax98 för att återställa allt.

Examination

Kursen består av en tenta (2 poäng) och en labbdel (2 poäng).

Laborationer

Labbkursen består av fem laborationer (fyra små och en lite större) som görs i grupper om högst två personer. De fyra första labbarna redovisas för någon annan kursdeltagare (denna kursdeltagare kan vara ens labbkamrat), den sista labben ska redovisas för kursledaren eller för en handledare. Då den sista labben redovisas måste de fyra första labbarna vara godkända. Enstaka labbar får inte sparas till annan kursomgång. Om du inte fullgör alla fem labbarna inom ett år från kursens slut har kursledaren rätt att kräva att du gör samtliga labbar i den nya kursomgången.

I kursen använder vi Flex och Bison. Nedan beskrivs hur man på Nada får tillgång till dessa program.

Flex
Gnuprojektets motsvarighet till Lex. Flex startas med kommandot flex som blir tillgängligt med module add gnu-make (som automatiskt görs om du skrivit course join syntax98). Dokumentation fås med man flex, i Info i Emacs och kan köpas på Nadas expedition.
Bison
Gnuprojektets motsvarighet till Yacc. Bison startas med kommandot bison som blir tillgängligt med module add gnu-make (som automatiskt görs om du skrivit course join syntax98). Dokumentation fås med man bison, i Info i Emacs och kan köpas på Nadas expedition.

Labbarna i kursen kan när det är möjligt göras i valfritt programspråk. I labblydelserna föreslås språket C eftersom Flex och Bison är avpassade för just C, men i allmänhet går C++ precis lika bra. Den som hellre vill använda Modula-3 kan göra det i alla labbar utom Flexlabben (labb 2).

Kommandot module add modula-3 gör Modula-3-kompilatorn och M3bison tillgängliga. För den som vill labba hemma finns källkoden till M3bison i katalogen /info/syntax98/m3bison.

Tentamen

Tid och plats för tentamen är torsdag den 5 mars 1998 klockan 14-19 i sal F11-F13. Du behöver inte anmäla dig i förväg.

Tentan består av en teoridel utan hjälpmedel och en problemdel med kursboken och föreläsningsanteckningarna som hjälpmedel. Hela skrivtiden är fem timmar. Efter två timmar måste teoridelen ha lämnats in, men du får gärna göra det tidigare. För godkänt krävs minst 25 poäng av maximala 50.

Tentaresultatet anslås högst tre veckor efter tentan på institutionens anslagstavla på plan 3 (rakt under elevexpeditionen). Klagomål på rättning av tentan lämnas in skriftligen till kursledaren inom tre veckor från det att tentaresultatet anslagits.

Hederskodex

Grundregeln är att det jobb du gör i kursen (labbar, inlämningsuppgifter, tentor m.m.) ska du göra själv, förutom att labbarna kan göras i tvåmannagrupper. Vid redovisning av labbar ska båda i gruppen kunna redogöra i detalj även för vad labbkompisen skrivit.

Ibland, speciellt när man skriver program, kan det vara nödvändigt att fråga någon annan (en kamrat eller en handledare) om hjälp med att hitta fel. Detta är tillåtet förutsatt att du uppfyller följande villkor.

Varje annan form av samarbete och utnyttjande av andras lösningar betraktas som ett brott mot hederskodexen och kan bestraffas, tex genom att du får göra en ny uppgift.

Fördjupnings- och referenslitteratur

Följande litteratur är det inte nödvändigt att ha eftersom den finns tillgänglig i Info i Emacs eller på kursens hemsida, men den som är extra intresserad kan köpa den på Nadas elevexpedition.

Ytterligare informationskällor

All administrativ information finns på kursens hemsida i webben. Viktiga nyheter kommer också att kunna läsas i kursens nyhetsgrupp. Slutligen har kursen en katalog på Unixdatorerna, /info/syntax98. På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

Synpunkter på kursen

Eftersom denna kurs kommer att ges för många elever under flera års tid är vi tacksamma för synpunkter på kursen. En datorstödd kursutvärdering håller på att göras. Synpunkter kan också lämnas direkt till lärarna.

Diverse länkar

^ Upp till kursens hemsida.


Sidansvarig: <enge@nada.kth.se>
Senast ändrad 29 maj 1998.