Nada

Kursanalys för 2D1372, Artificiella språk och syntaxanalys, våren 1996

Kursdata

Tid: period 3 läsåret 1995/96 dvs januari-mars 1996.
Poängantal: 3 (varav labb 1 poäng, tenta 2 poäng).
Tenta: ordinarietenta efter period 3 (4 mars), omtenta i påskperioden (9 april).
Föreläsningar: 28 timmar.
Övningar: 14 timmar.
Labbar: 4 små och en större, 12 timmar schemalagd tid.
Kurslitteratur: Boken Introduction to compiler construction av T W Parsons och häftet Automata and BDDs - new tools in verification and optimization av S Arnborg.
Kursansvarig och lärare: Viggo Kann.
Antal elever: 65, varav 51 från D, 4 från F, en från M, 8 från SU och en doktorand.

Avklarade moment 1996-06-01:

Ordinarietenta 48 av 51 (94%)
Omtenta         6 av 8  (75%)
Tenta, totalt  54  (83%)
Labb 1-4       60  (92%)
Labb 5         37  (57%)
Prestationsgrad:    74%
Examinationsgrad:   55%

Bakgrund

Undervisningen i automatteori, formella språk och enkel kompilatorkonstruktion låg fram till och med för årskurs D-90 i kursen Programkonstruktion under andra året. I den kursen ingick ett ganska stort kompilatorprojekt (4 poäng). För årskursen D-91 ersattes den kursen av en lingvistikkurs och en kurs i algoritmer och datastrukturer (också med namnet Programkonstruktion). Lingvistikkursen innehöll till viss del teorin om automater och formella språk men detta kursavsnitt undervisades på ett sätt som gjorde eleverna inte tillgodogjorde sej kunskaperna. Som en nödåtgärd las en labb i Lex och Yacc in i Programkonstruktion.

För D-92 ersattes lingvistikkursen av Kommunikation och kognition, och därigenom försvann det aktuella kursavsnittet helt från utbildningen. Som ännu en nödåtgärd las kursen Översättarteknik in obligatoriskt i årskurs tre för Programsystemteknikinriktningen. Översättartekniken tog upp delar av teorin, men koncentrerade sej på användningen av den inom kompilatorkonstruktion.

I och med kursomläggningen som inträffade för D-93 så ersattes översättarteknikkursen av två nya kurser: Artificiella språk och syntaxanalys och Programspråksimplementation. Den första kursen är obligatorisk för Programsystemteknikinriktningen under våren i trean medan fortsättningskursen är valfri under hösten i fyran.

Tanken var att Artificiella språk och syntaxanalys skulle innehålla all teori om automater och formella språk tillsammans med exempel på hur teorin kan tillämpas på lexikal och syntaktisk analys i praktiska fall, inom både översättning av programspråk och andra notationer. Kursen har bara gått en gång.

Kursen Programspråksimplementation går första gången i höst och kommer att ta upp alla steg i programspråksimplementation utom lexikal och syntaktisk analys. Kursen blir mindre teoretisk än syntaxkursen.

Elevernas synpunkter

Två enkäter gjordes med ACE, en för tentan (19 svar, 37%) och en för resten av kursen (23 svar, 35%). Fullständigt resultat finns i WWW. Här följer en sammanfattning av enkätsvaren.

Kursinnehåll

Kursen ansågs vara medelsvår (70%), på gränsen till lätt (22%). Nästan alla (87%) fick i början av kursen klart för sej vad kursens mål var. 96% tyckte kursen var intressant och meningsfull, varav 61% tyckte den var mycket intressant och meningsfull. Förkunskaperna (Inda) var tillräckliga för i stort sett alla.

Kurslitteratur

Kursboken fick ett gott omdöme (87% tyckte bra eller mycket bra om den). BDD-kompendiet fick däremot ett blandat mottagande. Hälften hade inte använt det, någon tyckte det var mycket bra och några att det var mindre bra eller dåligt. Föreläsningsanteckningarna (ca 80 sidor) ansågs vara mycket bra (70%) eller bra (30%) och fick kommentarer som "Korta, koncisa och intressanta! Suveränt!"

Undervisningen

Ungefär hälften gick på i stort sett alla föreläsningarna och nästan alla gick på åtminstone hälften av föreläsningarna. Hälften ansåg att föreläsningarna var mycket bra och hälften att dom var bra. Några kommentarer:
"Jag är mycket nöjd, Viggo är en av de bästa lärare jag haft här på KTH."
"Jag tycker inte man kan kräva så mycket mer av en föreläsare. Välstrukturerat, bra och tydliga förklaringar, kompetent och lite kul ibland."
"Konceptet att ha utskrivna stordia som man kan anteckna på är mycket bra. Man slipper allt detta kopierande."
"kanske lite för mycket oh eftersom man hade alla oh framför sig men i övrigt bra".

