bild
Skolan för
datavetenskap
och kommunikation

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

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

Vi testar att använda php för kurssidorna. Förhoppningsvis kommer det att fungera bra. Kontakta kursledaren om sidorna uppför sig konstigt.

Senaste nytt

050328

Tentan är rättad. Använd

  res show syntax05

för att se resultatet.

Alla nyheter

Topp>>

Schema

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

Topp>>

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.

Topp>>

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.

topp>>

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.

Topp>>

Examination

Tenta

Det krävs ingen föranmälan till Nadas 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.

Topp>>

Kurslitteratur

Bok

Det finns flera böcker som kan fungera som kursbok på kursen. I första hand rekommenderas

Andrew Appel: Modern Compiler Implementation in Java, 2nd edition, Cambridge University Press, 2002, ISBN 052182060X. (Observera att den skiljer sig ganska 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.

Några andra alternativ är:

  • T W Parsons: Introduction to compiler construction, Computer Science Press, New York, 1997, ISBN 0716782618. Det finns tyvärr ett antal tryckfel i boken, både i den första tryckningen (1992) och den andra tryckningen (1997).
  • Alfred V. Aho, Ravi Sethi och Jeffrey D. Ullman: Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, 1986 ISBN 0201100888.

Topp>>

Studentexpedition och Delfi

Nadas studerandeexpedition finns på Osquars backe 2 plan 2. Den har öppet må-to 9.45-11.30 och 12.45-14.15, samt fr 9.45-11.30.

Delfi är Nadas systemgrupps mottagning som har hand om konton och passerkort. Delfi har öppet må-to 10-12 och 13-15, samt fr 10-12.

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)

L1: Påbörja Applex 1.

F3: Reguljära uttryck och språk. NFA = DFA = RE. Verktyg för lexikal analys. (Ap 2.1, 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)

L2: Avsluta Applex 1. Påbörja 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)

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

L3: Avsluta 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)

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

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)

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

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.

L6: Arbeta med projektet.

L7/L8: Redovisa projektet.

topp>>

Konto vid Nada

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

topp>>

Förändringar sedan förra läsåret

Förra året användes Appels bok som en alternativ kursbok för de studenter som vill läsa programspråksimplementation. I år är Appels bok ordinarie kursbok. Implementation av typkontroll i MiniJava var förra året ett av flera projektalternativ och visade sig fungera bra. Jämfört med andra projektalternativ innebär det att man å ena sidan arbetar med de verktyg och tekniker som är centrala i kursen och å andra sidan slipper det ganska omfattande och repetitiva arbete som det innebär att arbeta med grammatiken för ett riktigt språk. Det ger också en mer direkt övergång till 2D1375. Den som vill kan föreslå ett alternativt projekt.

Sidansvarig: Mikael Goldmann <migo@kth.se>
Uppdaterad 2005-11-03