Einf. in das symbolische Programmieren CIS, SS 2001, H.Leiss ================================================================= Abgabe: Donnerstag, 28.6.2001 in der Vorlesung ----------------------------------------------- Aufgabe 10 8 Punkte ---------- Angenommen, wir brauchen Baeume, deren Verzweigungsknoten nicht zu zwei, sondern zu beliebig vielen direkten Teilbaeumen verzweigen duerfen. Ausserdem sollen sowohl die Blaetter, als auch die Verzweigungsknoten markiert sein, wie bei Syntaxbaeumen: s / \ np vp / | \ / \ det a n v np / / / | / \ / / | | det n / / | | \ \ der junge Hund jagt die Katze Die Markierungen sollen an den inneren Knoten des Baums aus einer vorgegebenen Liste von syntaktischen Kategorien stammen: knotenmarke(M) :- member(M,[s,n,a,v,p,np,vp,pp,adv,det,conj]). An den Blattknoten sollen beliebige Prolog-Atome stehen duerfen: blattmarke(M) :- atom(M). (Bem. In Prolog ist z.B. Hund eine Variable, kein Atom, aber 'Hund' ist ein Atom.) In Prolog gibt es ein eingebautes Relationszeichen '=..' (infix, d.h. zwischen die Argumente geschrieben), mit dem man einen Term zerlegen und eine Liste [Funktionszeichen|Teilterme] seiner Bestandteile erhaelt: ?- f(a,g(b,c),d) =.. L. L = [f, a, g(b,c), d] Aufgabe: Definiere ein Praedikat syntaxbaum/1, das folgende Terme von Prolog (ohne Variablen) als Darstellungen von Syntaxbaeumen auszeichnet: i) Jeder Term, der ein einstelliges Funktionszeichen hat, das eine Knotenmarke ist, und dessen Teilterm eine Blattmarke ist, stellt einen Syntaxbaum dar. ii) Jeder Term, der ein Funktionszeichen hat, das eine Knotenmarke ist, und dessen direkte Teilterme Syntaxbaeume darstellen, stellt selber einen Syntaxbaum dar. Nach i) soll also z.B. gelten: syntaxbaum(det(die)) und syntaxbaum(n('Katze')). Nach ii) soll daher z.B. gelten: syntaxbaum(np(det(die),n('Katze))). Hinweis: Benutze das Hilfspraedikat '=..' zur Zerlegung von Termen und ein Hilfspraedikat syntaxbaumliste/1, das Listen von Syntaxbaeumen definiert. Aufgabe 11 10 Punkte ---------- Betrachte folgendes Programm zur Vereinfachung von Syntaxbaeumen (vgl Aufg.10): vereinfache(s(NP,VP), SE) :- vereinfache(NP,NPE), vereinfache(VP,VPE), SE = s(NPE,VPE). vereinfache(np(X,conj(und),Y),NPE) :- !, vereinfache(X,XE), NPE = np(XE,conj(und),Y). vereinfache(np(X,conj(und),Y),NPE) :- !, vereinfache(Y,YE), NPE = np(X,conj(und),YE). vereinfache(np(det(Artikel),a(Adjektiv),n(Nomen)),NPE) :- !, NPE = np(det(Artikel),n(Nomen)). vereinfache(vp(v(Verb),adv(Adverb),NP),VPE) :- VPE = vp(v(Verb),NP). vereinfache(vp(v(Verb),adv(Adverb),NP),VPE) :- !, vereinfache(NP,NPE), VPE = vp(v(Verb),adv(Adverb),NPE). vereinfache(X,X). Betrachte den Beispielsatz Der junge Hund jagt manchmal die schnelle Katze und den flinken Hasen. a) Welche 3 Loesungen liefert Prolog zu vereinfache(s(np(det('Der'),a(junge),n('Hund')), vp(v(jagt), adv(manchmal), np(np(det(die),a(schnelle),n('Katze')), conj(und), np(det(den),a(flinken),n('Hasen'))))), Satz). b) Gib fuer jede der 3 Loesungen an, welche der 7 Klauseln beim Beweis dieser Loesung verwendet werden. c) Welches ! bewirkt, dass keine weiteren Loesungen gefunden werden? Begruende, warum dieses ! die uebrigen denkbaren Loesungen abschneidet, (und nicht ein anderes der !). d) Modifiziere das Programm vereinfache/2 so, dass es folgendes macht: - aus jeder Verbalphrase werden die Adverbien entfernt, und - aus jeder Nominalphrase werden die Adjektive entfernt. Beim Beispielsatz sollte das Programm also nur den vereinfachten Satz der Hund jagt die Katze und den Hasen liefern (d.h. den entsprechenden Syntaxbaum). (Es reicht, wenn man Saetze und Nominalphrasen wie in den Koepfen der obigen Regeln behandeln kann!) Hinweis: Fuer d) braucht man b) und c) nicht zu verstehen; das Programm wird auch einfacher.