Kurshemsida: http://stp.lingfil.uu.se/~matsd/uv/uv09/pa/
Parsningsalgoritmer VT 2009
| 2009-03-19 torsdag | 15-16 | PA | MD/MK | turing |
| 2009-04-28 tisdag | 10-12 | PA | MD/MK | turing |
| 2009-04-28 tisdag | 13-16 | PA | MD | chomsky |
| 2009-04-29 onsdag | 10-12 | PA | MD/MK | chomsky |
| 2009-05-05 tisdag | 10-12 | PA | MD/MK | turing |
| 2009-05-05 tisdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-06 onsdag | 10-12 | PA | MD/MK | turing |
| 2009-05-06 onsdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-07 torsdag | 10-12 | PA | MD/MK | turing |
| 2009-05-07 torsdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-12 tisdag | 9-12 | PA | MD/MK | turing |
| 2009-05-12 tisdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-13 onsdag | 10-12 | PA | MD/MK | turing |
| 2009-05-13 onsdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-14 torsdag | 10-12 | PA | MD/MK | turing |
| 2009-05-14 torsdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-19 tisdag | 9-12 | PA | MD/MK | turing |
| 2009-05-19 tisdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-26 tisdag | 10-12 | PA | MD/MK | turing |
| 2009-05-26 tisdag | 13-15 | PA | MD/MK | chomsky |
| 2009-05-28 torsdag | 13-15 | PA | MD/MK | chomsky |
Aktuellt material
- 2009-04-27: Uppvärmningsuppgift flyttad: Nu på Lab. 1
- 2009-04-28: Introduktion. OH
- 2009-04-28-2009-05-05: Shift-reduce-parsning. OH Lab. 1
- 2009-05-06: Cocke-Kasami-Younger-algoritmen (CKY): OH.
- 2009-05-06: CKY (2): OH. Material till Lab. (CKY, icke-examinatorisk): PA-2009-05-06.tar.gz.
- 2009-05-07: Earley-algoritmen (bottom up): OH. Lab. 2 och 3 (Earley, examinatorisk).
- 2009-05-12: Earley-algoritmen (bottom up) (2): OH.
- 2009-05-13: Earley-algoritmen (kanoniska varianten): OH.
- 2009-05-14: Earley-algoritmen (kanoniska varianten) (2): OH.
- 2009-05-19: Dependensparsning OH. Lab. 4 (Dependensparsning med orakel).
- 2009-05-28: Recursive descent och avslutning: OH.
- Deadlines: Labbarna måste in senast 12/6 för att bedömas före sommaruppehållet. (Annars bedöms de tidigast i september.)
Lärandemål
Efter avslutad kurs skall studenten för att förtjäna betyget Godkänd minst kunna:
- redogöra för parsningsproblemet i relation till frasstrukturgrammatiker och någon form av dependensgrammatik.
- redogöra för klassificeringen av olika parsningsalgoritmer i kategorierna top-down/bottom-up och bredden-först/djupet-först.
- redogöra för olika sätt att använda minne och bakåtspårning i olika parsningsalgoritmer
- implementera i ett imperativt/objektorienterat språk (exempel på) följande slag av algoritmer: "recursive-descent", "shift-reduce" och chartparser samt testa och informellt förklara arbetssättet hos dessa implementationer
- dokumentera aktuell kod på ett användbart sätt
- med viss självständighet finna artiklar om andra parsningsalgoritmer och analysera dessa algoritmer utifrån de begrepp som nämns ovan
Examination och arbetssätt
Framsteg noteras i Studentportalen: Noteringar om VG och partiella G som kommentarer. För övrigt: Klar är G och rest U.
Kursen examineras genom två duggor och fyra laborationsuppgifter (skriftliga rapporter kompletterade med "examinatoriskt" samtal). Var och en av dessa bedöms med U, G eller VG. Samtliga måste vara minst G för G och VG som kursbetyg. Dessutom minst tre VG ger VG som kursbetyg.
- Dugga 1, bedömningsprincip: G: båda algoritmerna behärskas. VG: nära nog perfekt hantering av algoritmerna.
Litteratur
Daniel Jurafsky & James H. Martin (1999) Speech and Langauge Processing, 357-361.
Joakim Nivre (2008) "Algorithms for deterministic incremental dependency parsing" Computational Linguistics, Vol. 34. (Valda delar.)
Stuart M. Shieber, Yves Schabes & Fernando C. N. Pereira (1995) "Principles and implementation of deductive parsing" The Journal of Logic Programming Volume 24, Issues 1-2. (Valda delar.)
Ytterligare material kan tillkomma.