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.


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.


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.


LiteraturLiteratur

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


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


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


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


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


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


Bottom-Up-TraversierungBottom-Up-Traversierung

S14

NP5 VP13

D2 N4 V7 NP12

D9 N11



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.


Left-Corner-TraversierungLeft-Corner-Traversierung

S1

NP6 VP7

D3 N4 V9 NP10

D12 N13


nach Rumpf


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.


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


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]).


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], []).


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


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


Christof Rumpf


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, ...)


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)


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

• ...


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.


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.


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 ò


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


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, : ).


Parsing-SessionParsing-Session

PATR II PATR II CompilerCompiler



Christof Rumpf


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.


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.


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]).


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.


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.


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



Christof Rumpf


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.


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.


Typensignatur - SyntaxTypensignatur - Syntax

• 2 Mengen: Types, Features• 2 Relationen:

– unmittelbarer Subtyp >>– Appropriateness ::

• TypdefinitionSupertyp

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


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


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


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)


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


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.


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


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

Documents

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