Syntaxanalysealgorithmen (Parsing)
Hans Leiß
Vorlesung Mo 12-14, Oettingenstr.67, Raum U 133
Inhalt und Ziel der Veranstaltung
Es werden zuerst die klassischen Verfahren zur Syntaxanalyse mit
kontextfreien Grammatiken behandelt: Top-Down-Analyse,
Bottom-Up-Analyse, Left-Corner-Analyse und Tabellengesteuerte Analyse.
Dann wird besprochen, wie man solche allgemeinen Verfahren zu einem
effizienteren Parser für eine bestimmte Grammatik spezialisiert, indem
man automatisch Eigenschaften der Grammatik berechnet und im Parser
ausnutzt.
Schließlich sollen Varianten dieser Verfahren für Grammatiken mit
Merkmalen (DCGs) und Kopfgrammatiken oder mehrfach kontextfreie Grammatiken
behandelt werden, die auch unzusammenhängende Konstituenten erfassen.
Literatur:
F.Pereira, S.Shieber: Prolog and Natural-Language Analysis.
CSLI Lecture Notes, 1987
S.Naumann, H.Langer: Parsing. B.G.Teubner, 1994.
K.John Gough: Syntax Analysis and Software Tools.
Addison-Wesley Publishing Company, 1988, Reading Mass.
K.Sikkel: Parsing Schemata. Springer, 1997.
S.Sippu, E.Soisalon-Soininen: Parsing Theory. Vol.I: Languages and
Parsing. Springer 1988
P.M.Nugues: An Introduction to Language Processing with Perl
and Prolog: An Outline of Theories, Implementation, and Application with
Special Consideration of English, French, and German. Springer, 2006.
Voraussetzungen:
Programmierkenntnisse in Prolog, Definite Clause Grammars.
Programme
Die Programme und Beispiele sind in einem Verzeichnis Programme/ vepackt zu
Vorlesungsfolien
Als Grundlage dienen die Folien der Vorlesung vom WS 2008/09
parsingfolien.pdf.
Gelegentlich werden die korrigiert oder erweitert.
Neue
Version vom Jan 19, 2012
.
Aufgaben
- Aufgabe
1 (Satzendeerkenner, Tokenisierer)
-
Aufgabenblatt
2 (Top-Down-Parser)
-
Aufgabenblatt
3 (Leftcorner-Parser)
-
Aufgabenblatt
4 (CYK, Baumextraktion)
-
Aufgabenblatt
5 (Earley-Erkenner/Parser)
-
Aufgabenblatt
6 (Grammatikübersetzung)
-
Aufgabenblatt
7 (Verallgemeinerter Leftcorner-Parser)
Fragen
Außerhalb der Veranstaltungszeiten können Sie mir eine Nachricht
schicken oder in meine Mentorenstunde kommen, jeweils mittwochs 13-14 Uhr,
Raum B 107, Oettingenstr.67.
File translated from
TEX
by
TTH,
version 3.67.
On 19 Jan 2012, 11:46.