Vorschau Prolog Aufbaukurs SS 2003 Heinrich-Heine-Universität Düsseldorf Christof Rumpf

VorschauVorschauProlog Aufbaukurs SS 2003

Heinrich-Heine-Universität Düsseldorf

Christof Rumpf

22.04.2003 Vorschau Prolog Aufbaukurs 2/46

TokenizerTokenizer

• Ein Tokenizer ist ein Programm, das beliebigen Zeicheninput in eine Liste von Tokens umwandelt.

• Ziel ist die Verarbeitung von Daten, die nicht in Prolog-Syntax vorliegen.

• Quelle der Daten kann die Tastatur oder eine Datei sein.

22.04.2003 Vorschau Prolog Aufbaukurs 3/46

TokensTokens

• Ein Token ist ein Intervall in einer Zeichenfolge, der per Konvention als nicht weiter zerlegbar gilt.

• Z.B. sind die Wörter dieser Präsentation durch Leerzeichen getrennte Tokens.

• Zeichen wie Punkt, Komma und Zeilenwechsel können ebenfalls Trenner sein oder auch selbständige Tokens bilden.

22.04.2003 Vorschau Prolog Aufbaukurs 4/46

AnwendungenAnwendungen

• Natürlichsprachlicher Input– Umwandeln einer Zeichenfolge in eine

Wortliste.

• Compilerbau– Übergabe einer Tokenliste an einen Compiler.

• Datenbanken– Import von Daten aus einer externen

Datenbank.

22.04.2003 Vorschau Prolog Aufbaukurs 5/46

LiteraturLiteratur

• O‘Keefe, Richard A. (1990): The Craft of Prolog. Chap. 10: Writing Tokenizers in Prolog. MIT Press.

22.04.2003 Vorschau Prolog Aufbaukurs 6/46

ParsingParsing

• engl. to parse: „grammatisch zerlegen“

• Ein Parser ist ein Automat, der einer Zeichenkette aufgrund einer Grammatik einen Syntaxbaum zuordnet.

Grammatik Parser SyntaxbaumZeichenkette

In Out

22.04.2003 Vorschau Prolog Aufbaukurs 7/46

ParsingstrategienParsingstrategien

• top-down• bottom-up• left-corner

Parsingstrategien unterscheiden sich durch die Reihenfolge, in der bei der Konstruktion des Syntaxbaums die Knoten im Baum besucht werden.

• depth-first• breadth-first

• left-to-right• right-to-left

22.04.2003 Vorschau Prolog Aufbaukurs 8/46

Beispielgrammatik (CFPSG)Beispielgrammatik (CFPSG)

rule(s,[np,vp]).rule(np,[d,n]).rule(np,[np,conj,np]).1

rule(vp,[v,np]).rule(vp,[v,np,pp]).rule(pp,[p,np]).rule(d,[]).2

word(d,the).word(conj,and).word(p,near).word(n,dog).word(n,dogs).word(n,cat). word(n,cats).word(n,elephant). word(n,elephants).word(v,chase). word(v,chases).word(v,see). word(v,sees).word(v,amuse). word(v,amuses).

1 nicht für top-down-Parser2 nicht für bottom-up-Parser

22.04.2003 Vorschau Prolog Aufbaukurs 9/46

Top-Down-TraversierungTop-Down-Traversierung

S1

NP2 VP7

D3 N5 V8 NP10

D11 N13

the4 dog6 chased9 the12 cat14

top-down depth-first left-to-right

22.04.2003 Vorschau Prolog Aufbaukurs 10/46

Top-Down-ParserTop-Down-Parser

parse(C,[Word|S],S) :- word(C,Word).

parse(C,S1,S) :- rule(C,Cs), daughters(Cs,S1,S).

daughters([C|Cs],S1,S) :- parse(C,S1,S2), daughters(Cs,S2,S).

daughters([],S,S).

% Wort der Kategorie C% Lexikon-Zugriff

% Phrase der Kategorie C% Regel mit Mutter C% Töchter Cs parsen

% Tochter der Kategorie C% ist Mutter eines Teilbaums% Schwestern parsen

% Alle Töchter verarbeitet

22.04.2003 Vorschau Prolog Aufbaukurs 11/46

Bottom-Up-TraversierungBottom-Up-Traversierung

S14

NP5 VP13

D2 N4 V7 NP12

D9 N11

the1 dog3 chased6 the8 cat10

22.04.2003 Vorschau Prolog Aufbaukurs 12/46

