Parsing: Eine Einführung in Die Maschinelle Analyse Natürlicher Sprache

ISBN-13: 9783519021391 / Niemiecki / Miękka / 1994 / 305 str.

Svenglish Naumann; Fritz Hohagenglish; Sven Naumann

Opis

Als wir Ende der 80er Jahre zum erstenmal Lehrveranstaltungen vorbereiteten, die einen Uberblick uber die aus Sicht der Computerlinguistik wichtigsten Parsin galgorithmen geben sollten, mussten wir feststellen, dass zwar einerseits die Zahl der Aufsatze, die sich direkt oder indirekt mit Fragen des Parsing beschaftigen, standig wachst und schon fast nicht mehr uberschaubar ist, es anderseits aber kaum Lehrbucher gibt, die sich als Grundlage fur einfuhrende Veranstaltungen eignen. Naturlich gibt es ganze Reihe von Buchern, die algorithmische Verfahren der Syn taxanalyse unter dem Gesichtspunkt der Entwicklung von Compilern (fur Program miersprachen) diskutieren. Einige fundamentale Unterschiede zwischen naturlichen und formalen Sprachen und den Anforderungen an Parser, die als Teil eines Compi lers oder eines naturlichsprachlichen Systems konzipiert werden, lassen diese Bucher aus Sicht der Computerlinguistik nur eingeschrankt geeignet erscheinen. Aus die sem Grund begannen wir, ein Skript zu schreiben, aus dem sich im Verlauf mehrerer Jahre dieses Buch entwickelte. In dieser Zeit ist es durch viele Hande gegangen: Fur viele wertvolle Anregungen mochten wir besonders P. Barg, F. Guenthner, R. Posner, LRenz und J. Schrepp danken. Ohne die Geduld und die Sorgfalt von S. Bauer, J. Falkenberg, B. Grote, H. Kranzdorf, B. Krier-Brandt und C. Schulz waren viele sach liche und orthographische Fehler unentdeckt geblieben. Alle die in diesem Buch abgedruckten Programme und weitere, die aus Platzgrunden nicht aufgenommen werden konnten, sind uber den ftp-Server der Universitat Trier erhaltlich (Adresse: ftp. uni-trier. de / User-Name: anonymous

Spis treści

I Grundlagen.- 1 Was ist Parsing?.- 1.1 Parsing und Compilerbau.- 1.2 Parsing und Kognitive Psychologie.- 1.3 Parsing in der Computerlinguistik.- 1.3.1 Die Rolle von Parsern in natürlichsprachlichen Systemen.- 1.3.2 Parsing natürlicher Sprache.- 1.3.3 Grammatikformalismen.- 2 Begriffe & Repräsentationen.- 2.1 Einige grundlegende Begriffe.- 2.2 Zur Klassifikation von Parsingalgorithmen.- 2.2.1 Verarbeitungsrichtung.- 2.2.2 Analyserichtung.- 2.2.3 Suchstrategien.- 2.3 Komplexität und Effizienz.- 2.3.1 Zur Bewertung von empirischen Tests von Parsingsystemen.- 2.4 Repräsentation des linguistischen Wissens.- 2.5 Die Beschreibung von Algorithmen und Prozeduren.- 2.5.1 Der Beschreibungskopf.- 2.5.2 Der Spezifikationsteil.- 2.5.3 Der Operationsteil.- II Elementare Analysealgorithmen.- 3 Top-down-Parsing.- 3.1 Grundzüge.- 3.2 Kontrollstrukturen.- 3.2.1 Depth-first-Parsing mit Backtracking.- 3.2.2 Breadth-first-Parsing ohne Backtracking.- 3.3 Grenzen des Top-down-Parsings.- 3.4 Implementierung.- 3.4.1 Lisp.- 3.4.2 Prolog.- 4 Bottom-up-Parsing.- 4.1 Grundzüge.- 4.2 Ein deterministischer Shift-reduce-Recognizer.- 4.3 Ein Shift-reduce-Recognizer mit Backtracking.- 4.3.1 Daten und Prozeduren.- 4.3.2 Backtracking.- 4.4 Vom Recognizer zum Parser.- 4.5 Ein Shift-reduce-Parser in Prolog.- 4.5.1 Die Repräsentation der Stacks und Regeln.- 4.5.2 Programmstruktur.- 4.5.3 Das Programm im Überblick.- 4.6 Ein breadth-first arbeitender Shift-reduce-Recognizer.- 4.7 Ein Shift-reduce-Recognizer in Lisp.- 5 Left-corner-Parsing.- 5.1 Grundzüge.- 5.2 Ein Left-corner-Erkennungsalgorithmus.- 5.3 Ein Left-corner-Parsingalgorithmus.- 5.4 Left-corner-Parsing mit Look-ahead.- 5.5 Left-corner-Parsing in Lisp.- 5.5.1 Der Recognizer.- 5.5.2 Der Parser.- 5.6 Das BUP-System.- 5.6.1 Das Kernprogramm als Recognizer.- 5.6.2 Optimierung: Die LINK-Relation.- III Chart-Parsing.- 6 Bottom-up-Chart-Parser.- 6.1 Ein genereller Bottom-up-Chart-Parser.- 6.2 Der Cocke-Kasami-Younger-Algorithmus.- 6.2.1 Berechnung einer einfachen Analysematrix.- 6.2.2 Berechnung einer komplexen Analysematrix.- 6.2.3 Zeit- und Speicherbedarf des Cocke-Kasami-Younger-Algorithmus.- 6.3 Implementierung der Algorithmen.- 6.3.1 Prolog-Implementierung des generellen Bottom-up-Chart-Parsers.- 6.3.2 Der Cocke-Kasami-Younger-Algorithmus.- 7 Der Earley-Algorithmus.- 7.1 Unterschiede zwischen dem CKY- und dem Earley-Algorithmus.- 7.2 Darstellung des Erkennungsalgorithmus.- 7.2.1 Version 1: Berechnung der Chart durch Vorwärtsverkettung.- 7.2.2 Version 2: Zwischenspeicherung neuer Kanten.- 7.3 Erweiterung des Algorithmus.- 7.3.1 Tilgungs- und Kettenregeln.- 7.3.2 Look-ahead.- 7.4 Die Generierung von Strukturbeschreibungen.- 7.4.1 Explizite Repräsentation.- 7.4.2 Implizite Repräsentation.- 7.5 Implementierung der Algorithmen.- 7.5.1 Prolog.- 7.5.2 Lisp.- 8 Insel-Parsing.- 8.1 Motivation für Insel-Parsing.- 8.2 Notwendige Modifikationen des Earley-Algorithmus.- 8.2.1 Datenstrukturen und Operationen.- 8.2.2 Berechnung der Chart durch Vorwärtsverkettung.- 8.2.3 Zwischenspeicherung der neu generierten Kanten.- 8.3 Implementierung.- 8.3.1 Kantenselektoren.- 8.3.2 Identifikation der Inseln im Satz.- 8.3.3 Die Hauptfunktionen.- 9 ID/LP-Syntaxen.- 9.1 Motivation für den ID/LP-Formalismus.- 9.2 Parsen mit ID/LP-Syntaxen.- 9.2.1 Indirektes Parsen.- 9.2.2 Direktes Parsen.- 9.3 Implementierung.- 9.3.1 Lisp.- IV Deterministisches Parsen.- 10 LR-Parsing.- 10.1 LR-Syntaxen.- 10.2 LR-Parser.- 10.3 Ein Algorithmus zur Generierung kanonischer LR(1)-Tabellen.- 10.4 Effiziente Repräsentation von LR-Parsingtabellen.- 10.5 Implementierung.- 10.5.1 Lisp.- 10.5.2 Prolog.- 11 Der Tomita-Algorithmus.- 11.1 LR-Parsing beliebiger kontextfreier Syntaxen.- 11.1.1 Stack-Listen.- 11.1.2 Baum-strukturierter Stack.- 11.1.3 Graph-strukturierter Stack.- 11.1.4 Effiziente Strukturverwaltung.- 11.2 Der Algorithmus.- 11.2.1 Der Erkennungsalgorithmus.- 11.2.2 Der Parsingalgorithmus.- 11.3 Komplexität.- 11.4 Implementierung.- V Unifikationsbasierte Grammatikformalismen.- 12 Definite Clause Grammatiken.- 12.1 Syntaktische Regeln als logische Ausdrücke.- 12.2 Differenzlisten.- 12.3 Vom Recognizer zum Parser.- 12.4 Nicht-kontextfreie Erweiterungen.- 12.5 Ein earley-basierter Parser für DCGs.- 13 Ein Chart-Parser für unifikationsbasierte Syntaxen.- 13.1 Indirektes Parsen.- 13.2 Direktes Parsen.- 13.2.1 Repräsentation von Regeln und Kategorien.- 13.2.2 Parsen mit merkmalsbasierten Syntaxen.- 13.3 Implementierung.- A Grundbegriffe der Syntaxtheorie.- B Graphentheoretische Begriffe.- C Datenstrukturen.- D Repäsentation von Syntax und Lexikon in LISP.- E Musterlösungen.- Namens- und Sachverzeichnis.

O autorze

Prof. Dr. med. Fritz Hohagen, Jg. 1954, Studium der Humanmedizin in Barcelona, Heidelberg und Mannheim. 1984 Staatsexamen und Promotion, 1990 Anerkennung als Arzt für Neurologie und Psychiatrie, 1990-95 Oberarzt an der Psychiatrischen Universitätsklinik Freiburg, 1992 Zusatztitel für Psychotherapie, 1995 Habilitation für das Fach Psychiatrie über 'Untersuchung zur Diagnostik, Prävalenz und Behandlung von Insomnien', 1995-99 Leitender Oberarzt der Abteilung Psychiatrie und Psychotherapie am Universitätsklinikum Freiburg, seit 1999 Ordinarius für Psychiatrie und Direktor für Psychiatrie und Psychotherapie der Universität zu Lübeck. Mitglied in zahlreichen nationalen und internationalen Fachgesellschaften, Gutachter für verschiedene wissenschaftliche Zeitschriften. Seit 2005 Präsident der Deutschen Gesellschaft für Psychiatrie, Psychotherapie und Nervenheilkunde (DGPPN).