bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Utbildning / Kurser / 2D1373 / syntax06

2D1373 Artificiella språk och syntaxanalys, 4p
VT 2006

Kursen ges läsåret 2005/2006 i period 3 med Mikael Goldmann (migo@kth.se) som kursansvarig.

Senaste nytt

060522

Snälla, hjälp till genom att fylla i kursenkäten!

Alla nyheter

Redovisning av projektet

Kontrollera instruktionerna om vad som krävs av ditt program och av dokumentationen. Skicka dokumentationen med e-post till kursledaren minst två dagar före redovsiningen.

Tryck här för att hämta bokningslistor:

Schema

Eventuella ändringar i schemat kommer att införas nedan.

Vecka 3, 2006 Moment Lokaler
Ons 18 jan 13:00-15:00 Frl Q33
Tor 19 jan 10:00-12:00 Frl Q33
 
Vecka 4, 2006
Tis 24 jan 10:00-12:00 Frl Q33
Tor 26 jan 10:00-12:00 Frl Q33
Fre 27 jan 13:00-15:00 Lab Spel, Sport
 
Vecka 5, 2006
Tis 31 jan 10:00-12:00 Frl Q33
Tor 2 feb 10:00-12:00 Frl Q34
Fre 3 feb 13:00-15:00 Lab Spel, Sport
 
Vecka 6, 2006
Tis 7 feb 10:00-12:00 Frl Q33
Tor 9 feb 10:00-12:00 Frl Q34
Fre 10 feb 13:00-15:00 Lab Spel, Sport
 
Vecka 7, 2006
Tis 14 feb 10:00-12:00 Frl Q33
Tor 16 feb 10:00-12:00 Frl D3
Fre 17 feb 13:00-15:00 Lab Spel, Sport
 
Vecka 8, 2006
Tis 21 feb 10:00-12:00 Frl Q33
Tor 23 feb 10:00-12:00 Frl Q33
Fre 24 feb 13:00-15:00 Lab Spel, Sport
 
Vecka 9, 2006
Tis 28 feb 10:00-12:00 Lab Spel, Sport
Ons 1 mar 13:00-15:00 Lab Spel, Sport
 
Vecka 10, 2006
Ons 8 mar 14:00-19:00 TEN Q15, Q24, Q25
 
Vecka 11, 2006
Fre 17 mar 13:00-15:00 Lab Spel
 
Vecka 12, 2006
Fre 24 mar 13:00-15:00 Lab Spel
 
Vecka 23, 2006
Fre 10 juni 08:00-13:00 TEN

Lärare

Mikael Goldmann är kursansvarig och föreläsare. Mikael nås enklast via epost (migo@kth.se), eller på mottagningstiden (tisdagar 10--11) i rum 1444.

Vem får läsa kursen

Kursen är valfri och kan läsas på många inriktningar. Den förutsätter att man har förkunskaper motsvarande någon av kurserna 2D1320 Tillämpad datalogi, 2D1340 Introduktion till datalogi, 2D1343 Datalogi, 2D1344 Grundläggande datalogi.

Kursens mål

Kursens mål är att ge

  • ge de teoretiska grunderna för definition och analys av programspråk och andra artificiella språk,
  • ge förmåga att utveckla lämpliga notationer för beskrivning av olika typer av problem,
  • ge förmåga att konstruera översättare från en notation till en annan,
för att studenterna
  • ska känna till kraftfullheten och begränsningarna hos automater och artificiella språk,
  • i praktiska situationer ska kunna specificera lämpliga inmatningsnotationer för datorprogram och konstruera analysatorer för dem.

Examination

Tenta

Det krävs ingen föranmälan till CSCs tentor. Tentan innehåller ett antal teorifrågor som ska lösas utan hjälpmedel. Ordinarie tentatillfälle och tillfälle för förta omtentan framgår av schemat ovan.

Programmeringsprojekt

Projektet går ut på att bygga en syntaxanalysator för MiniJava som producerar ett syntaxträd. Syntaxträdet ska sedan analyseras med hjälp av "Visitors" för att utföra en typkontroll.

Betyg

Betygskriterierna finns beskrivna i det utdelade kursprogrammet.

Kurslitteratur

Bok

Andrew Appel: Modern Compiler Implementation in Java, 2nd edition, Cambridge University Press, 2002, ISBN 052182060X. (Observera att den skiljer sig mycket från första upplagan)

