Einf. in das symbolische Programmieren      CIS, SS 2002, H.Leiss
=================================================================

Abgabe: Mittwoch, 10.7.2002 in der Vorlesung
--------------------------------------------

Aufgabe 17:
----------
Das Uebersetzungsprogramm translate/2 (s.Vorlesungsfolien bzw. 
dcg-uebersetzer.pro) kann zwar gewisse Disjunktionen in den
rechten Regelseiten behandeln, wie z.B.

   np --> det, n (np ; pp).

Aber *optionale* Konstituenten, wie z.B. ein optionales Adjektiv in
Nominalphrasen, das man durch

   np --> det, (a ; []), n.         (*)

beschreiben moechte, fuehrt zu einem Fehler bei der Analyse. 

Erweitere die Beispielgrammatik aus Aufgabe 15 um die Regel (*) und
die Adjektive 'schnell' und 'fleissig' (in den noetigen Wortformen).

Wie muss translate/4 geaendert werden, damit man mit (*) auch
optionale Adjektive behandeln kann?                       (4 Punkte)

Aufgabe 18:
-----------
In Aufgabe 16 (und in der letzten Uebung) haben wir die Kategorien
einer Grammatik um Ausgabeargumente fuer den Syntaxbaum (als
Prologterm) erweitert. Z.B. wurden 

   a --> [wort].
   a --> b, c.

zu 

   a(Baum) --> [wort], { Baum = a(wort) }.
   a(Baum) --> b(Baum1), c(Baum2), { Baum = a(Baum1,Baum2) }.

oder, wenn man den Ergebnisbaum in den Kopf der Klausel einsetzt:

   a( a(wort) ) --> [wort].
   a( a(Baum1,Baum2) ) --> b(Baum1), c(Baum2).      (**)

Da diese Aenderung der Grammatik jede Regel nach demselben Schema
behandelt, koennen wir die neuen Regeln auch automatisch erzeugen!

Schreibe ein neues Uebersetzungsprogramm

   ergaenze_baumausgabe(+Regel,-ErgaenzteRegel)

das zu jeder DCG-Regel (ohne Disjunktionen auf den rechten Seiten)
eine entsprechende Regel von der Form wie (**) ausgibt.

Hinweis:
--------
Vervollstaendige das folgende Programmfragment:

% 1. Lexikalische Regeln: 
ergaenze_baumausgabe((Links --> [Wort]),(LinksErw --> [Wort])) :-
     !, 
     ergaenze_baum(Links,[Wort],LinksErw,_Baum).

% 2. Syntaktische Regeln:
ergaenze_baumausgabe((Links --> Rechts),(LinksErw --> RechtsErw)) :-
     ergaenze_baeume(Rechts,RechtsErw,Baeume),
     ergaenze_baum(Links,Baeume,LinksErw,_Baum).

durch zwei Hilfspraedikate, die folgendes leisten:

a) ergaenze_baum(+Kategorie,+Teilbaeume,-NeueKategorie,-Baum). 
                                                         (4 Punkte)
  
Aus einer Kategorie und vorgegebenen Teilbaeumen soll ein Baum
gebildet werden, indem man nur das Funktionszeichen der Kategorie mit
den Teilbaeumen zusammensetzt; ausserdem soll eine neue Kategorie
ausgegeben werden, die diesen Baum als Ausgabeargument liefert. Z.B.

   +Kategorie = np(Kas), +Teilbaueme = [BaumA,BaumB,BaumC]
   ==>
   -Baum = np(BaumA,BaumB,BaumC),  -NeueKategorie = np(Kas,-Baum).

Bem: Den Ausgabebaum -Baum braucht man bei den Aufrufen in
     ergaenze_baumausgabe/2 nicht, aber bei den Aufrufen in Teil b).
     
b) ergaenze_baeume(+Tupel von Kategorien,                (4 Punkte)
                   -Tupel der neuen Kategorien,
                   -Liste der Ausgabebaeume der neuen Kategorien)

Zu den Kategorie einer rechten Regelseite muessen einerseits neue
Kategorien mit den jeweiligen Ausgabeargumenten gebildet werden. Die
Liste der Ausgabebaeume braucht man, um den Baum fuer die linke
Regelseite zu bilden. z.B.

   +Kategorientupel = (det(Kas), n(Kas))
   -NeueKategorien =  (det(Kas,BaumDet), n(Kas,BaumN))
   -Liste der Ausgabebaeume = [BaumDet, BaumN]

Bem. Sehen Sie einen Fall fuer n+1-Tupel (A,B) vor und einen Fall fuer
     1-Tupel (A).

Fuer eine Regel ohne {...} und [...]-Teile sollte man erhalten:

   ?- ergaenze_baumausgabe((np --> det, n),Neu).

   Neu = np(np(BaumD, BaumN))-->det(BaumD), n(BaumN) .

c) Wenn b) funktioniert, fuege in ergaenze_baume((A,B),...,Baeume) zwei
   Sonderfaelle fuer A der Form {Atome} oder [Atom] ein.

   Wie muss hier die Liste der Baeume aussehen?          (4 Punkte)

d) Kombiniere die Praedikate

       ergaenze_baumausgabe(DCG-Regel,Neue-DCG-Regel)  
   und 
       translate(Regel,Klausel)           (aus dcg-uebersetzer.pro)

   zu einem Praedikat

       translate_mit_baum(DCG-Regel,Klausel),

   das sowohl die Baumausgabe wie die Differenzlistenargumente zu
   einer DCG-Regel hinzufuegt.                           (3 Punkte).