Nada

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


Utvärdering

Resultatet av enkäten kommer att presenteras i kursnalysen.

Senaste Nytt

010308 Tentalösningar finns nu. Meddela Mikael eventuella feltryck.

010226 Konflikter i java_cup hanteras into som konflikter hanteras i Bison. I java_cup får varje regel en prioritet som är lika med prioriteten hos den sista slutsymbolen i högerledet. Detta kan leda till att den genererade parsers reducerar istället för att skifta om det finns en skift-reduce konflikt (till exempel vid if-else). Se avsnitt 2 i cup-manualen.

010215 Fel i javapub.l som finns i /info/syntax01/labbar/5/java-grammatik/ rättat.

På rad 143 i javapub.l stod det
"null" {return NULL;}

vilket ändrats till
"null" {return JNULL;}

Om du redan kopierat javapub.l, rätta i din kopia, annars kommer du att få svårbegripliga fel när du använder den tillsammans med grammatiken i samma katalog.

010130 Kursbunt finns åter på expeditionen.

Om du gjort "course join syntax01" sker numera några initieringar när du loggar in. Detta hjälper java och javac att hitta java_cup och JLex, och ger dig också tillgång till "rätt" make samt kommandot "jflex". Om du tittar i filen /info/syntax01/module/syntax01 ser du precis vilka initieringar som görs. Hör av dig om det leder till trassel.

010129 Kursbunt och kursbok är tillfälligt slut. Kursboken lär vara beställd till kårbokhandlen och kan säkert köpas på nätet eller av folk som tidigare gått kursen. Kursbunten är på omtryckning och blir förhoppningsvis klar till onsdag 31/1.

Kopior på OHbilder.
Eftersom flera personer frågat har jag kopierat OH-bilderna från föreläsning 5. Några har jag hoppat över eftersom de bara var utdrag ur filerna till labb 3. Kopiorna finns i en pärm i förrummet till Nadas elevexpedition.

010128 Nya filer till labb 3.
Tyvärr blev fel version av filerna för labb 3 upplagda i kurskatalogen. Nya filer finns nu parallellt med de ursprungliga i katalogerna c_ny, m3_ny och java_ny. Läs mer här.

010121 Feltryck i kurs-pm:

  1. Labbar ska redovisas senast i septemberperioden 2001.
  2. Man lämnar kursen med >>course leave syntax01>>.
Det finns en gnu-version av JLex också: JFlex. Jag har inte provat den själv, men om du gör det så är jag intresserad av dina synpunkter! Vill du prova den så ge kommandot

/info/syntax01/JFlex/bin jflex regler.l

Den är nästan helt kompatibel med JLex-filer (undantag är att tecknen ! och ~ är specialtecken i JFlex, men vanliga tecken i JLex). JFLex rättar till ett par av JLex egenheter.

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å 9-11 3-8 Q2
F to 15-17 3-8 E2
L fr 9-11 4-8 Spelhallen
L må 16-18 9 Sporthallen, Musiksalen
L må 8-10 11-12 Sporthallen

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 syntax01» 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 syntax01». Detta kommando gör tre saker:

När du är klar med kursen ger du kommandot »course leave syntax01» 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 syntax01»). 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 syntax01»). 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/syntax01/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 2001.
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/syntax01». På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

Manualer m m

Diverse länkar

^ Upp till kursens hemsida.

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