Algoritmer för syntaxanalys. VT 2008.

Nytt tillfälle 080604. Meddela mig snarast, senast dagen före 10.00, vilka duggor ni vill göra om den 4/6!

Gör kursutvärdering: formulär!

[Kurssida. Nytt utdelat material samlas i Materialmappen.]

Övningsduggor. Lite om Javakoden. NYTT 080515: Dependensparsing. Problemen med ShiftReduce fixade och exemplen korrigerade.

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 Java, 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 antal korta skriftliga prov (duggor), se schemat. (Dessa skall visa att studenten kan redogöra för centrala algoritmer och beskriva deras arbetssätt.)
• Redovisningar (labbrapporter) av tre implementationer av olika typer av algoritmer.

Laborationsuppgifter

Studenter och lärare fastställer tillsammans lämpliga val av uppgifter. Arbetsfördelningen vid samarbete skall klargöras. (Arbetsuppgifterna skall visa att studenten kan implementera denna typ algoritmer, samt testa och dokumentera sådana implementationer.) Titta på litteraturen, tidigare års kurssidor (06, 07) och sök på nätet tidigt på kursen för att komma fram till lämpliga uppgifter.

• Ett konkret förslag (som första labb): Uppgradera den befintliga Recursive-Descent-implementationen i Java (mer här) (från recognizer) till parser (som alltså samlar ihop trädinformationen).
• Uppgradering från recognizer till parser kan även göras för Java-implementationerna av shift-reduce, vänsterhörnsalgoritmen, och chartrecognizern.
• Andra implementationer av algoritmerna är också en bra uppgift, t.ex. att göra mer kompakta implementationer i Java, Prolog eller annat språk.
• Ovanstående kan även göras för andra parsingalgoritmer.

Inlämnade rapporter skall innehålla väldokumenterad kod. Om Java används, skall koden följa gängse konventioner och dess dokumentation skall bygga på Javadoc (se på utdelade exempel!). 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 tillåter alltså en hög grad av individuell anpassning. Betyg sätts utifrån de skriftliga provens utfall och 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.

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.)