Ein Earley-Parser für Zeichenketten generierende Hypergraphgrammatiken

Student:Sebastian Seifert
Title:Ein Earley-Parser für Zeichenketten generierende Hypergraphgrammatiken
Type:study thesis
Advisors:Fischer, I.; Philippsen, M.
State:submitted on October 4, 2004
Prerequisits:
Topic:

Hintergrund:
Hypergraphen sind Graphen, deren Kanten nicht nur zwei sondern beliebig viele Knoten besuchen. Transformationen auf Hypergraphen durch Grammatiken werden ausführlich in [1] beschrieben. String-Grammatiken, eine Untergruppe der Hypergraphgrammatiken, zeichnen sich dadurch aus, dass das Ergebnis der Ableitung eine Zeichenkette darstellt. Für Zwischenergebnisse einer Ableitung muss diese Bedingung allerdings nicht gelten, dies können normale Hypergraphen sein.
In der Sprachverarbeitung eignen sich String-Grammatiken besonders zur Modellierung diskontinuierlicher Konstituenten wie z.B. in Ich habe einen Hund gekauft, der beißt. Normale kontextfreie Chomsky-Grammatiken können diesen Satz nicht adäquat modellieren, der Zusammenhang zwischen Hund und dem zugehörigen Relativsatz, sowie den finiten und infiniten Verbteilen bereitet Schwierigkeiten. String-Grammatiken umgehen dieses Problem durch die Zwischendarstellung als Hypergraphen [4].
In der Sprachverarbeitung finden Chartparser häufige Verwendung [2,3]. Sie werden nicht nur für kontextfreie Chomsky-Grammatiken eingesetzt, sondern auch für eine Vielzahl anderer Grammatikarten.

Aufgabenstellung:
Ziel dieser Studienarbeit ist es einen Chartparser für Stringgrammatiken zu entwickeln und programmieren. Grundlage soll dabei der Chartparser von Earley sein. Zuerst muss zuerst untersucht werden, ob die in [1] angegebenen Definitionen sich problemlos für eine Übertragung in einen Chartparser eignen. Eine Notation für Lexikon und Grammatik muss entwickelt werden. Der Parser soll mit großen Lexika und Grammatiken für natürliche Sprachen zurechtkommen können. Ebenso soll er Funktionen zur Fehlersuche in Lexika und Grammatiken enthalten. Während der Programmierung ist auf leichte Erweiterbarkeit zu achten (Merkmalsstrukturen, Unifikation, Probabilistische Grammatiken,...). Der Parser ist mit mehreren formalen Grammatiken wie in [1] angegeben sowie einer kleinen Grammatik für das Deutsche zu testen.
Literatur:

  • Annegret Habel Hyperedge Replacement: Grammars and Languages, LNCS 643, 1992
  • Sven Naumann, Hagen Langer, Parsing, Teubner Verlag, 1994
  • James Allen Natural Language Understanding, Benjamin Cummings, 1987, Second Edition, 1994
  • I. Fischer. Modelling Discontinuous Constituents with Hypergraph Grammars. In Proc. International Workshop on Applications of Graph Transformations with Industrial Relevance (AGTIVE'03), Charlottesville, Virginia, USA, 28.September - 1.Oktober, 2003
watermark seal