Parsing und Recognizing des Französischen mit Backtracking

Inhaltsverzeichnis

1. Einleitung

2. Definitionen
2.1. Grammatik und Syntax
2.2. Kontextfreie Grammatik
2.3. Parsing

3. Forschungsstand

4. Parsingverfahren
4.1. Top-down
4.2. Bottom-up
4.3. Suchstrategien beim Parsing
4.4. Mischformen

5. Backtracking

6. Das Verfahren eines einfachen Backtrack-Recognizers anhand eines französischen Beispielsatzes
6.1. Methodik
6.2. Verfahren und Ergebnisse
6.3. Diskussion

7. Fazit und Ausblick

Literaturverzeichnis

1. Einleitung

Die Computerlinguistik (CL), ungefähr so alt wie der Computer selbst (vgl. Dietrich/Klein 1974: 10), beschäftigt sich mit der maschinellen Verarbeitung natürlicher, also menschlicher, Sprache. Es werden Modelle für Programme entwickelt, die natürlichsprachliche Äußerungen verstehen und selbst produzieren können. Damit liegt die CL an der Schnittstelle zwischen Lin­guistik und Informatik (vgl. Carstensen et al. 2010: 1; Rolshoven/Seelbach 1991: 1) und beide Disziplinen ergänzen und beeinflussen sich gegenseitig (vgl. Schmitz 1986: vii).

Ein Teilbereich der CL widmet sich der automatischen Erkennung grammatischer Strukturen und Relationen in mündlichen wie schriftlichen Äußerungen, dem Parsing. Die analysierte Struktur kann entweder in einer Klammer- oder Baumstruktur ausgegeben werden. Die vorlie­gende Arbeit hat einen syntaktischen Fokus. Zur Analyse der syntaktischen Struktur von Ein­gabeketten gibt es die Richtungen top-down und bottom-up, wovon erstere in dieser Arbeit aus­führlicher behandelt wird. Neben Parsern gibt es Recognizer, die lediglich erkennen, ob ein Satz grammatisch ist oder nicht (vgl. Wehrli 1997: 57).

Parser und Recognizer können Backtracking durchführen. Dieses Verfahren hilft dabei, Ambi­guitäten aufzulösen und wird angewendet, wenn es mehrere Regeln in der Grammatik zur Ex­pansion eines Symbols gibt. Die vorliegende Arbeit widmet sich der Fragestellung, inwiefern ein einfacher Backtrack-Recognizer eine effiziente Möglichkeit darstellt, französischspra­chige Eingabeketten zu erkennen. Dabei soll die Hypothese überprüft werden, dass das vor­gestellte Verfahren eines Backtrack-Recognizers zwar einfach, aber ineffizient ist. Der Fokus liegt auf dem Französischen, da die Parsingforschung im frankophonen Raum nicht so extensiv betrieben wird wie im anglophonen. Ziel der Arbeit ist es, das Vorgehen eines einfachen Back- track-Recognizers darzustellen und zu erklären. Es interessiert, wie dieser verfährt, wenn es mehrere Möglichkeiten zur Analyse der syntaktischen Struktur einer Eingabekette gibt. In die­sem Zuge soll die Frage nach der Effizienz des Verfahrens geklärt werden.

Im ersten Schritt werden, um eine Grundlage zu liefern, die zentralen Begriffe, Grammatik und Syntax (2.1.), kontextfreie Grammatik (2.2.) und Parsing (2.3.), definiert. Dem folgt ein Über­blick über den Forschungsstand zum Parsing und im Speziellen zum Parsing des Französischen, um die Arbeit besser in den Forschungskontext einordnen zu können (3.). Daraufhin werden die Analyserichtungen top-down (4.1.) und bottom-up (4.2.) kurz erklärt und die Suchstrategien depth-first- und breadth-first-search (4.3.) sowie Mischformen des Parsings (4.4.) erläutert. Die Strategie des Backtrackings sowie der Aufbau eines einfachen Backtrack-Recognizers werden als nächstes vorgestellt (5.). Danach wird eine kontextfreie Grammatik für ein Fragment des Französischen gegeben (6.1.), die die Basis für die Darstellung und Erklärung des Vorgehens des Backtrack-Recognizers bildet (6.2.). Anschließend werden die Analyseergebnisse im Hin­blick auf die Fragestellung diskutiert und die Grenzen der durchgeführten Analyse aufgezeigt (6.3.). Zum Schluss erfolgt eine Zusammenfassung der Ergebnisse und die Klärung, ob die Hy­pothese verifiziert oder falsifiziert werden kann, sowie ein Ausblick (7.).

