Nada

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

Nyheter vecka 31

Sista tid för redovisning av LAB-momentet för 1999 års kursomgång är 17:00 den 31 augusti 1999.


Nyheter vecka 20

Tid och plats för nästa omtenta är bestämda: Lördagen den 21 augusti, 8:00-13:00, sal F11.


Nyheter vecka 17

Jag har lagt upp resultatet av utvärderingsdiskutionen på webben.

Laborationsresultaten kommer att rapporteras in nästa gång den 4 juni. Det går bra att redovisa innan dess, men resultatet kommer inte att rapporteras in förrän den 4 juni. Tag kontakt med mig för att boka en redovisningstid.


Nyheter vecka 15

Omtentorna är rättade och finns på expeditionen från måndag (1999-03-19).

Jag har postat ett inlägg i nada.kurser.syntax angående kursutvärdering; läs gärna det.


Nyheter vecka 12

Jag har lagt in extra redovisningstillfällen fredagen den 16 april i bok-systemet. Boka endast en tid per grupp.


Nyheter vecka 11

Tentorna är rättade och finns på expeditionen. Det var genomgående bra resultat, både på torsdagens och lördagens tenta. Nästa omtenta äger rum torsdagen den 15 april.

Jag kommer att ha mottagning på måndag vecka 12 (1999-03-22), men därefter har jag mottagning enligt överenskommelse.

Tack för en trevlig kursomgång.


Nyheter vecka 9

Jag har lagt upp redovisningstider för laboration 5 i bok-systemet. Boka endast en tid per grupp. I KTH-schemat är redovisningen schemalagd till 17:00-19:00, men jag har lagt in tillfällen 15:00-17:00 också, för dem som vill slippa sitta i skolan sent på kvällen. I laborationshäftet står det uppstolpat vad ni ska göra och hur ni ska redovisa laborationen.

Det står fel i lösningen till tal 2a i tentan 1998-08-21. Det reguljära uttrycket i lösningen skall vara (K|VK*V)*.


Nyheter vecka 8

På föreläsningarna gick jag igenom hur vissa ärvda attribut kan hanteras under syntaxanalys nerifrån och upp, samt hur attribut hanteras under syntaxanalys uppifrån och ner.

Tentan kommer att bestå av sex tal, varav det sista är något av ett överkurstal. Det räcker med 2½ avklarade tal för godkänt, 3½ för betyg 4 och 4½ för betyg 5. Universitetsstuderande får VG för 4 avklarade tal. Inga hjälpmedel är tillåtna på tentan, se kurs-pm för detaljer.

Jag är bortrest onsdag till söndag vecka 9. Viggo Kann tar emot redovisningarna på onsdagen i brun sal. Han svarar också på frågor i mån av tid.


Nyheter vecka 7

På föreläsningarna gick jag igenom konstruktion av LR(0)- SLR(1)-, LALR(1)- och LR(1)-tabeller, begreppet attribut och visade hur syntetiserade attribut kan hanteras under LR-analysen.

Tid och plats för den extra ordinarietentan är lördagen den 13 mars klockan 14.00-19.00 i sal F55. Jag vill att ni i första hand utnyttjar ordinarietillfället (den 11 mars), och jag vill att ni som tänker skriva tentan den 13 mars anmäler er snarast till mig med datorpost <enge@nada.kth.se>. Det är inte tillåtet att utnyttja båda tillfällena.

Parsons är lite otydlig när han beskriver de olika typerna av LR-analysatorer i sin bok. LR(0)-analysatorn beskriver han inte alls. SLR(1)-analysatorn kallar han kort och gott för SLR-analysatorn. Samma sak gäller LALR(1)-analysatorn. Det som Parsons kallar "the canoical LR parser" är helt enkelt LR(1)-analysatorn. På sidan 156 i kursboken finns en mening som är mycket olyckligt formulerad, på fjärde raden i näst sista stycket: "[LALR parsers] are as powerful as canonical LR parsers." Det jag tror Parsons menar är, att i de fall det går att konstruera en LALR(1)-tabell ur en LR(1)-tabell så känner LALR(1)-analysatorn igen samma språk som LR(1)-analysatorn. Däremot finns det grammatiker som är LR(1) men som inte är LALR(1). En sådan finns i exempelsamlingen. Överhuvudtaget kan jag rekommendera exempelsamlingen som komplement vid instuderingen av LR-analysatorerna. I exempelsamlingen (lösningsdelen) har jag försökt att klart och tydligt stolpa upp vad som karakteriserar LR(0)-, SLR(1)-, LALR(1) respektive LR(1)-tabellerna.

Några har fått problem med felmeddelanden av typen

