Nada

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


Senaste Nytt

11 mars
Nu kan du boka tid för att redovisa labb 5.
Tryck här för att hämta bokningslistor:
10 feb
Hur man  kopplar ihop  flex och bison.
7 feb
Exempelfilerna från föreläsning 7 finns här.
26 jan
Parsons har kommit till kårbokhandeln!


Årets versioner av filerna till labb 3 finns nu på kurskatalogen. Om någon redan hunnit börja med labb 3 och vill fortsätta att använda filerna från VT-99 så finns de på /info/syntax99/labbar/3/
Grammatiken som används i casio.c och Casio.m3 avviker något från labblydelsen:
Produktionen

 factor --> prim | prim ^ factor
har vänsterfaktoriserats till
 factor  --> prim factor1
 factor1 --> epsilon | ^ factor

Lärare

Kursledare och föreläsare är Mikael Goldmann, <migo@nada.kth.se>, rum 1444. Telefonnumret dit är 790 68 13.

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, 1997, ISBN 0-7167-8261-8. Ca pris: 505 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 70 kronor. Papper som delas ut under kursens gång kommer att finnas i en pärm i hyllan utanför expeditionen.

Läsanvisning

Kursboken skall läsas enligt följande:
Kapitel Nivå
kapitel 1-5 Ingår i detalj.
kapitel 6-8 Ingår inte alls.
appendix A Ingår i detalj.
appendix B Läs översiktligt, inga tentafrågor.
Dessutom ingår de övningsexempel som inte är märkta med »kuriosa» i övningshäftet.

Ett alternativ till kursboken Parsons är att läsa den så kallade »drakboken»: Alfred V. Aho, Ravi Sethi och Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, 1986.

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.

Ett tredje alternativ är att använda någon av Appels böcker, Modern compiler implementation in ML / Java / C, och kombinera den med någon bok som behandlar formella språk. Det finns flera sådana böcker, en klassiker är Hopcroft och Ullman, Formal languages and their relation to automata, från 1969. Den finns också i en nyare variant, Introduction to automata theory, languages, and computation, från 1979. En kompakt skriven, men mycket prisvärd bok är Révész, Introduction to formal languages.

Schema

Aktivitet Tid Vecka Sal
F må 8-10 3-8 E2
F to 15-17 3-8 E3
L fr 8-10 4-8 Spelhallen
L må 16-18 9,11-12 Spelhallen

Följande tabell visar vad som preliminärt kommer att behandlas under föreläsningarna. Angivelser inom parentes svarar mot avsnitt i kursboken.

vecka 3:
F1 - Hur en kompilator fungerar i stort (1.1-1.10), formella språk, ändliga automater (2.1-2.4).

F2 - DFA=NFA, minimal DFA (2.5, appendix A). Kapitel 2 (ej 2.7-2.10) och 3 i exempelsamlingen.
Uppgift 1 i laborationshäftet.
vecka 4:
F3 - reguljära uttryck, RE=DFA, Flex, reguljära uttryck i Unix, hur Flex fungerar (2.6-2.7, 2.9, appendix B.1, Flex-manualen).

F4 - Språk som inte är reguljära, grammatik, syntaxträd, BNF (2.8, 3.1). Kapitel 4 i exempelsamlingen.
Uppgift 2 i laborationshäftet.
vecka 5:
F5 - Syntaxanalys uppifrån och ner, rekursiv medåkning (3.2-3.5).

F6 - Stackautomat (PDA), turingmaskin (TM), chomskyhierarkin (3.1.6-3.1.8). Resten av kapitel 2 samt kapitel 5 (ej 5.6) i exempelsamlingen.
Redovisa uppgift 1 och 2 i laborationshäftet. Uppgift 3 i laborationshäftet.
vecka 6:
F7 - Syntaxanalys nerifrån och upp, Bison (4.1, appendix B.2, Bison-manualen).

F8 - Hur Bison fungerar, LR(k), LALR(1) (4.2-4.4). Kapitel 6 i exempelsamlingen.
Uppgift 4 i laborationshäftet.
vecka 7:
F9 - Avancerad Bison (appendix B.2).

F10 - Intern representation, kodgenerering, optimering, språkkonstruktion (5.1-5.3).
Redovisa uppgift 3 och 4 i laborationshäftet. Påbörja uppgift 5 i laborationshäftet.
vecka 8:
F11 - Attributgrammatik vid analys uppifrån och ner, (5.4).

F12 - Attribut vid analys nerifrån och upp, att undvika ärvda attribut (5.5-5.8). Uppgift 5.6 i exempelsamlingen.
Fortsätt med uppgift 5 i laborationshäftet.
vecka 9:
Avsluta och redovisa uppgift 5 i laborationshäftet.
vecka 11:
Reservtid för redovisning.
vecka 12:
Reservtid för redovisning.

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.

Dessutom måste du, för att kursledaren ska kunna hålla reda på dina resultat, registrera dig i Nadas resultatrapporteringssystem. Detta görs med kommandot »res checkin syntax00» 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 syntax00». Detta kommando gör tre saker:

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

Examination

Kursen består av en tentamen (2 poäng) och en laborationsdel (2 poäng). 

Laborationer

Laborationsdelen består av fem laborationer (fyra små och en lite större) som görs i grupper om högst två personer. 

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 syntax00»). 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 syntax00»). 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/syntax00/m3bison».

Tentamen

Tentamen består av ett antal teoriuppgifter - inga hjälpmedel är tillåtna. Programmering examineras inte på tentamen, däremot ska man naturligtvis i stora drag kunna redogöra för hur verktygen Flex och Bison arbetar internt. För godkänt krävs minst 50% av den totala poängsumman.

Notera att tidigare års uppdelning i teori- och problemdel är avskaffad; från och med förra året består tentamen väsentligen av en något utökad teoridel där inga hjälpmedel tillåts.

Resultatet anslås högst tre veckor efter tentamen på institutionens anslagstavla på plan~3. Klagomål på rättning av tentan lämnas in skriftligen till kursledaren inom tre veckor från det att tentaresultatet anslagits. Sista tentamenstillfälle denna kursomgång är septemberperioden 2000.
Tentan går i period 3, Påsk och i augusti.

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/syntax00». På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

Diverse länkar

^ Upp till kursens hemsida.

Sidansvarig: <migo@nada.kth.se>
Senast ändrad 11 jan 2000.