2. Definitionen

Um eine Grundlage für die Analyse zu geben, wird zuerst definiert, worum es sich bei einer Grammatik und einer Syntax, einer kontextfreien Grammatik und beim Parsing handelt.

2.1. Grammatik und Syntax

Feststellbar ist, dass es unmöglich ist, alle Sätze einer Sprache, die gebildet werden können, aufzulisten. Menschen sind jedoch grundsätzlich in der Lage, zu erkennen, ob ein Satz zu der Sprache oder den Sprachen, die sie beherrschen, gehört oder nicht. Denn in jeder Sprache gibt es eine endliche Anzahl von Kriterien, die ein Satz erfüllen muss und derer SprecherInnen der jeweiligen Sprache sich implizit bewusst sind. Diese Kriterien möchten LinguistInnen identifi­zieren und Grammatiken für Sprachen formulieren (vgl. Roeck 1983: 4). Sie beinhalten in systematischer Form phonologische, morphologische, syntaktische, semantische und pragma­tische Informationen über eine natürliche Sprache (vgl. Naumann/Langer 1994: 3). Diet- rich/Klein (1974: 12) definieren eine Grammatik als „[e]ine zusammenhängende Menge von Regeln über einen sprachlichen Datenbereich“. Ebenso verweist Roeck (1983: 4) auf das zent­rale Charakteristikum der endlichen Anzahl von Regeln, die eine Sprache beschreiben. Sie ver­fügen über eine starke generative Kapazität, sagen also voraus, welche Struktur den Sätzen der Sprache, die sie beschreiben, zugrunde liegt. Eine Grammatik G generiert eine Sprache L(G) und die Art von G bestimmt die Art von L(G) (vgl. Roeck 1983: 5). Die Menge aller von einer Grammatik erzeugten Worte ergibt eine formale Sprache. Grammatiken arbeiten binär: Entwe­der ist eine Zeichenkette generierbar und gehört zur Sprache, die von der Grammatik erzeugt wird, oder nicht (vgl. Klabunde 2010: 67).

Regeln erhalten ihre Bedeutung nur im Rahmen der jeweiligen Gesamtgrammatik (vgl. Schmitz 1986: 43), weil unterschiedlichen Sprachen unterschiedliche Grammatiken zugrunde liegen. Regeln bestehen aus einer linken und einer rechten Seite. Jede Seite hat Ketten, die aus (Nicht- )Terminalsymbolen aufgebaut sind. Terminalsymbole sind die Wörter einer Eingabekette.

Nichtterminalsymbole sind beispielsweise NP für Nominalphrase und VP für Verbalphrase. Symbole wie N (Nomen), V (Verb) und DET (Determinierer) sind ebenso Nichtterminalsym­bole, werden aber auch Präterminalsymbole genannt, weil sie einzig zu Terminalsymbolen ex­pandieren. Auf der linken Regelseite muss mindestens ein Nichtterminalsymbol vorkommen. Eine Regel ist auf eine Eingabekette anwendbar, wenn ein Teil von ihr mit der linken Regelseite identisch ist (vgl. Naumann/Langer 1994: 16). Regeln sind nach dem Schema a ß aufgebaut (sprich: a wird durch ß ersetzt) (vgl. Klabunde 2010: 68). Sie können auf verschiedene Weisen miteinander verknüpft sein, weshalb eine Grammatik umso komplizierter und unüberschauba­rer wird, je mehr Regeln sie enthält (vgl. Dietrich/Klein 1974: 14).

Da der Fokus dieser Arbeit auf syntaktischem Parsing liegt, wird nun der Begriff der Syntax definiert. Sie ist die Lehre von den Relationen zwischen den Satzelementen, also die Lehre vom Satzbau einer Sprache (vgl. Stein 2014: 43). Sätze werden in Elemente zerlegt, in Klassen zu­sammengefasst und in ihrer Funktion beschrieben, indem ihr Verhältnis zu anderen Elementen analysiert wird (vgl. Stein 2014: 46). Eine Grammatik ist insofern die Gesamtheit der Regeln einer Sprache, die es ermöglichen, wohlgeformte (grammatische) von nicht wohlgeformten (ungrammatischen) Sätzen zu unterscheiden (vgl. Stein 2014: 43). Wortarten wie Verb, Nomen, Adjektiv usw. werden auch als Kategorien bezeichnet (vgl. Stein 2014: 44) und die nach Regeln gebildeten Gruppen von Kategorien, die die Struktur eines Satzes bilden, werden Konstituenten genannt. Zusammengehörende Elemente heißen Phrasen, deren Namen sich an einem ihrer Ele­mente orientieren (Nominalphrasen, Verbalphrasen usw.) (vgl. Stein 2014: 50).

