Wortstellungsrestriktionen für Zeichenketten generierende Hypergraphgrammatiken

Student:Martin Riedl
Title:Wortstellungsrestriktionen für Zeichenketten generierende Hypergraphgrammatiken
Type:study thesis
Advisors:Fischer, I.; Philippsen, M.
State:submitted on November 17, 2005
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 [3].
ID/LP-Grammatiken versuchen freie Wortstellung und Chomsky-Grammatiken zu integrieren. So ist im Deutschen nicht nur Ich habe einen Hund gekauft. korrekt, sondern auch Einen Hund habe ich gekauft. Diskontinuierliche Phrasenstrukturgrammatiken versuchen freie Wortstellung und diskontinuierliche Konstituenten zu verbinden.

Aufgabenstellung
Ein bereits existierender Earley-Parser für Zeichenketten generierende Hypergraphgrammatiken ist zu pflegen und zu erweitern. Bisher werden nur diskontinuierliche Konstituenten verarbeitet, im Rahmen dieser Studienarbeit soll die freie Wortstellung eingeführt werden. Dazu soll die Literatur gesichtet werden, wie in normale kontextfreie Phrasenstrukturregel Wortstellung integriert wird. Einen Ansatzpunkt bietet hier [2]. Daraus soll ein Vorschlag ausgewählt und auf den existierenden Parser übertragen werden. Dabei ist sowohl der Parsingalgorithmus zu erweitern als auch die Notation von Lexikon und Grammatik anzupassen. Der Parser sollte durch ausgewählte formale und natürlichsprachliche Beispiele getestet werden.

Literatur
1. Annegret Habel Hyperedge Replacement: Grammars and Languages, LNCS 643, 1992
2. Sven Naumann, Hagen Langer, Parsing, Teubner Verlag, 1994
3. Seifert, Sebastian; Fischer, Ingrid: Parsing String Generating Hypergraph Grammars . In: Ehrig, Hartmut; Engels, Gregor; Parisi-Presicce, Francesco (Hrsg.): Graph Transformations (Second Internationsal Conference on Graph Transformations (ICPC 04) Rome, Italy September, 28 - October, 1). Berlin: Springer-Verlag, 2004, S. 352 - 267. (Lecture Notes On Computer Science)

watermark seal