Algoritmer för syntaxanalys • VT 2006

Lärare och kursansvarig: Mats Dahllöf.

Schema och planering

Dag	tid	lokal	info.
2006-05-02	10-12	3-0012	F1
2006-05-03	10-12	3-0012	F2
2006-05-03	13-15	labCh	L1
2006-05-04	13-14	labCh	L2
2006-05-08	10-12	3-0012	F3
2006-05-08	13-15	labCh	L3
2006-05-11	10-12	3-0012	F4
2006-05-11	13-15	labCh	L4
2006-05-15	10-12	3-0012	F5
2006-05-15	13-15	labCh	L5
2006-05-18	10-12	3-0012	F6
2006-05-18	13-15	labCh	L6
2006-05-22	9-11	9-2029/3-0012	F7 (Schemaändr.)
2006-05-22	13-15	labCh	L7
2006-05-24	10-12	3-0012	F8
2006-05-24	13-15	labCh	L8
2006-05-29	10-12	3-0012	F9 (Studentpresentationer.)
2006-05-29	14-16	labCh	L9 (Schemaändr.!) (Studentpresentationer)
2006-06-01	10-12	labCh	L10
2006-06-01	14-16	3-0012	F10 (DUGGA!)

1. Introduktion, Hellwig: 1, Mellish, et al.: 9. OH.

2. Recursive descent, Hellwig: PT-1. Pereira och Shieber: 6.1-6.3, Mellish, et al.: 10. OH. Material för undersökning av resolutionen (MD).

3-4. Earley/chart, Earley, Hellwig: PT-4, Mellish, et al.: 12, Pereira och Shieber: 6.6. OH. Ant. motsvarande kod.

5-7. Vänsterhörnsparsing, Pereira och Shieber: 6.5. OH Prolog. Uppsala Chart Parser, Sågvall Hein & Starbäck, Dahllöf 1989. Shift-reduce, Hellwig: PT-6 (sofistikerad typ). OH, Ant. Prolog. CKY (Cocke, Kasami och Younger), Hellwig: PT-5. Mellish, et al. 11. OH. Prolog.

7. Shift-reduce parsing Hellwig: PT-6 (sofistikerad typ). OH, Ant. Prolog. CKY (Cocke, Kasami och Younger) (för självstudier) Hellwig: PT-5. Mellish, et al. 11. OH. Prolog.

8. Dependensparsing. Nivre och Nilsson, Nivre och Scholtz. OH. Kod

9-10. Dugga. Uppgiftspresentationer från studenterna.

Innehåll och arbetssätt

Kursplanen säger följande: Kursen ger en introduktion till algoritmer för syntaxanalys och färdighet i att implementera dem. Kursen tar upp viktiga algoritmer för syntaxanalys, t.ex. ”recursive descent” och olika typer av chartparsing. Även klassifikationen av sådana algoritmer behandlas. Vidare tar kursen upp datastrukturer som används för att implementera charts och sådana särdragsstrukturer som är viktiga i många språkteknologiska grammatikformalismer. Undervisningen sker i form av lektioner och laborationer under handledning.

Arbetssätt och examination

Arbetet på kursen och bearbetningen av materialet kommer främst att bestå i att vi implementerar grundläggande och viktiga parsingalgoritmer. Undervisningen kommer främst att utgå från Prolog, då det är Logikprogrammering II som är kursens programmeringsmässiga förkunskapskrav, men studenter som är kunniga i och intresserade av något annat programspråk får gärna använda det.

Kursen examineras genom följande:

Ett mindre skriftligt prov (dugga).
Redovisningar (labbrapporter) av två laborationsuppgifter.
Fördjupningsarbete (muntligen och som uppsats).

Dessa kan labbar och fördjupningsarbete kan göras individuellt eller gruppvis, av max tre personer (så att alla lär sig det det handlar om).

Inlämnade rapporter skall innehålla väldokumenterad kod. Om Prolog används, skall koden och dess dokumentation följa Covingtons instruktioner. Dessutom skall illustrativa körningsexempel ges. Laborationsrapporterna skall vara språkligt korrekta och ha ett typografiskt korrekt och tilltalande utseende. Titta på exempel. LaTeX-användning rekommenderas starkt. De skall inlämnas utskrivna på papper.

Kursens labbuppgifter och fördjupningsarbete tillåter en hög grad av individuell anpassning. Betyg sätts utifrån en helhetsbedömning av de uppgifter som lämnats in. Deras svårighetsgrad och hur väl de utförts kommer att vägas in. Dokumentation är viktigt.

Labbuppgifter:

(1) ”Recursive Descent”
(2) ”Bottom-up”

Material:

Javaprogram för att läsa SUC.

Förslag på fördjupningsuppgifter:

Särdragsstrukturer (och parsing) i annat slag av språk än Prolog (Java, t.ex.). Implementera.
Vänsterhörnsparsing. Implementera.
Dependensparsing (t.ex. utifrån Nivres artiklar). Implementera.
Annan intressant implementation av någon algoritm.
''Fallstudie'': se på hur parsing hanteras i något verkligt språkteknologiskt system.

Kurslitteratur

Dahllöf, M., 1989, “En lexikonorienterad parser för svenska” (M.A. thesis), Göteborg University, Dept of Computational Linguistics. (Det som handlar om UCP, s. 2-9.)

Dahllöf, M., 2005, A Chart Parser in Prolog, föreläsningsanteckningar.

Earley, J. 1970, An efficient context-free parsing algorithm.

Hellwig, P. 2003, Natural Language Parsers, A “Course in Cooking”, Universität Heidelberg.

Grune D. och Ceriel J.H. Jacobs, 1990, Parsing Techniques - A Practical Guide.

Mellish, C., P. Whitelock och G. Ritchie, 1994, Techniques in Natural Language Processing. (PostScript) (länk), Department of AI, University of Edinburgh. [Kapitel 9-13. Tidigare kapitel bra repetition.]

Nivre, J. och Nilsson, J. (2003) Three Algorithms for Deterministic Dependency Parsing (finns här).

Nivre, J. och Scholz, M. (2004) Deterministic Dependency Parsing of English Text (finns här).

Pereira, F. och S. M. Shieber, 2002, Prolog and Natural-Language Analysis (Millenial reissue), Microtome Publishing. [Kapitel 6. Tidigare kapitel bra repetition.]

Striegnitz, K., m.fl. (2003) Algorithms for Computational Linguistics.

Sågvall Hein, Anna & Starbäck, Per: A Test Version of the Grammar Checker for Swedish, Deliverable 6.5.1. (Det som handlar om UCP, s. 4-9.)

Ytterligare material kan tillkomma.

Länkar

GSLT course: Parsing methods (Peter Ljunglöf, 2005).