Shift-Reduce-AlgorithmusShift-Reduce-Algorithmus

• Shift: lege ein Wort aus der Eingabekette auf einen Stapel.

• Reduce: reduziere den Stapel mit Hilfe der Grammatik soweit wie möglich.

• Falls die Eingabekette noch Wörter enthält, gehe zu Shift, sonst halte.

22.04.2003 Vorschau Prolog Aufbaukurs 13/46

Left-Corner-TraversierungLeft-Corner-Traversierung

S1

NP6 VP7

D3 N4 V9 NP10

D12 N13

the2 dog5 chased8 the11 cat14

nach Rumpf

22.04.2003 Vorschau Prolog Aufbaukurs 14/46

Chart-ParserChart-Parser

• Ein Chart-Parser speichert Information über bereits geparste Teilstrukturen in einer Tabelle (Chart).

• Bereits geleistete Arbeit kann beim Backtracking aus der Tabelle gelesen werden.

22.04.2003 Vorschau Prolog Aufbaukurs 15/46

Motivation: Motivation: trashingtrashing

VP

V NP PP

D N P NP

D N

chased the cat into the garden

VP V NP

VP V NP PP

22.04.2003 Vorschau Prolog Aufbaukurs 16/46

ChartChart

• In der Tabelle wird für jede Konstituente ein Eintrag gespeichert:– Name der Konstituente– wo sie beginnt– wo sie endet

• Beispielchart(np,[the,cat,into,the,garden],[into,the,garden]).

22.04.2003 Vorschau Prolog Aufbaukurs 17/46

Earley-Chart: Earley-Chart: the dog chases the catthe dog chases the catchart(start,[the,dog,chases,the,cat],[s], [the,dog,chases,the,cat]).chart(s, [the,dog,chases,the,cat],[np,vp],[the,dog,chases,the,cat]).chart(np, [the,dog,chases,the,cat],[d,n], [the,dog,chases,the,cat]).chart(np, [the,dog,chases,the,cat],[n], [dog,chases,the,cat]).chart(np, [the,dog,chases,the,cat],[], [chases,the,cat]).chart(s, [the,dog,chases,the,cat],[vp], [chases,the,cat]).chart(vp, [chases,the,cat],[v,np], [chases,the,cat]).chart(vp, [chases,the,cat],[v,np,pp], [chases,the,cat]).chart(vp, [chases,the,cat],[np], [the,cat]).chart(vp, [chases,the,cat],[np,pp], [the,cat]).chart(np, [the,cat],[d,n], [the,cat]).chart(np, [the,cat],[n], [cat]).chart(np, [the,cat],[], []).chart(vp, [chases,the,cat],[], []).chart(s, [the,dog,chases,the,cat],[], []).chart(start,[the,dog,chases,the,cat],[], []).chart(vp, [chases,the,cat],[pp], []).

22.04.2003 Vorschau Prolog Aufbaukurs 18/46

PerformancePerformanceParser ALS Prolog

20 MHz 80386Quintus PrologSparcstation 1+

DCG 3,4 0,3Top-Down 6,0 1,2Bottom-Up 38,3 8,4Left-Corner ohne Linking 12,7 2,6Left-Corner mit Linking 12,0 2,5Chart ohne Completeness-Check 47,2 20,5Chart mit Completeness-Check 59,3 27,3Chart mit Subsumptions-Check 71,3 32,2Earley ohne Subsumptions-Check 320,3 144,5Earley mit Subsumptions-Check 989,8 172,0

22.04.2003 Vorschau Prolog Aufbaukurs 19/46

LiteraturLiteratur

• Covington, Michael A. (1994): Natural Language Processing for Prolog Programmers. Chap. 6: Parsing Algorithms. Prentice-Hall.

• Gazdar, Gerald & Chris Mellish (1989): Natural Language Processing in Prolog. Addison Wesley.

PATR IIPATR IIInterpreterInterpreter

Prolog Aufbaukurs SS 2000

Heinrich-Heine-Universität Düsseldorf

Christof Rumpf

22.04.2003 Vorschau Prolog Aufbaukurs 21/46

Grammatik-FormalismenGrammatik-Formalismen

• Grammatikformalismen sind Sprachen zur Beschreibung von Sprachen.– Metasprache (Formalismus: Beschreibungsebene)– Objektsprache (natürliche Sprache: Objektebene)

• Anwendungszweck von Formalismen:– Werkzeug-orientiert (PATR II, ALE, QType, ...)– Theorie-orientiert (LFG, GPSG, HPSG, ...)

