Parsing Parsing

Hans Leiß


Vorlesung, Di 8-10, Oettingenstr.67 Raum 1.31

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 die Verwendung von Metaregeln zur Angabe einer größeren Grammatik behandelt werden.

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 ,,Satzgrammatik'' sollten diese Vorlesung besuchen, da die hier erklärten Techniken im Hauptseminar benutzt werden.

Organisatorisches

Programme

werden (voraussichtlich) über die Seite des Seminars ,,Satzgrammatik'' zugänglich gemacht. Die Dokumentation steht unter

Tokenizer, Lemmatizer, Tabellenparser:

Ich hoffe, gelegentlich einen Beamer zum Demonstrieren mitbringen zu können.

Vorlesungsfolien

Da es Schwierigkeiten mit der Anzahl der LaTeX-Boxen beim Darstellen der Bäume gibt, muß ich die Folien der Vorlesung in Blöcke aufteilen:

  1. Grammatiken, Top-Down- und Bottom-Up-Analyse (S.1-40)
  2. Leftcorner-Parser
  3. Headcorner-Parser, Löschbare Kategorien
  4. Ketten- und Linke-Ecken-Relation
  5. Regelvoraussage, Tabellenverfahren (CYK und Earley) (S.77-85)
  6. Verallgemeinerte Earley- und Leftcorner-Analyse (S.86-90)
  7. Prolog-Implementierung der verallgemeinerten Tabellenparser, Beispielanalysen (S.91-114)
  8. Top-Down-Parser für unzusammenhängende Phrasen (S.114-120)

Inhalt der einzelnen Vorlesungen: (Programme z.T. ausführlicher in der Programmdokumentation, größere nur dort)

27.10.03: Vorläufiger Plan
27.10.03 (S. 2-17): Lexikalische Analyse, Grammatiken, Syntaktische Struktur
04.11.03 (S. 18-24): Nicht-deterministischer Top-Down-Erkenner und Parser
11.11.03 (S. 24-29): Implementierung eines Top-Down-Parsers für DCGs in Prolog
cfg.grm, dcg.grm, top-down.pl, top-down-dcg.pl
18.11.03 (S. 30-36) Bottom-Up-Erkenner und Parser
sr.nd.pl, sr.pl
25.11.03 (S. 41-50) Left-Corner-Erkenner und Parser
cfg.lc.grm, leftcorner.pl, leftcorner.shieber.pl
02.12.03 (S. 51-61) Head-Corner Parser; Grammatikübersetzung: Erreichbarkeitsrelationen
09.12.03 (S. 62-68) Berechnung der Kettenrelation
16.12.03 (S. 69-74) Berechnung der Linke-Ecken-Relation
23.12.03 (S. 75-76) Voraussage brauchbarer Regeln (LC)
13.01.04 (S. 77-80) Tabellenverfahren: Erkenner von Cocke,Younger,Kasami
20.01.04 (S. 81-85) Tabellenverfahren: Erkenner von Earley
earley-doerre.pl
03.02.04 (S. 86-90) Tabellenverfahren: Verallgemeinerte Earley- und Leftcorner-Parser
09.02.04 (S. 91-114) Prolog-Implementierung der verallgemeinerten Parser
09.02.04 (S. 114-120) Top-Down-Parser für unzusammenhängende Phrasen

Fragen

Außerhalb der Veranstaltungszeiten können Sie mir eine Nachricht schicken an

leiss@cis.uni-muenchen.de

oder in meine Mentorenstunde kommen, jeweils dienstags, 10-11, Raum B 107, Oettingenstr.67.

File translated from TEX by TTH, version 2.54.
On 9 Feb 2004, 18:22.