Charakteristisch für die französische Syntax ist die relative Unbeweglichkeit der Satzele­mente, beispielsweise im Vergleich zum Deutschen: Subjekt, direktes und indirektes Objekt haben im Französischen bestimmte Positionen vor und nach dem Verb. Vertauschen ist nur in engen Grenzen möglich. Weiterhin können manche attributiven Adjektive vor oder nach dem Nomen stehen, Adverbien können unterschiedliche Positionen einnehmen. Des Weiteren kommt die Inversion von Subjekt und Verb nur als fakultative Variante in speziellen Registern vor, etwa in der administrativen Fachsprache, oder obligatorisch nach manchen satzeinleiten­den Adverbien, zum Beispiel peut-ètre (vgl. Stein 2014: 63).

2.2. Kontextfreie Grammatik

Der Grammatiktyp, der für das Parsing zentral ist und die Basis für syntaktische Analysen bil­det, ist die kontextfreie Grammatik (KFG), die der Typ-2-Grammatik in der Chomsky-Hierar­chie entspricht (vgl. Chomsky 1956).

Klabunde (2010: 68), Langer (2010: 283) und Roark (2001: 251) beschreiben den Aufbau einer KFG G = (E, O, R, S ). Sie besteht aus einem Alphabet E mit Terminal- und einem Alphabet O mit Nichtterminalsymbolen. Die Mengen der Alphabete sind disjunkt, sie besitzen also keine gemeinsamen Elemente. Weiterhin bestehen KFGs aus einer endlichen Regelmenge R, damit aus Terminalsymbolen bestehende Zeichenketten generiert werden können. Die Regeln haben die Form A a, wobei A für ein Nichtterminal- und a für eine Kette von (Nicht-)Terminal- symbolen steht. Das Startsymbol S ist ein Element des nichtterminalen Vokabulars. Es bildet die Wurzel der Baumstrukturen, die auf Grundlage der KFG generiert werden können, und be­zeichnet die syntaktische Kategorie ,Satz‘ (vgl. Langer 2010: 283).

Kennzeichen von KFGs sind, dass die linke Regelseite aus einem einzelnen (Nicht-)Terminal- symbol besteht (vgl. Naumann/Langer 1994: 17) und die rechte Regelseite aus einer beliebigen Folge von (Nicht-)Terminalsymbolen bestehen kann. Für ein Wort existieren nicht selten meh­rere Ableitungen (vgl. Klabunde 2010: 80). Mit KFGs können Grundelemente der syntakti­schen Struktur von natürlichsprachlichen Ausdrücken beschrieben werden, da sie einfach zu entwickeln und zu modifizieren sind und die Frage, ob ein Satz zu der von einer Grammatik beschriebenen Sprache gehört, entscheidbar machen (vgl. Naumann/Langer 1994: 17). Dies kann zum Beispiel durch die Segmentierung komplexer Ausdrücke in Teilausdrücke und durch die Bildung von Kategorien (NP, VP, usw.) geschehen (vgl. Langer 2010: 286). Zwar gelten KFGs als Basisinstrument für syntaktische Analysen, werden heutzutage jedoch nur noch selten in ihrer Reinform verwendet (vgl. Langer 2010: 282).

Seit den 1960er Jahren werden auch probabilistische KFGs entwickelt. Hier erhält jede Regel eine numerische Bewertung, die Expansionswahrscheinlichkeit, deren Wert zwischen null und eins liegt (vgl. Langer 2010: 300). Werden die Wahrscheinlichkeiten aller Regeln miteinander multipliziert, ergibt sich die Gesamtwahrscheinlichkeit für die jeweilige Ableitungsmöglichkeit einer Eingabekette (vgl. Roark 2001: 252). Probabilistische KFGs dienen vordergründig der korrekten Disambiguierung von Sätzen. Ein Satz ist ambig (mehrdeutig), wenn er mehrere Les­arten aufweist. Werden Expansionswahrscheinlichkeiten festgelegt, lässt sich eine Lesart be­vorzugen (vgl. Langer 2010: 301 f.), was zur Effizienz eines Parsingalgorithmus in einem sol­chen Fall beiträgt.

2.3. Parsing