22.04.2003 Vorschau Prolog Aufbaukurs 22/46

PATR-Design-EntscheidungenPATR-Design-Entscheidungen

• Oberflächenbasiert (vs. transformationiell)

• Informationstragend (linguistisches Wissen)

• Induktiv (Berechnung der Informationskombination)

• Deklarativ (was vs. wie wird berechnet)

• Merkmalsbasiert bzw. Constraintbasiert (komplexe Merkmalsstrukturen)

22.04.2003 Vorschau Prolog Aufbaukurs 23/46

Abdeckung theoretischer Abdeckung theoretischer FrameworksFrameworks

• CG categorial grammar

• GPSG generalized phrase structure grammar

• HPSG head driven phrase structure grammar

• LFG lexical functional grammar

• FUG functional unification grammar

• DCG definite clause grammar

• ...

22.04.2003 Vorschau Prolog Aufbaukurs 24/46

PATR BasisoperationenPATR Basisoperationen

• Konkatenation– String-Kombination auf Basis eines

kontextfreien Phrasenstrukturgerüst. Jeder (Teil-)String wird mit einer Merkmalsstruktur assoziiert.

• Unifikation– Informations-Kombination durch monotone

Unifikation von Merkmalsstrukturen.

22.04.2003 Vorschau Prolog Aufbaukurs 25/46

MerkmalsstrukturenMerkmalsstrukturen

• Seien F (features) und V (values) Mengen.Dann ist FS (feature structures) eine Menge von partiellen Funktionen F V mit V FS1.

num : sing

pers :

cat : NP

agr : 3

num : sing

pers : 3

1: Bzw. V ohne atomare Werte.

22.04.2003 Vorschau Prolog Aufbaukurs 26/46

UnifikationUnifikation

• Die Unifikation FS1 FS2 = FS0 ist die allgemeinste Merkmalsstruktur FS0, so dass FS1 FS0 und FS2 FS0.

• Falls FS0 nicht existiert, scheitert die Unifikation.

num : singagr : num : sing agr : pers : 3 = agr :

pers : 3

ò

agr : num : sing agr : num : plur = fail ò

22.04.2003 Vorschau Prolog Aufbaukurs 27/46

PATR II MerkmalslogikPATR II Merkmalslogik

• Eine Merkmalslogik ist eine Beschreibungs-sprache für Merkmalsstrukturen.

• Ein Ausdruck Li L der PATR II-Merkmalslogik L ist eine Abbildung Li FS (vs. Li (FS) mit Negation und Disjunktion).

• Bestandteile der PATR II-Merkmalslogik sind– Pfadgleichungen P– Makros M L = (P M)*– Konjunktion

22.04.2003 Vorschau Prolog Aufbaukurs 28/46

PfadgleichungenPfadgleichungen• Seien FSi FS, Fj F, AVk AV (atomare Werte),

mit AV V und sei P die Menge der Pfade <FSi Fj*>, dann ist G die Menge der Pfadgleichungen mit Pi = AVk Pi = Pj.

• Originalnotation:– <S head> = <VP head>

– <NP head agr num> = sg

• Prolog-Notation:– S:head === VP:head– NP:head:agr:num === sg

:- op(600,xfx,===).

:- op(510,xfy, : ).

22.04.2003 Vorschau Prolog Aufbaukurs 29/46

Parsing-SessionParsing-Session

PATR II PATR II CompilerCompiler

Prolog Aufbaukurs SS 2000

Heinrich-Heine-Universität Düsseldorf

Christof Rumpf

22.04.2003 Vorschau Prolog Aufbaukurs 31/46

3 Compiler-Komponenten3 Compiler-Komponenten

• Tokenizer– Input: PATR II-Grammatik– Output: Token-Zeilen

• Präprozessor– Input: Token-Zeilen– Output: Token-Sätze

• Syntax-Compiler– Input: Token-Sätze– Output: Prolog-Klauseln

compile_grammar(File):-clear_grammar,tokenize_file(File), read_sentences,compile_sentences.

22.04.2003 Vorschau Prolog Aufbaukurs 32/46

Tokenizer-InputTokenizer-Input

; Shieb1.ptr; Sample grammar one from Shieber 1986

; Grammar Rules; ------------------------------------------------------------

Rule {sentence formation} S --> NP VP:

<S head> = <VP head><VP head subject> = <NP head>.

Rule {trivial verb phrase} VP --> V:

<VP head> = <V head>.