Kursen kommer i stort att följa upplägget i denna bok och projektuppgiften är hämtad härifrån. Detta är också kursboken på fortsättningskursen Programspråksimplementation.

Exempelsamling

Exempelsamligen innehåller ett stort antal lösta exempeluppgifter, några implementationsuppgifter (applex) samt ett teoriavsnitt. Teoriavsnittet täcker teori som endast presenteras översiktligt, eller inte alls, i Appels bok. Exempelsamlingens teoriavsnitt ingår i kursen.

Kompletterande material

Ett fåtal saker som ingår i kursen täcks varken av Appels bok, exempelsamlingen eller verktygens dokumentation. I dessa fall hänvisas till utdelat material eller elektroniska källor som anges vid respektive kursavsnitt.

Studentexpedition och Delfi

CSCs studerandeexpedition finns på Osquars backe 2 plan 2.
Öppettider under terminstid:
måndag-fredag 9.45-11.30,
måndag-torsdag 12.45-14.15.
Telefon 08-790 8077,
e-post studentexp@nada.kth.se

Delfi är CSCs systemgrupps mottagning som har hand om konton och passerkort.
Öppettider under terminstid:
Månd - torsd 10-12, 13-15
Fredagar 10-12
e-post: system@nada.kth.se
Telefon: 08-790 71 46

Kursuppläggning

Ap = Avsnitt i kursboken (Appel), ApEx = Övningsexempel i kursboken (Appel), Öv = Avsnitt i kompendiet med övningsexempel, PT = Parsing Techniques: A Practical Guide.

F1: Introduktion. Administration. Formella språk och ändliga automater. (Ap 1, 2.3; Öv 0.1-0.3)

F2: NFA, NFA = DFA, DFA-minimering. (Ap 2.4-2.5; ApEx 2.6 Öv 6.1--6.5; OH (pdf))

F3: Reguljära uttryck och språk. NFA = DFA = RE. Verktyg för lexikal analys. (Ap 2.1, 2.2, 2.5; dokumentation av JavaCC och JFlex; Öv 6)

F4: Icke-reguljära språk och pumpningslemmat. Kontextfria grammatiker. (Appel 3.1; Öv 0.4, 5.7, 7.1-7.7)

L1: Arbeta med Applex 1 och påbörja eventuellt Applex 2 (eller Programmeringsuppgiften till kap 2 i Appel).

F5: Kontextfria språk. Stackautomater. Syntaxanalys uppifrån och ner (LL-analys), rekursiv medåkning. First- och Follow-mängder. (Appel 3.2; Öv 0.5, 7.8--7.9, 8, OH (pdf))

F6: Tabellstyrd LL-analys. Konflikter. JavaCC. (Ap 3.2; Öv 8; JavaCC-dokumentation, OH (pdf))

L2: Avsluta Applex 1, arbeta med Applex 2. Påbörja Applex 3 (som även kan lösas med JavaCC)

F7: Syntaxanalys nerifrån och upp (LR-analys). Shift-reduce-analysator. LR-tabeller. (Ap 3.3-3.5)

F8: LR-annalys (forts). Konflikter. Parsergeneratorn Cup. (Ap 3.3-3.5; Öv 9)

L3: Avsluta Applex 2, arbeta med Applex3.

F9: Cup. Konflikter. Attributgrammatiker. Semantiska åtgärder. (Ap 4; Öv 9; PT 2.9; Cup-manualen)

F10: Bygga syntaxträd. Traversering av syntaxträd med Visitors. Typkontroll i MiniJava. (Ap 4 och 5). Exempel

L4: Avsluta Applex 3, påbörja Applex 4 (eller Programmeringsuppgifterna till Appel kap 3 (och 4)).

F11: Avsluta typkontroll: symboltabeller, omgivningar och räckvidd för definitioner (Ap 4).

F12: Avluta teorin. Chomskyhierarkin (PT 2.3). Pumpningslemmat för kontextfria språk (Öv 0.6-0.7). Exempel.

L5: Avsluta Applex 4. Påbörja projektet.

L6: Arbeta med projektet.

L7/L8: Redovisa projektet.

Konto vid CSC

För att kunna delta behöver du ett användarkonto på CSCs datorer. Kontakta kursledaren om du inte har något konto.

Sidansvarig: Mikael Goldmann <migo@kth.se>
Uppdaterad 2006-03-01