Nada

Kursanalys för 2D1373, 1998 års kursomgång

Kurs: Artificiella språk och syntaxanalys
Kursnummer: 2D1373
Antal poäng: 4 (2 poäng lab och 2 poäng tenta)
Kursledare och lärare: Lars Engebretsen
Undervisning: 24h föreläsning, 12h övning, 14h terminalövning
Antal registrerade elever: 60
Kurslitteratur: Parsons, Introduction to compiler construction, W.H. Freeman, New York.

Resultatstatistik

TENTASTATISTIK

   Nr   Datum    Tot   U    (%)     3    (%)     4    (%)     5    (%)

   1    980305    47    3    6.4    10   21.3    13   27.7    15   31.9
   2    980423     4    0    0.0     0    0.0     3   75.0     1   25.0
   Totalt 48 godkända av 60 (80.0%)

LABSTATISTIK (ALLA)

   Lab   Ant G     (%)   Ant S     (%)   Totalt  (%)

   1       38     63.3      1      1.7     39     65.0
   2       38     63.3      1      1.7     39     65.0
   3       38     63.3      0      0.0     38     63.3
   4       38     63.3      0      0.0     38     63.3
   5       41     68.3      0      0.0     41     68.3

LABSTATISTIK (GODKÄNDA PÅ TENTA)

   Lab   Ant G     (%)   Ant S     (%)   Totalt  (%)

   1       33     68.8      0      0.0     33     68.8
   2       33     68.8      0      0.0     33     68.8
   3       33     68.8      0      0.0     33     68.8
   4       33     68.8      0      0.0     33     68.8
   5       36     75.0      0      0.0     36     75.0

LABSTATISTIK (EJ GODKÄNDA PÅ TENTA)

   Lab   Ant G     (%)   Ant S     (%)   Totalt  (%)

   1        5     41.7      1      8.3      6     50.0
   2        5     41.7      1      8.3      6     50.0
   3        5     41.7      0      0.0      5     41.7
   4        5     41.7      0      0.0      5     41.7
   5        5     41.7      0      0.0      5     41.7

38 godkända på lab1-momentet och 48 på ten1-momentet ger en prestationsgrad på 72%. Godkänt på hela kursen har 32 elever, det vill säga 53%.

Mål

Kursens mål är att

för att eleverna

Sammanfattning

Jag tycker kursen fungerar i stort sett bra. Takten i kursen kändes ganska låg i början av kursen, och snabbare mot slutet.

Undervisningen

Undervisningen bedrevs i föreläsningsform, på övningarna gavs eleverna möjlighet att själva lösa problem inom kursen. Jag fanns tillgänglig för att svara på frågor under övningstimmarna.

Examination

Halva kursen examineras med laborationer, halva med en skriftlig tentamen. Labkursen består av fyra små laborationer, som redovisas för någon elev på kursen, och en projektuppgift som redovisas för kursledaren eller terminalassistent. Tentamen består av en teoridel utan hjälpmedel och en problemdel med hjälpmedel.

Kurslitteratur

Kurslitteraturen består delas av Parsons bok och dels av en exempelsamling med lösningar. Parsons bok passar hyfsat bra med kursens inriktning, exempelsamlingen fyller i de hål som finns. Tyvärr finns det ganska många tryckfel i boken, jag har med elevernas hjälp upprättat en errata på kursens hemsida.

Utvärdering

I slutet av den sista föreläsningen hade vi en liten utvärderingsdiskussion. Jag förde minnesanteckningar.

Kursboken
Boken går ofta långt ner i detaljer, men ibland sopar författaren enstaka detaljer under mattan. En ordlista för kursens facktermer vore bra. Boken och föreläsningarna ger något olika bilder av kursen.
Övningshäftet
Antalet uppgifter är lagom, och lösningarna är bra. Övningshäftet och boken har tyngdpunkten på olika saker. Övningshäftet och föreläsningarna upplevs höra ihop bättre.
Laboration 1-4
De är lagom stora och fyller sitt syfte, nämligen att vara till hjälp vid instuderingen av kursmaterialet. Avsaknaden av feedback är en nackdel (labbarna redovisas ju inte). Vi diskuterade att göra färdiga lösningar, men det ansågs farligt av några. Ett annat alternativ är att lösningarna finns, men att man måste be kursledaren om att få dem. Man kan också tänka sig någon form av kontrollfrågor som stöd. Det är ju dessutom tillåtet att fråga kursledaren om man är osäker på om man har gjort rätt eller inte.
Föreläsningarna
Ger ofta mer översiktliga samband, medan boken är ganska detaljerad. Några av föreläsningarna var för korta (de slutade en kvart för tidigt). Vissa saker som behandlas ganska mycket på föreläsningarna behandlas summariskt i boken. I synnerhet gäller detta automater och hierarkier av beräkningsmodeller.
Räkneövningarna
Några tyckte att det var bra med schemalagd, handledd studietid. Många tyckte att det var olyckligt att räkneövningarna råkade äga rum klockan åtta på morgonen. En möjlighet är att byta ut räkneövningarna mot utökad mottagningstid. Då förlorar man möjligheten till direkt hjälp. Å andra sidan tänker man ofta igenom sina frågor lite mer om man ska gå iväg till någons rum och fråga honom där. Några tyckte att just schemaläggningen var värdefull; då har man en avsatt tid för studier inom kursen. Alla var överens om att två timmars självstudier ger eleven mer än två timmar på en "klassisk" KTH-övning.
Terminalövningarna
Även här tyckte några att det var bra med en schemalagd laborationstid, både för möjligheten att få hjälp och för att det blev två timmar avsatta till datorövningar inom kursen.

Kursens verkliga innehåll