; Lexicon; ----------------------------------------------------------------

Word uther:<cat> = NP<head agreement gender> = masculine<head agreement person> third<head agreement number> = singular.

22.04.2003 Vorschau Prolog Aufbaukurs 33/46

Tokenizer Output = Präprozessor InputTokenizer Output = Präprozessor Input

line(1,[o($;$),b(1),u($Shieb1$),o($.$),l($ptr$)]).line(2,[o($;$),b(1),u($Sample$),b(1),l($grammar$),b(1),l($one$),b(1),l($from$),b(1), ...line(3,[ ]).line(4,[ ]).line(5,[o($;$),b(1),u($Grammar$),b(1),u($Rules$)]).line(6,[o($;$),b(1),o($-$),o($-$),o($-$),o($-$),o($-$),o($-$),o($-$),o($-$),o($-$),o($-$), ...line(7,[ ]).line(8,[u($Rule$),b(1),o(${$),l($sentence$),b(1),l($formation$),o($}$)]).line(9,[b(2),u($S$),b(1),o($-$),o($-$),o($>$),b(1),u($NP$),b(1),u($VP$),o($:$)]).line(10,[b(1),o($<$),u($S$),b(1),l($head$),o($>$),b(1),o($=$),b(1),o($<$),u($VP$),b(1), ...line(11,[b(1),o($<$),u($VP$),b(1),l($head$),b(1),l($subject$),o($>$),b(1),o($=$),b(1), ...line(12,[b(1)]).line(13,[u($Rule$),b(1),o(${$),l($trivial$),b(1),l($verb$),b(1),l($phrase$),o($}$)]).line(14,[b(2),u($VP$),b(1),o($-$),o($-$),o($>$),b(1),u($V$),o($:$)]).line(15,[b(1),o($<$),u($VP$),b(1),l($head$),o($>$),b(1),o($=$),b(1),o($<$),u($V$),b(1),......line(41,[b(1),o($<$),l($head$),b(1),l($subject$),b(1),l($agreement$),b(1),l($number$),...line(42,[eof]).

22.04.2003 Vorschau Prolog Aufbaukurs 34/46

Präprozessor Output = Compiler InputPräprozessor Output = Compiler Input

sentence( 1,11,[u($Rule$),o(${$),l($sentence$),l($formation$),o($}$),...

sentence(12,15,[u($Rule$),o(${$),l($trivial$),l($verb$),l($phrase$),o($}$),...

sentence(16,24,[u($Word$),l($uther$),o($:$),o($<$),l($cat$),o($>$),o($=$),...

sentence(25,30,[u($Word$),l($knights$),o($:$),o($<$),l($cat$),o($>$),o($=$),...

sentence(31,36,[u($Word$),l($sleeps$),o($:$),o($<$),l($cat$),o($>$),o($=$),...

sentence(37,41,[u($Word$),l($sleep$),o($:$),o($<$),l($cat$),o($>$),o($=$),...

sentence(42,42,[eof]).

Der Präprozessor entfernt Kommentare und Leerzeichen und fasst mit einem Punkt terminierte Sätze aus mehreren Zeilen zusammen. Der eigentliche Compiler kann sich dann auf das wesentliche konzentrieren.

22.04.2003 Vorschau Prolog Aufbaukurs 35/46

Compiler OutputCompiler Output

A ---> B , C :: A : cat === 'S', B : cat === 'NP', C : cat === 'VP', A : head === C : head, C : head : subject === B : head.

A ---> uther :: A : cat === 'NP', A : head : agreement : gender === masculine, A : head : agreement : person === third, A : head : agreement : number === singular.

22.04.2003 Vorschau Prolog Aufbaukurs 36/46

LiteraturLiteratur

• Shieber, Stuart (1986): An Introduction to Unification-based Approaches to Grammar. CSLI Lecture Notes.

• Gazdar, Gerald & Chris Mellish (1989): Natural Language Processing in Prolog. Addison Wesley.

• Covington, Michael A. (1994): Natural Language Processing for Prolog Programmers. Chap. 6: Parsing Algorithms. Prentice-Hall.

TypinferenzTypinferenz

Prolog Aufbaukurs SS 2000

Heinrich-Heine-Universität Düsseldorf

Christof Rumpf

22.04.2003 Vorschau Prolog Aufbaukurs 38/46

HintergrundHintergrund

• Getypte Merkmalsstrukturen sind von Bedeutung insbesondere für die HPSG.

• Implementierte Systeme zur Verarbeitung getypter Merkmalsstrukturen sind u.a. ALE, CUF, LKB, TFS, TROLL, ...

• Die nachfolgenden Definitionen liegen dem Düsseldorfer System QType zugrunde, das sich seit 1997 in Entwicklung befindet.

22.04.2003 Vorschau Prolog Aufbaukurs 39/46

Getypte MerkmalsstrukturenGetypte Merkmalsstrukturen

• Sind Mengen von Attribut-Wert-Paaren.

• Jede Merkmalsstruktur hat einen Typ.

• Jeder Wert eines Attributs ist eine getypte Merkmalsstruktur.

• Die Typen sind in einer Vererbungshierarchie (Summenhalbverband) angeordnet, innerhalb der Attribut-Wert-Paare top-down vererbt werden.

• Die Vererbungshierarchie wird durch eine Typensignatur etabliert, in der Klassen von Merkmalsstrukturen definiert werden.

22.04.2003 Vorschau Prolog Aufbaukurs 40/46

Typensignatur - SyntaxTypensignatur - Syntax

• 2 Mengen: Types, Features• 2 Relationen:

– unmittelbarer Subtyp >>– Appropriateness ::

• TypdefinitionSupertyp

>> Subtyp1, ..., Subtypn :: Feature1:Typ1, ...,Featurem:Typm.

22.04.2003 Vorschau Prolog Aufbaukurs 41/46

TyphierarchieTyphierarchie

category

verbal np

v vp s

head

vhead nhead

gen

masc fem neut

pers

first second third

num

sing plur

vform

finite base

featval

top

agr

22.04.2003 Vorschau Prolog Aufbaukurs 42/46

FS zu Typ FS zu Typ ss in ‚Shieber 1‘ in ‚Shieber 1‘s

HEAD : vhead

np

SUBJECT : HEAD : nhead

agr

NUMBER : numAGREEMENT :

PERSON : pers

GENDER : gen

FORM : vform

22.04.2003 Vorschau Prolog Aufbaukurs 43/46

Typensignatur-InterpreterTypensignatur-Interpreter

• type(?Type)

• immediate_subtype(?ImmediateSubType,?Type)

• subtype(?SubType,?Type)

• immediate_supertype(?SuperType,?Type)

• supertype(?SuperType,?Type)

• lb(?Type1,?Type2,?Type3) lower bound

• glb(?Type1,?Type2,?Type3) greatest lower bound

• ub(?Type1,?Type2,?Type3) upper bound

• lub(?Type1,?Type2,?Type3) least upper bound

• complement(?Type,-Complement)

22.04.2003 Vorschau Prolog Aufbaukurs 44/46

Interpretieren vs. KompilierenInterpretieren vs. Kompilieren

• Eine Typensignatur enthält implizit viele Relationen.

• Ein Interpreter macht diese Relationen explizit.– Laufzeit-, Runtime-, bzw. Online-Berechnung

• Ein Compiler berechnet (alle) Relationen vollständig und liefert das Ergebnis der Berechnung zum direkten Zugriff.– Kompilezeit-, Compiletime-, bzw. Offline-Berechnung

22.04.2003 Vorschau Prolog Aufbaukurs 45/46

MerkmalslogikMerkmalslogik• Eine Merkmalslogik definiert eine Beschreibungssprache

für Merkmalsstrukturen.

• Die Semantik eines Ausdrucks in unserer Merkmalslogik wird durch die partielle Funktion mgu definiert:

mgu: Descr 2FSs

• Partiell: nicht alle Beschreibungen haben Lösungen.

• Potenzmenge: manche Beschreibungen haben mehrere Lösungen, da durch Disjunktion und Negation ein Nichtdeterminismus eingebracht wird.

22.04.2003 Vorschau Prolog Aufbaukurs 46/46

Bestandteile der LogikBestandteile der Logik

• Variablen• Typen• Attribut-Wert-Paare• Konjunktion• Disjunktion• Negation• Makros

• PrologVar DESCR• Type DESCR• F:DESCR DESCR• DESCR, DESCR DESCR• DESCR; DESCR DESCR• - DESCR DESCR• @MacroHead DESCR

22.04.2003 Vorschau Prolog Aufbaukurs 47/46

mgu/1mgu/1

mgu(Descr):-

mgu(Descr,top, FS),

print_fs(FS).

:

:

:

agr

cas cas

num num

gen gen

(_1,agr, [ cas:(_2,cas,[]),

num:(_3,num,[]),gen:(_4,gen,[])])

agr