("parser.y", line xx) error: type clash (`states' `') on default action
("parser.y", line yy) error: type clash (`states' `letter') on default action
i laboration 4. Felmeddelandet beror på att det finns en semantisk standardåtgärd {$$=$1;}, och den ger problem då $$ och $1 har olika typer. Ett sätt att komma ifrån problemet på är att skriva tomma sematiska åtgärder, {}, vid de regler som blir problem. Jag har (den 15 februari) lagt upp en ny version av filerna, som innehåller en kommentar om detta, i »/info/syntax99/labbar/4».


Nyheter vecka 6

På föreläsningarna gick jag igenom syntaxanalys nerifrån och upp, först verktyget Bison och sedan analyseringsalgoritmen och konstruktion av en LR(0)-tabell.

Eftersom det är så pass många (ett tiotal) som har tentakrock både på ordinarietentan och påsktentan har jag beslutat att ge en extra tenta. Preliminärt siktar jag på eftermiddagen den 13 mars, slutgiltig tid och plats kommer att anslås här.

Jag har installerat några exempel som visualiserar LR-analys. De är kompilerade för Solaris och finns i katalogen »/info/syntax99/v-yacc/exempel».

Jag har lagt upp ett redovisningstillfälle för laboration 5 1999-03-03 i bok-systemet. Boka endast en tid per grupp. Fler tider samma dag kommer att läggas upp om behov uppstår.


Nyheter vecka 5

På föreläsningarna gick jag igenom syntaxanalys uppifrån och ner (top-down parsing), definierade FIRST- och FOLLOW-mängder och presenterade rekursiv medåkning (recursive descent) och tabellstyrd LL(1)-analys. Dessutom pratade jag om Chomsky-hierarkin, definierade stackautomater (DPDA och NPDA) och visade att varje kontextfri grammatik kan kännas igen av en NPDA.


Nyheter vecka 4

På föreläsningarna gick jag igenom reguljära uttryck och visade några satser. Dels hur man bygger en NFA från ett givet reguljärt uttryck och dels att det finns språk som inte kan beskrivas av något reguljärt uttryck. Sedan började jag gå igenom transformationsgrammatiker och definierade vad som menas med en kontextfri grammatik.

Jag fick en fråga på onsdagens föreläsning om det var tillåtet att visa att ett visst språk inte är reglujärt genom att reducera till det kända icke-reguljära språket {anbn : n>=0}. Efter att ha funderat lite på detta har jag beslutat att det är tillåtet, men jag förbehåller mig rätten att på tentamen kräva ett bevis som inte reducerar till ett känt icke-reguljärt språk. (Dessutom finns det gott om icke-reguljära språk som inte kan reduceras till {anbn : n>=0}, så det lönar sig nog att lära sig det direkta beviset hur som helst.)

Olyckligtvis hade det smugit sig in ett fel i filerna »casio.c» och »Casio.m3» i kurskatalogen. Jag hade missat att ')' ingår i FOLLOW-mängderna till <factor>, <term> och <expr>. Jag hoppas att ni inte har drabbats av alltför mycket merarbete på grund av detta. Nu (30 januari) har jag lagt ut en korrigerad version.


Nyheter vecka 3

På föreläsningarna gick jag igenom ändliga automater (DFA och NFA) och visade två satser, dels att varje NFA kan konverteras till en DFA, och dels att det finns en algoritm som minimerar antalet tillstånd i en given DFA.

Tyvärr tog kursbuntarna slut. Nu (21 januari) har jag lagt in tio nya buntar på expeditionen.


Lärare

Kursledare och föreläsare är Lars Engebretsen, <enge@nada.kth.se>, rum 1443. Telefonnumret dit är 790 68 09.

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. 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 60 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 övningshä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 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

På KTH-schemat står det att det ska vara sex salsövningar i kursen, vilket är fel. Istället finns kursledaren tillgänglig för frågor under terminalövningarna. Dessutom är en terminalövning tillagd i vecka 3 och terminalövningarna veckorna 4--9 är framflyttade två timmar.
Fmå 10-12v 3-8E3
Fon 13-15v 3-8E3
Lon 15-17v 3-9Konsthallen, Matsalen
Lon 17-19v 11-12Konsthallen, Matsalen
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. 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). 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 syntax99» 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 syntax99». Detta kommando gör tre saker:

När du är klar med kursen ger du kommandot »course leave syntax99» 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. Endast den sista uppgiften examineras. Sista redovisningstillfälle för denna kursomgångs laborationsmoment är septemberperioden 1999.

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

Tentamen

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

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 i år blir tentamen väsentligen 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 (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. Sista tentamenstillfälle denna kursomgång är septemberperioden 1999.

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

Diverse länkar

^ Upp till kursens hemsida.


Sidansvarig: <enge@nada.kth.se>
Senast ändrad 4 aug 1999.