Computerlinguistik

Hauptpraktikum Computerlinguistik B.1

Wintersemester 2002/2003 Bernhard Schroder ¨ 24. April 2003

Inhaltsverzeichnis

1 Organisatorisches 2 Parser 2.1 DCGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Parsingstrategien . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Ein weiterer Top-Down-Parser . . . . . . . . . . . . . . . . . . 2.4 Shift-Reduce-Parser . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Shift-Reduce-Algorithmus . . . . . . . . . . . . . . . . 2.4.2 Erzeugung von Parse-B¨umen beim Shift-Reduce-Parser a 2.5 Left-Corner-Parser . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Algorithmus des Left-Corner-Parsing . . . . . . . . . . 2.6 Chart-Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Motivation eines Chart . . . . . . . . . . . . . . . . . . 2.6.2 Vollst¨ndigkeit eines Teilchart . . . . . . . . . . . . . . a 2.6.3 Vollst¨ndigkeitsmarkierung und Kategorienargumente . a 3 4 4 6 7 10 10 12 14 14 16 16 19 20

3 Merkmalstrukturen 24 3.1 Darstellung von Merkmalstrukturen in Prolog . . . . . . . . . 25 3.2 Unifikation von Merkmalstrukturen in Prolog . . . . . . . . . 25 4 ML und Prolog 26

1

A Projektvorschl¨ge a A.1 Projekt Bottom-Up-Chart-Parser (bereits vergeben) . . . . . . A.2 Projekt Shift-Reduce-Chart-Parser (bereits vergeben) . . . . . A.3 Projekt BUP-Pr¨prozessor (bereits vergeben) . . . . . . . . . a A.4 Projekt Grafische Ausgabe des Chart (bereits vergeben) . . . . A.5 Projekt Grafische Ausgabe des Parse-Baums beim Top-DownParsing (bereits vergeben) . . . . . . . . . . . . . . . . . . . . A.6 Projekt Grafische Ausgabe des Parse-Baums beim Shift-ReduceParsing (bereits vergeben) . . . . . . . . . . . . . . . . . . . . A.7 Projekt Grafische Ausgabe des Parse-Baums beim Left-CornerParsing (bereits vergeben) . . . . . . . . . . . . . . . . . . . . A.8 Projekt Pr¨prozessor zur Kompilation einer DCG in einen a Top-Down-Chart-Parser . . . . . . . . . . . . . . . . . . . . . A.9 Projekt Typisierte Merkmalstrukturen . . . . . . . . . . . . . A.10 Parsebaum als Merkmalstruktur . . . . . . . . . . . . . . . . . ¨ A.11 Projekt Ubersetzungssystem . . . . . . . . . . . . . . . . . . . A.12 Projekt FA-System . . . . . . . . . . . . . . . . . . . . . . . . A.13 Projekt Aktiv-Passiv-Wandler . . . . . . . . . . . . . . . . . . A.14 Projekt Linksrekursionschecker . . . . . . . . . . . . . . . . . A.15 Projekt Nullkonstituentenchecker . . . . . . . . . . . . . . . . A.16 Projekt Parser f¨r S¨tze mit morphologischem Tagging . . . . u a A.17 Projekt Treebank (bereits vergeben) . . . . . . . . . . . . . . . B Beispielprogramme B.1 gram1.pl . . . . . B.2 gram1rek.pl . . . B.3 gram1a.pl . . . . B.4 gram1arek.pl . . B.5 gram1b.pl . . . . B.6 append.pl . . . . B.7 gram2.pl . . . . . B.8 gram3.pl . . . . . B.9 gram4.pl . . . . . B.10 gram5.pl . . . . . B.11 gram5a.pl . . . . B.12 gram7a.pl . . . . B.13 td.pl . . . . . . . B.14 regeln.pl . . . . .

27 28 29 30 31 32 33 34 34 34 35 35 36 36 36 37 37 38 38 38 39 41 42 43 44 45 46 47 48 51 54 57 58

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . 2

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

B.15 B.16 B.17 B.18 B.19 B.20 B.21 B.22 B.23 B.24 B.25 B.26 B.27 B.28 B.29 B.30 B.31 B.32 B.33 B.34 B.35 B.36 B.37

preproctd.pl . . td2.pl . . . . . preproctd2.pl . tdbaum.pl . . . tdbaum2.pl . . tdzaehler.pl . . botupp.pl . . . botupg1.pl . . . botupg2.pl . . . botuppbaum.pl leftc.pl . . . . . leftcg.pl . . . . chart.pl . . . . chartg.pl . . . . chartc.pl . . . . chartcs.pl . . . chartcsg1.pl . . chartcspp.pl . . chartcsg2.pl . . subsumes.pl . . fsunif.pl . . . . saetze.xml . . . treebank.xml .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

58 58 59 59 60 60 62 63 64 66 67 68 69 71 71 73 76 76 77 77 79 80 80 82

C Seminarplan

1

Organisatorisches

Leistungsnachweis Aktive Teilnahme, Hausarbeiten, “Projekt”am Ende des Praktikums (abzugeben vor Beginn des Sommersemesters 2003) Teilnahmenachweis Regelm¨ßige aktive Teilnahme (nicht mehr als zweia mal Fehlen) Materialien Dieses Skript befindet sich unter

http://www.ikp.uni-bonn.de/dt/lehre/materialien/hpclb.1/skript.pdf; Bei-

spielprogramme auf allen Linux-Rechnern im Pavillon unter /CIP_MATERIALIEN/LEHRVERANSTALTER_INDIVIDUELL/bsh/HPCLB.1, die 3