Följande tabell visar vad som preliminärt kommer att behandlas under föreläsningarna. Angivelser inom parentes svara mot avsnitt i kursboken. För övningarna och terminalövningarna anges rekommenderade uppgifter i övningshäftet respektive labbhäftet.

vecka 3
F1 hur en kompilator fungerar i stort (1.1-1.10)
F2 ändliga automater, DFA=NFA, minimal DFA (2.1-2.5, appendix A)
Ö1 automater (uppgift 1.1-1.7)
vecka 4
F3 formella språk, reguljära uttryck, RE=DFA, reguljära uttryck i Unix. (2.6-2.10)
F4 Lex, hur Lex fungerar (appendix B.1)
Ö2 reguljära uttryck, Lex (uppgift 2.1, 2.2, 2.5, 2.7)
TÖ1 labb 1: simulering av NFA
vecka 5
F5 grammatik, syntaxträd, BNF, grammatik för naturliga språk (3.1.1-3.1.5)
F6 stackautomat (PDA), Turingmaskin (TM), Chomskyhierarkin (3.1.6-3.1.8)
Ö3 grammatiker, PDA, TM (uppgift 1.8, 1.9, 3.1, 3.3-3.5)
TÖ2 labb 2: lexikal analys med Flex
vecka 6
F7 uppifrån-och-ner-syntaxanalys, rekursiv medåkning (3.2-3.5)
F8 botten-och-upp-syntaxanalys, Bison (4.1, appendix B.2)
Ö4 LL-analys, Bison (uppgift 4.1, 4.2, 4.3, 4.5, 5.4)
TÖ3 labb 3: rekursiv medåkning
vecka 7
F9 hur Bison fungerar, LR(k), LALR(1) (4.2-4.4)
F10 avancerad Bison (appendix B.2)
Ö5 LR-analys, Bison (uppgift 5.1-5.3, 5.7)
TÖ4 labb 4: reguljära uttryck med Flex och Bison
vecka 8
F11 intern representation, kodgenerering, optimering, språkkonstruktion (5.1-5.3)
F12 attributgrammatik, felhantering, fortsättningskurser (5.4-5.8)
Ö6 attributgrammatik (uppgift 5.5, 5.8, 5.9)
TÖ5 arbete med labb 5: en valfri översättare
vecka 9
TÖ6 arbete med och redovisning av labb 5: en valfri översättare
vecka 11
TÖ7 arbete med och redovisning av labb 5: en valfri översättare
vecka 12
TÖ8 arbete med och redovisning av labb 5: en valfri översättare

Nedan anges mycket kort vad som verkligen hänt:

vecka 3
Allmän introduktion. Dessutom definierade jag DFA och NFA, gick igenom exempel 1.1 i exempelsamlingen och visade att DFA:er och NFA:er känner igen precis samma mängd språk. Som avslutning nämnde jag två tillämpningar av DFA:er: KMP-automater (exempel 1.2) och BDD:er. Jag hann inte med att beskriva algoritmen som minimerar en DFA. På övningen fick jag frågan vad man menar när man skriver att "x tillhör {0,1}*". Det betyder helt enkelt att x är en sträng som består av noll eller flera tecken ur {0,1}.
vecka 4
Jag definierade reguljära uttryck, och visade att RE och DFA känner igen exakt samma mängd av språk. Ena halvan av detta bevis finns i kursboken och andra halvan finns nedskriven i övningshäftet (uppgift 2.4). Därefter gick jag igenom grunderna i Flex.
vecka 5
Jag pratade om grammatiker, definierade dem och beskrev hur man härleder strängar av slutsymboler från produktionerna i en grammatik. Dessutom definierade jag automattyperna DPDA och NPDA och visade att DPDA är strikt kraftfullare än NFA. Jag definierade begreppet kontextfri grammatik och påstod att NPDA och kontextfria grammatiker är lika kraftfulla, men att NPDA är strikt kraftfullare än DPDA. Dessutom nämnde jag att turingmaskinen är strikt kraftfullare än NPDA:n och visade en algoritm som givet en sträng och en kontextfri grammatik avgör om strängen kan genereras av grammatiken.
vecka 6
Jag gick igenom rekursiv medåkning, som heter recursive descent på engelska, applicerat på programmet i laboration 3. Därefter definierade jag First-mängder noggrant och Follow-mängder mer intuitivt. Sedan använde jag dessa begrepp för att diskutera hur rekursiv medåkning kan automatiseras till tabellstyrd uppifrånochneranalys. Avslutningsvis gick jag igenom grunderna i Bison, och hur Bison samarbetar med Flex för att producera en syntaxanalysator.
vecka 7
Jag gick igenom LR-analysatorn på det klassiska sättet: LR(0) till SLR(1) till LALR(1) till LR(1). Sedan diskuterade jag varför vänsterrekursion är att föredra vid LR-analys samt hur konflikter i LR-tabellen kan uppkomma och lösas. Till sist visade jag hur man kan få Bison att producera spårutskrifter.
vecka 8
Jag gick igenom attributgrammatiker, syntetiserade och ärvda attribut, vad som händer när man tar bort vänsterrekursioner i en attributgrammatik, samt hur LL- och LR-analys kan hantera attribut. Sedan pratade jag om olika intermediärrepresentationer och nämnde lite om maskinoberoende optimering. Vi avslutade med en liten utvärdering.

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

Jag kommer att ta bort övningarna helt och hållet, och istället utöka min mottagningstid. Jag kommer förmodligen att ta bort problemdelen på tentan, och istället utöka teoridelen en smula. Inga hjälpmedel kommer då att tillåtas på tentan.


Sidansvarig: <enge@nada.kth.se>
Senast ändrad 28 maj 1998