Nada

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

Senaste Nytt

2002-08-15

Jag tar emot restredovisningar av projektuppgiften fram till den 30 augusti, i första hand 22/8, 29/8 och 30/8. Tid bokas via mail.

2002-04-17

Jag har nu skrivit en kursanalys. Den är baserad på era enkätsvar och mina intryck.

2002-04-12

Jag har nu lämnat labbresultaten till expeditionen för inrapportering, så de borde snart synas i LADOK/ping.

2002-04-03

Tentan 2002-04-02 är rättad. Resultaten finns i res.

2002-04-02

Jag tänkte ta emot restredovisningar av projektuppgifter fredagen den 12 april. Bokningslista finns på dörren till mitt rum (1434, Nada plan 4).

2002-03-20

Det finns en lus i Cup som gör att man kan få följande felmeddelande vid körning om man har stora grammatiker:

Exception in thread "main" java.lang.ClassFormatError: CUP$parser$actions
(Code of a method longer than 65535 bytes)
        at java.lang.ClassLoader.defineClass0(Native Method)

Jag har fått, och installerat, en patch för detta på Nada. Det är filen emit.java i Cup-distributionen som är ändrad.

2002-03-20

Jag har nu satt upp bokningslistor även för nästa vecka. De tider man kan boka är 10.00-11.30 samt 14.00-16.30 tisdag, onsdag och torsdag samt 17.00-17.30 tisdag och onsdag.

2002-03-18

Många av dem som kör någon av kodförskönaruppgifterna har hört av sig till mig och frågat hur kommentarer ska hanterats. Som ni har lagt märke till är det lite bökigt att ta hand om kommentarer eftersom de kastas bort i den lexikala analysen. Jag tycker att ni kan strunta i att hantera kommentarer, men fundera igenom hur man skulle kunna ta hand om dem så kan vi prata lite om det på redovisningen.

2002-03-18

Planen för projektuppgiftsredovisningar är följande: Jag har satt upp en bokningslista på min dörr med tider onsdag, torsdag och fredag denna vecka, 14.00-17.30 alla tre dagarna. Vid behov går det bra att redovisa torsdag förmiddag också, dock helst inte före 10.00.

Veckan därpå kommer det att finnas redovisningsmöjligheter tisdag, onsdag och torsdag samt eventuellt måndag förmiddag.

Sista dag för bonus är ju torsdag nästa vecka. För er som inte hinner redovisa innan dess kommer jag att ha redovisningstillfällen i anslutning till omtentorna. Nästa omtenta är redan tisdagen den 2 april, så jag planerar att ha ett redovisningstillfälle veckan efter. Nästnästa omtenta är i september. Ni som inte har redovisat projektet när septemberperioden är slut kommer jag normalt att hänvisa till nästa kursomgång, som börjar januari 2003. Jag brukar göra undantag från detta för personer som ska ta ut sin examen, åka utomlands en längr tid, och dylikt. Det är inte säkert att labbdelen av kursen är samma nästa år. Det har varit få förändringar i uppgifterna de senaste åren, men man kan tänka sig att bonussystemet kommer att fungera annorlunda (jag kommer förmodligen inte att ha kursen nästa år).

2002-03-08

Tentan 2002-03-07 är rättad. Resultaten finns i res.

2002-02-22

För er som vill redovisa projektuppgiften före tentan har jag reserverat eftermiddagen tisdagen den 5 mars. Bokning sker på listan på min dörr, rum 1434 på Nada plan 4. Redovisningen är också i mitt rum. Om ni absolut inte kan redovisa den eftermiddagen men ändå vill redovisa innan tentan kan ni kontakta mig.

Ytterligare ett förtydligande angående extentorna: De senaste två åren användes ett annat bonussystem än det jag valde att använda. Därför kunde man få vissa uppgifter på tentan tillgodoräknade om man hade redovisat vissa laborationer i tid. I år är bonussystemet annorlunda och därför kommer man inte att få några uppgifter på tentan tillgodoräknade automatiskt.

2002-02-18

En del har undrat lite om redovisning av projektuppgiften. I kurs-pm står det att man kan få bonus om man redovisar senast tre veckor efter ordinarietentan; det visade sig bli skärtorsdagen. Jag kommer att anordna redovisningsmöjligheter med jämna mellanrum på något sätt under tiden fram till skärtorsdagen. Tider och platser annonseras på den här webbsidan. Det är naturligtvis tillåtet att redovisa redan på torsdag eller på måndag om man är färdig.

Jag har lagt upp OH-bilderna till föreläsning 11. Det finns ett tryckfel i kurs-pm: Tentamen är torsdagen den 7 mars 2002.

Jag har fått en del frågor om varningar som dyker upp när man kompilerar den kod som genereras av Flex och Bison. Tyvärr går en del av dem inte att få bort på ett enkelt sätt, så man får leva med dem. Det brukar vara »normalt» att få varningar på följande form:

/pkg/gnu-make/1.3/share/bison.simple: In function `yyparse':
/pkg/gnu-make/1.3/share/bison.simple:432: warning: implicit declaration of function `yylex'

