Parsing

Hans Leiß


Vorlesung/Hauptseminar mit Übung, Mo 9-10, Oe 67 Raum 1.39
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, 199?
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.
Voraussetzungen: Programmierkenntnisse in Prolog, Definite Clause Grammars.
Hinweis: Teilnehmer des Hauptseminars ,,Grammatikimplementierung'' sollten diesen Kurs besuchen, da die hier erklärten Techniken dort benutzt werden.

Organisatorisches

Die erste Stunde Mo 9-10 ist zur Besprechung von Übungsaufgaben und Implementierungsfragen vorgesehen. Die Stunden Mo 10-12 sind als Vorlesungsteil mit gelegentlichen Seminarvorträgen geplant.

Programme

Die Programme und Beispiele sind in einem Verzeichnis Programme/ vepackt zu (aktualisiert 16.1.07, Berechnung des LR(0)-Automaten korrigiert)

Vorlesungsfolien

Die Folien der Vorlesung erscheinen fortlaufend hier als parsingfolien.ps oder parsingfolien.pdf. (aktualisiert 16.1.07, LR(0)-Berechnung und Beispiele dazu)

Aufgaben

  1. Aufgabe 1 (Sublexikon, Taggen)
  2. Aufgabe 2 (Tokenmodell, Top-Down-Parsen)
  3. Aufgabe 4 Det.Simulierung des Top-Down-Parsers in Prolog
  4. Aufgabe 5 Erweiterung des Bottom-Up-Parsers auf DCG-Grammatiken
  5. Aufgabe 6+7 Leftcorner-Parsers für DCG-Grammatiken + Differenzlisten/Baumausgabe automatisch
  6. Aufgabe 8 Vom Head-Corner-Erkenner zum Head-Corner-Parser
  7. Aufgabe 9: Programmieren Sie für CFG's die Berechnung der Erreichbarkeitsrelationen und z.B. den Earley-Parser für übersetzte Grammatiken. Versuchen Sie es wenigstens!

Fragen

Außerhalb der Veranstaltungszeiten können Sie mir eine Nachricht schicken oder in meine Mentorenstunde kommen, jeweils dienstags, 10-11, Raum B 107, Oettingenstr.67.

File translated from TEX by TTH, version 3.67.
On 16 Jan 2007, 12:23.