Der Begriff Parsing leitet sich aus dem lateinischen partes orationis ab (dt. Teil der Rede, also der Wortarten). Beim Parsing finden Analyseprozesse statt, die die grammatische Struktur einer mündlichen oder schriftlichen Äußerung wiedergeben (vgl. Langer 2010: 303). Stein (2014: 195 f.) definiert Parsing als „automatische Erkennung syntaktischer Strukturen und grammati­scher Relationen“ und die in der übrigen Forschungsliteratur gefundenen Definitionen stimmen mit dem sinngemäß überein (z. B. Naumann/Langer 1994: 4; Schmitz 1986: 42; Wehrli 1997: 9). Wehrli (ebd.) fügt noch hinzu, dass Strukturbeschreibungen im nächsten Schritt bestimmte semantische und pragmatische Interpretationen erlauben. Auch gehören zu den Aufgaben des Parsings die Disambiguierung, die Identifikation der Eingabekette, etwa wenn Sprachsignale mehrere Interpretationen zulassen und erst eine syntaktische Analyse zur Reduktion der Mög­lichkeiten nötig ist, sowie die Korrektur der Eingabe (vgl. Naumann/Langer 1994: 13 f.). Parser sind Automaten, die in der Lage sind, eine Eingabekette in eine andere Kette von Symbolen wie Baum- oder Klammerstrukturen zu konvertieren (vgl. Wehrli 1997: 57). Eine andere Art von Automaten sind Recognizer (engl. to recognize: erkennen). Sie erkennen lediglich, ob ein Satz zu einer Sprache gehört, die mit einer Grammatik G beschrieben wird (vgl. ebd.).

Nicht nur natürliche Sprachen können mit Hilfe von Parsing analysiert werden, sondern auch künstliche, wie Programmiersprachen, wenn beispielsweise eine programmiersprachliche Stufe in eine andere transformiert werden soll (vgl. Hausser 2000: 179). Die Herausforderungen die­ser beiden Arten von Parsing sind unterschiedlich, was an den Eigenschaften natürlicher Spra­chen liegt: Sie weisen eine höhere syntaktische Komplexität und größere Strukturvielfalt, zahl­reiche Ambiguitäten, Vagheit und Unregelmäßigkeiten auf (vgl. Naumann/Langer 1994: 14). Parser müssen mit dieser Komplexität natürlicher Sprache umgehen können. Es ist jedoch frag­lich, ob maschinelle Systeme dazu jemals in der Lage sein werden. In der Alltagssprache etwa treten sehr häufig Ambiguitäten auf und in der Forschungsliteratur herrscht der Konsens vor, dass sie ein Hauptproblem der CL darstellen (vgl. Dietrich/Klein 1974: 22; Langer 2010: 307). Nicht immer schaffen es Parser, Ambiguitäten zu erkennen und zu lösen. Zentrale Fragen sind, unter welchen Bedingungen eine adäquate syntaktische Analyse natürlichsprachlicher Einhei­ten automatisch erfolgen kann und bis zu welchem Abstraktionsgrad sprachliche Regelmäßig­keiten durch formale Theorien beschrieben werden können (vgl. Dietrich/Klein 1974: 14). Nur wenn LinguistInnen und InformatikerInnen zusammenarbeiten, könnten derartige Probleme in Zukunft gelöst werden.

Es gibt verschiedene Typen von Parsern: Syntaktische, semantische, phonologische und mor­phologische sowie Textparser, welche Diskursstrukturen analysieren (vgl. Hausser 2000: 179; Naumann/Langer 1994: 4). Syntaxparser analysieren die grammatische Struktur eines eingege­benen Satzes und geben das Ergebnis als Klammer- oder Baumstruktur aus. Voraussetzung ist, dass sie Wortformen erkennen können. Es muss also ein Morphologieparser integriert sein (vgl. Hausser 2000: 179 f.). In einer Baumstruktur stellt jede Expansion eine Regel der KFG dar. Die Enden werden als Blätter bezeichnet und eine Baumstruktur, deren Blätter gänzlich aus Termi­nalsymbolen bestehen, gilt als komplett (vgl. Roark 2001: 251). Ein Parsingalgorithmus inter­pretiert und wendet eine generative Grammatik automatisch an (vgl. Hausser 2000: 180). Als Algorithmus wird ein deterministischer Vorgang bezeichnet, der zur Lösung eines Problems führt (vgl. Klabunde 2010: 67). In 6. wird der Ablauf des Algorithmus eines Recognizers schrittweise beschrieben und erklärt.

3. Forschungsstand