Labbarna

Simulering av NFA Ansågs lätt till medelsvår.
Flex Ansågs mycket lätt till lätt.
Rekursiv medåkning Ansågs medelsvår till lätt.
Reguljära uttryck med Yacc Ansågs medelsvår.
En valfri översättare Ansågs ganska svår.

Labb 4 och 5 ansågs mest givande. Några blandade kommentarer:
"Jag tycker att jag lärt mig mycket mer på dessa labbar än på vissa andra labbkurser där labbarna har vart mycket svårare och mer tidskrävande."
" Väldigt intressant. Kul att se att man kan göra något nyttigt med sina kunskaper (H-kodsgenererare)."
"Bra att avsluta med en lite krångligare..."
"Lab 1-4 var alla ganska så lätta, de var aldrig riktigt svåra. Jag saknade ett mellansteg mellan laboration 4&5 i svårighetsgrad alltså. Laboration 4 får gärna luta mer åt 5:an än mot 3:an. Det blir ett ganska så tvärt kast."
"Tja, valde ju själv i labb 5 hur mycket man ville göra, blev lagom."

Nedlagd studietid

Dom flesta la ner mellan 15% och 50% av sin totala studietid på kursen. Nästan alla läste två eller tre kurser parallellt med kursen.

Statistik för labbtid:

Labb   Godk   LT/G  Medel    10%   25%   40%   50%   60%   75%   90%

1       83%    96%    4.6    2.0   3.0   4.0   4.0   4.0   6.0   8.0
2       83%   100%    1.8    1.0   1.0   1.0   2.0   2.0   2.0   4.0
3       82%   100%    3.1    1.5   2.0   2.0   3.0   3.0   4.0   5.0
4       76%    96%    5.0    2.5   3.0   4.0   4.5   5.0   6.0   8.0
5       47%    97%   23.4    7.0  12.0  15.0  17.0  20.0  24.0  30.0

Tot                  37.9   14.0  21.0  26.0  30.5  34.0  42.0  55.0

Godk = elever som fått godkänt på labben
LT/G = elever som angett labbtid av dem som fått godkänt

Tentan

Tentan ansågs medelsvår (53%) eller ganska lätt (37%). Den ansågs spegla kursinnehållet bra eller mycket bra (84%). Kommentarerna var i huvudsak positiva: "Utmärkt att tentan rättades så snabbt! Möjligen var det lite grymt att hela sista talet delvis hängde ihop, så att det om man missade a) delen blev ganska svårt att göra resten av talet..." "Teoridelen var mycket bra - hade man hängt med i kursen så gick det bra på teoridelen. Däremot kan jag tänka mig att denna del var klurig om man inte hade pluggat särskilt mycket. Då det gäller problemdelen tycker jag inte att den speglade kursinnehållet lika bra. Det var väldigt mycket grammatik, syntaxanalys och i princip ingenting annat. I stort tycker jag dock att tentan var bra!" "Vettiga teoridelsfrågor. Jag tyckte att tentan var lagom svår för mig. Schysst rättning." "Exemplarisk tenta, hade man gått på föreläsningar samt läst kursboken och gjort labbarna så kunde man knappast misslyckas med tentan. För den skull säger jag inte att den var för lätt."

Tentan rättades på tre dagar och resultatet var mycket bra (3 blev underkända, 16 fick betyg 3, 16 betyg 4 och 16 betyg 5). Att sista talet var värt så mycket som 19 poäng av 50 verkar inte ha inneburit något hinder. Alla som fick godkänt på tentan klarade åtminstone första delen av sista talet, och dom tre som fick underkänt var inte närheten av att klara tentan i alla fall.

Allmänna elevkommentarer

Genomgående intressant och trevlig. Sist jag följde en kurs i samma utsträckning var i 1:an under Diff&Int-kursen.
Jag gillar kursen!
Jag gillar Viggos engagemang. Han bryr sig och respekterar oss; det gillar jag.
Utmärkt kurs! Det är bara att hoppas att kursen i programspråksimplementation blir lika bra!
Trevlig kurs, blandar teori och praktiskt labbande på ett bra sätt. Verkar användbar. Den ovation Viggo fick vid sista föreläsningens slut hade han helt klart gjort sig förtjänt av!
En mycket givande och intressant kurs grattis!!
Bra och intressant labbar. Krävde inte nattjobb i datasalarna men gav mycket. Kursen skulle bli väldigt teoretisk utan labbarna.
Guldkurs! Jag väntar på fortsättningen.
Jag tycker att fr o m LR-delen i kursen och framåt så blev det väl detaljerat. Fast å andra sidan krävs ju ingen utantillärning. Tentaformen (med teoridel och problemdel) är mycket bra eftersom man då inte behöver lära in massa detaljer till problemdelen, man får ju ha boken då.
Jag tror att det är så att kursen översättarteknik har delats upp i två delar - denna kurs samt programspråksimplementation. Jag skulle föredra en stor kurs framför dessa två småkurser.
Labbarna var lätta, men man lärde sig vansinnigt mycket igentligen. En näst intill perfekt labbkurs mao. Jag har en tendens att bli lite trött när jag går på föreläsningar, men när jag var vaken var det mycket bra! Kursboken, bra upplagd, men det var väldans många tryckfel. Fixa en errata eller nåt till den.
Mycket bra!!!