lex.l:368: warning: `yyunput' defined but not used
Man kan också få någon varning angående yyerror() beroende på var man har definierat den.

2002-02-13

Jag fick tips om en tillämpning av Flex och Bison: De används för att tolka ett scriptspråk till Zephyr på Nada. Källkod för den intresserade finns exempelvis i katalogen /pkg/zephyr/src/zephyr-2.0.4-sunos/clients/zwgc i Nadas unix-system.

2002-02-12

Extentor från de senaste fyra kursomgångarna finns på kursens hemsida. De tre äldsta tentorna består av en teoridel och en problemdel; årets tenta kommer inte att se ut på det viset utan istället ha samma struktur som de tre senaste årens tentor.

Det fanns ett fel i lösningen till uppgift 7.2 i övningshäftet. Eftersom det dessutom tidigare har funnits en del småfel i peken till applexen har jag lagt upp hela det reviderade kompendiet i PDF-format. Dokumentet är ganska stort, så skriv helst inte ut mer av det än ni verkligen behöver. För att de kapitel som innehåller applex skulle få samma nummer som respektive applex minskade jag alla kapitelnummer med ett.

Jag har lagt upp nya versioner av ett par filer till C-versionerna av applex 3 och 4 i kurskatalogen eftersom de gamla innehöll ett par mindre fel. Det fanns ett fel applex 3 som gjorde att fel debuginformation skrevs ut i nextToken() och det fanns ett deklarationsfel av konstanten EPSILON i applex 4.

Jag har lagt upp nya versioner av ett par filer till Java-versionen av applex 4, de gamla filerna innehöll ett par skrivfel.

2002-02-05

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.

2002-01-31

Det fanns tyvärr ett midre fel i filen lexer.c som används i applex 3. Korrigerad version finns nu på kurskatalogen.

Det finns en viss risk för att jag bytte plats på snedstreck och kommatecken när jag gick igenom övergångar i stackautomater på föreläsningen igår. Rätt notation är hursomhelst den som står i kompendiet: a / b , c1c2c3.

2002-01-29

För den som tycker att pumpnings-lemmat är extremt spännande finns även ett lemma som inte pumpar: Guo-Qiang Zhang och Rodney E. Canfield, The end of pumping?, Theoretical Computer Science, 174(1-2):275-279, 1997. (Artikeln finns i Nada-biblioteket.)

2002-01-25

JFlex-manualen innehåller ett missledande exempel på sidan 8 där det ser ut som om nyrad-tecknet ska beskrivas av det reguljära uttrycket \\n. Det exemplet matchar i själva verket strängen som innehåller ett bakvänt snedstreck följt av ett n; för att matcha nyradtecknet använder man det reguljära uttrycket \n.

Ett klargörande angående peket till applex 2: yylval används enbart i Flex, i JFlex används Symbol-objektet istället.

2002-01-24

Det finns en oklarhet i applex 2 angående vad som är tal. Det räcker om ni hanterar icke-negativa decimaltal utan plus eller minus framför. Den lexikala analysatorn som ni skriver i applex 2 ska användas som en komponent i applex 3 och där visar det sig att negativa tal kommer att hanteras av grammatiken för taluttryck. Den lexikala analysatorn ni skriver i applex 2 ska alltså översätta teckenströmmen -3.5 till slutsymbolerna MINUS och NUMBER<3.5>. Den syntaktiska analysatorn i applex 3 kommer att se slutsymbolerna MINUS och NUMBER<3.5> och ur detta extrahera talet -3.5.

2002-01-22

Ett tillstånd har fallit bort i figuren på sidan 27 i övningshäftet. Jag har lagt upp en PDF-version av den korrigerade sidan 27.

2002-01-21

Det fins tyvärr ett tryckfel i övningshäftet. Tillståndet längst till höger i figuren på sidan 16 ska vara q10 istället för q0 och det ska dessutom vara accepterande. Jag har lagt upp en PDF-version av den korrigerade sidan 16 i kompendiet.

Lärare

Kursledare och föreläsare är Lars Engebretsen.

Kurslitteratur

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

Kursbunt

Kursbunten kan köpas på Nadas elevexpedition. Papper som delas ut under kursens gång kommer att finnas i en pärm i hyllan utanför expeditionen.

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).

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

F   må   13-15   v 3,6-8   E2
F   ti   13-15   v 3       E2
F   ti   13-15   v 4-6     Q2
F   ti   15-17   v 8       E2
F   on   15-17   v 4-5     E2
F   on   15-17   v 7       F3
L   fr   10-12   v 4-6     Spel, Sport
L   to   08-10   v 7       Grå, Karmosin
L   to   10-12   v 8       Sport, Musik, Konst
L   må   13-15   v 9       Spel, Sport

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.

Manualer m m

Diverse länkar

^ Upp till kursens hemsida. -->

Sidansvarig: <enge@nada.kth.se>
Senast ändrad 15 augusti 2002.