Es ist feststellbar, dass Parsingforschung im frankophonen Raum nicht so extensiv betrieben wird wie im anglophonen. Als englischsprachiges Einführungswerk ins Parsing gilt King (1983). Der darin enthaltene Beitrag von Roeck (1983) klärt grundlegende Terminologien wie Grammatik und KFG, die zum Verständnis des Parsings wichtig sind, und erläutert die Verfah­ren top-down und bottom-up, auf denen alles beim Parsing aufbaut.

Eine deutschsprachige Einführung in die CL liefern Dietrich/Klein (1974). Die Einführung ins Parsing von Naumann/Langer (1994) enthält neben Definitionen der für das Parsing relevanten Begriffe auch Erläuterungen berühmter Algorithmen wie des Earley-Algorithmus. Des Weite­ren publizierten Carstensen et al. (2010) ein deutschsprachiges Handbuch für die CL und Sprachtechnologie mit dem Anspruch, zu einem Standardwerk für Studierende, Wissenschaft­lerInnen und für die industrielle Anwendung zu werden (vgl. Carstensen et al. 2010: iii), was auch gelang (vgl. Carstensen et al. 2010: vii).

Der Sammelband von Rolshoven/Seelbach (1991) enthält Beiträge von computerlinguistisch orientierten RomanistInnen aus Deutschland, Frankreich und Italien über Systeme zur maschi­nellen Analyse und Synthese romanischer Sprachen. Eines der wenigen französischsprachigen Werke, die Parsing behandeln, ist Wehrli (1997). Gardent et al. (1989) präsentieren einen Bot­tom-up-Chart-Parser für Französisch, der auf Grundlage einer kategorialen Unifikationsgram­matik entwickelt wurde. Die erste Grammatik für Französisch, die für die Tree Adjoining Grammar (TAG) geschrieben wurde, stellt Abeillé (1988) vor. TAG ist ein unifikationsbasiertes grammatisches Modell, bei dem das Lexikon der jeweiligen Sprache im Vordergrund steht. In einer TAG gehört zu den Wörtern bereits ein Ast in der Baumstruktur, der mit nur wenigen Regeln, anhängen oder ersetzen, kombiniert wird. Auf Basis dieser TAG, die auf ein Lexikon der 4.000 gängigsten Wörter des Französischen zurückgreift, entwickelten Schabes et al. (1988) eine Parsingstrategie für Französisch, die sich am Earley-Algorithmus orientiert. Abeillé et al. (2003) stellen eine Treebank für das Französische vor, deren Korpus aus 870.000 Worttokens, 37.000 Lemmata und 32.000 Sätzen der Zeitung ,Le Monde‘ besteht. Treebanks bestehen aus Korpora, in denen jeder Satz geparst ist. Sie werden von LinguistInnen verwendet, um Parser zu trainieren und zu bewerten.

Zwar sind Parser für die französische Sprache verfügbar (z. B. Candito et al. 2010a), deren Anwendung erfordert aber tiefere technische Vorkenntnisse. Stein (2014: 196) verweist darauf, dass es Formen der syntaktischen Analyse beispielsweise auch in den Korrekturmodulen von Textverarbeitungsprogrammen gibt. Candito et al. (2010a) konvertieren die Konstituenten- Treebank von Abeillé/Barrier (2004) in eine Dependenz-Treebank. Die AutorInnen (2010a: 1.846) stellen fest, dass sie geeignet ist, um probabilistische Parser zu trainieren. Weiterhin präsentieren Barchan et al. (1986) ein auf der Programmiersprache Prolog basierendes Tool zur Analyse der französischen Grammatik. Roark (2001) stellt einen probabilistischen Top-down­Parser vor und beschreibt seine Anwendungsmöglichkeiten im Bereich der Spracherkennung. Wie die Jahreszahlen der aufgeführten Forschungsliteratur verdeutlichen, gilt dem Parsing schon seit Jahrzehnten das Interesse in der CL. Insgesamt lässt sich sagen, dass sich die aktuel­lere Forschung auf probabilistisches Parsing konzentriert. Für das Französische ist probabilis­tisches Dependenzparsing relevant (z. B. Candito et al. 2010b).

4. Parsingverfahren

Im Folgenden werden die beiden Grundverfahren des Parsings erklärt. Der Standard ist die Links-rechts-Verarbeitung, die an der Reihenfolge orientiert ist, in der in vielen europäischen Sprachen Äußerungen getätigt werden. Die Analyse beginnt mit dem Satzanfang und verfährt Wort für Wort von links nach rechts (inkrementelles Verfahren) (vgl. Langer 2010: 304 f.).

[...]