Anpassning till andra kurser

Närliggande kurser är Programmeringsparadigm (vad gäller beskrivning av syntax och kompilering), Algoritmer, datastrukturer och komplexitet (vad gäller teoretisk datalogi och Turingmaskiner) och Digital elektronik (vad gäller ändliga automater). Enda överlappet är med paradigmkursen i första årskursen, och det måste finnas ett visst överlapp, men det bör förstås inte vara för stort.

En D-teknolog bör tidigt få se hur man kan beskriva syntax och semantik för programspråk. Däremot är nog ingen djupare förståelse för syntaxanalys eller vilka överväganden som ligger bakom konstruktionen av programspråksgrammatiker nödvändigt i ProgP.

En så ingående beskrivning av interpretering och kompilering som görs i ProgP just nu tycker jag inte är nödvändigt. Dom som är intresserade av detta kan läsa programspråksimplementationskursen. Det räcker att eleverna förstår så pass mycket av vad som försiggår inuti kompilatorn att dom förstår varför programspråk ser ut som dom gör (t ex parameteröverföringsmekanismer, definitionsområde och livslängd för deklarationer) och varför typiska programmeringsfel får så allvarliga konsekvenser (minneshantering, stack, heap, representation av variabler och andra objekt).

Jämförelse med liknande kurser

Automater, formella språk och syntaxanalys tillhör standardstoffet i datalogi och undervisas därför vid varje universitet i världen som har en D-utbildning. Uppläggningen verkar dock variera. På en del ställen tas allt upp i en kurs i kompilatorkonstruktion, och då blir teoridelen ofta lidande. På andra ställen finns det en separat teorikurs där automater och formella språk ingår och dessutom en praktiskt inriktad kompilatorkurs. När kurserna är uppdelade på detta sätt (t ex i Linköping) verkar dom ha liten kontakt med varandra, och den teoretiska kursen borde kännas ganska torr.

Att det är ovanligt att dela upp översättarteknik på det sätt som vi gör styrks också av bristen på böcker med detta innehåll. Kursboken jag använt (och som jag är mycket nöjd med) är visserligen inriktad på översättning av programspråk, men den tar upp teorin ordentligt och går inte in på programspråksimplementationen förrän i dom tre sista kapitlen.

Jag är dock övertygad om att den uppdelning vi har valt är den rätta, och att dom flesta elever bara borde behöva läsa syntaxkursen och bara dom extra intresserade läsa fortsättningskursen. Intresset för fortsättningskursen verkar dock vara oväntat stort.

Förändringar till nästa kursomgång

Eftersom kursen har gått så bra kommer den inte att ändras mycket till nästa gång. Jag tänker behålla samma upplägg och kursbok. Här är en lista med ändringar som jag (troligen) tänker genomföra.

Nedskärning av timantalet. D-lärarmötet 11 januari 1996 kom fram till att den schemalagda salsundervisningen borde minskas till tolv timmar per poäng. Därför kommer kursen nästa gång bara att ha 12 föreläsningar och 6 övningar (istället för 14 respektive 7).
I lydelsen till labb 5 kommer jag att betona att uppgiften inte behöver vara så omfattande. Jag ska också försöka hitta på nya förslag till mindre uppgifter. Därigenom kanske fler elever hinner redovisa sista labben i tid.
Labb 2 gick i år ut på att skriva ett Flexprogram som översatte tecken i kommentarer och strängar i ett C-program, men inte på andra platser. Eftersom flera har tyckt att det var så pass lätt så kanske jag försöker hitta på någon svårare Flexuppgift till nästa gång.
Jag kommer att göra en erratalista till boken.
Jag kommer att säga mer om hur LL- och LR-tabellerna förhåller sej till dom teoretiska stackautomaterna.

Upp till aktuella kurssidan.

Sidansvarig: <viggo@nada.kth.se>
Senast ändrad 6 juni 1996
Tekniskt stöd: <webmaster@nada.kth.se>