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

  1. Aufgabe 1 (Satzendeerkenner, Tokenisierer)
  2. Aufgabenblatt 2 (Top-Down-Parser)
  3. Aufgabenblatt 3 (Leftcorner-Parser)
  4. Aufgabenblatt 4 (CYK, Baumextraktion)
  5. Aufgabenblatt 5 (Earley-Erkenner/Parser)
  6. Aufgabenblatt 6 (Grammatikübersetzung)
  7. 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.