Elemente der künstlichen Intelligenz (5): Grammatiken in Prolog
Die bei weitem wichtigste Anwendungen der KI ist der intelligente Umgang des Computers mit dem Menschen. Alan Turing, einer der geistigen Väter des Computers, hat 1950 den bekannten Test veröffentlicht, der über die Intelligenz eines Computers Auskunft geben soll [4]. Danach erkennt man einen intelligenten Computer daran, daß man ihn nicht (als solchen) erkennt. Stellen Sie sich vor, Sie sitzen in einem abgedunkelten Raum, Sie können Ihren Gesprächspartner nicht erkennen aber sich angeregt mit ihm unterhalten. Nach der Unterhaltung werden Sie gefragt, ob Sie mit einem Computer oder mit einem Menschen kommuniziert haben. Gelingt Ihnen keine eindeutige Aussage, und ist Ihr Gesprächspartner wirklich ein Computer, dann ist er wohl völlig zu Recht intelligent zu nennen.
Beim heutigen Stand der Technik wäre man natürlich schon mit einer Kommunikation über Tastatur und Bildschirm zufrieden, da man Computersprache noch sehr deutlich von menschlicher Sprache unterscheiden kann. Das gleiche gilt für das Verständnis des gesprochenen Wortes. Es gibt schließlich noch nicht die über Mikrofon mitschreibende Schreibmaschine, geschweige denn den Sinn eines gesprochenen Satzes verstehenden und entsprechend agierenden Computer. Aber die Kommunikation über Tastatur und Bildschirm klappt schon ganz gut. Wesentliche Bestandteile eines solchen Sprachen verstehenden Systems sind die Grammatiken, eine Domäne von Prolog.
Grammatikregeln in Prolog
Wenn wir einen Computer zur Verarbeitung von Sätzen einer Sprache verwenden wollen, dann müssen wir vorher genau definieren, welche Form die Sätze haben dürfen. Die erlaubte Form der Sätze heißt die Syntax einer Sprache. Die Bedeutung der erlaubten Sätze wird durch die Semantik festgelegt. Für natürliche Sprachen ist die Festlegung der Syntax ein schwieriges Unternehmen, da sich die Sprachgewohnheiten ständig ändern. Für die Verwendung mit Computern werden deshalb einfachere Sprachen verwendet, die sogenannten formalen Sprachen, deren Aufbau leichter zu definieren ist. Eine Grammatik ist dann nichts anderes als eine Menge von Regeln, die festlegen, welche Sätze erlaubt sind und welche nicht (Definition der Syntax). Wir beschäftigen uns im Bereich der Computersprachen nur mit kontextfreien Grammatiken, die aus folgenden Teilen besteht:
- Einer endlichen Menge VN von Nichtterminalsymbolen. Z.B. VN = s,a,b.
- Einer endlichen Menge VT von Terminalsymbolen. Z.B. VT = |[d], [f], [gf . Man beachte: in Prolog sind die terminalen Symbole in eckige Klammern gesetzt! Für beide Mengen muß gelten, daß Ihre Schnittmenge leer ist (VN U VT = 0), d.h. kein Element aus VT ist in VN und umgekehrt.
- Einer Menge R von Regeln. In Prolog haben diese Regeln die Form v----> z,y,z. Wenn die Grammatik kontextfrei sein soll, muß v aus VN sein, x kann wie y und z aus VN oder VT sein.
- Einem Startsymbol s (siehe Beispiel in 1).
Man sieht also, daß die Nichtterminalsymbole Atome oder Strukturen verschieden von Listen sind, die Terminalsymbole dagegen einelementige Listen.
Als Sprache L(G) bezeichnet man dann alle aus dem Startsymbol s ableitbaren Terminalworte (Terminalwort = Terminalsymbolfolge). Für weitgehende Informationen seien [1] und [2] empfohlen.
Ein Beispiel
Um das oben beschriebene theoretische Gerüst etwas verständlicher zu machen, wollen wir als nächstes ein einfaches umgangssprachliches Modell entwickeln.
Ein Satz ist ein Gebilde aus Subjekt, Verb, Objekt. Ein Subjekt besteht aus Artikel und Substantiv. Ebenso ein Objekt. Um die Sache nicht zu kompliziert zu machen, sollte unsere Beispielgrammatik nur einen Artikel besitzen und die Substantive für Subjekt und Objekt gleichen Geschlechts sein. Wir wählen als Artikel das Terminalsymbol [die], für das Substantiv verwenden wir die Terminalsymbole [maus] und [schlänge] und für das Verb verwenden wir [beisst] und [frisst]. Eine so definierte Grammatik würde man in Prolog folgendermaßen angeben:
satz ------------> Subjekt,verb, objekt.
Subjekt ---------> artikel,substantiv.
objekt ----------> artikel,substantiv.
artikel ---------> [die],
substantiv-----> [maus].
substantiv-----> [schlange].
verb ---------> [beisst],
verb ---------> [frisst].
Das nichtterminale Symbol satz wird also aus den Konstrukten Subjekt, verb und objekt gebildet, alles nichtterminale Symbole. Subjekt und objekt entstehen aus den Konstrukten artikel und substantiv, artikel , substantiv und verb schließlich entstehen aus terminalen Symbolen. Das Startsymbol der Grammatik ist satz. Demnach wäre die Terminalsymbolfolge [die,schlänge,beisst,die,maus] ein Satz der Sprache der oben definierten Grammatik. Um dies nachzuweisen, müßten wir mit Hilfe der Grammatikregeln zeigen, daß die angegebene Terminalsymbolfolge das Konstruktsatz bildet. Abb. 1 zeigt die Herleitung grafisch an einem Ableitungsbaum. Natürlich interessiert uns, wie Prolog an Hand der grammatischen Regeln erkennt, daß der obige Beispielsatz ein Satz der durch die gegebene Grammatik definierte Sprache ist. Abb. 2 zeigt deshalb die Herleitung in TOY-Prolog. Lediglich das yes. zeigt die Zustimmung von Prolog zu unserem Satz. Einen Satz mit anderen Elementen als den durch unsere Grammatik definierten lehnt Prolog dagegen ab. Man beachte außerdem, daß in der Abb. 2 das Prädikat satz/2 verwendet wird. Dies ist vorher aber nicht bekannt gewesen. Also muß der Prolog Interpreter bereits beim einiesen der grammatischen Regeln diese in gleichnamige Prädikate übersetzt haben. In TOY-Prolog kann man sich diese Übersetzung mit dem mitgelieferten Editor ansehen (Abb 3).
Übersetzung der grammatischen Regeln
Bei näherer Betrachtung des Ableitungsbaumes in Abb. 1 wird verständlich, wie Prolog die grammatischen Regeln übersetzt:
Nichtterminale Symbole werden in zweistellige Prädikate umgewandelt, erweitert um zwei Argumente Xn. Das linke Argument steht für die Eingabe, das rechte für die Ausgabe. Im Rumpf der Übersetzung (manchmal auch Produktion genannt) wird die Ausgabe des finken Symbols als Eingabe des rechten Symbols benutzt.
Terminale Symbole werden so eingefügt, daß sie in der entsprechenden Ausgabefiste fehlen.
Abb. 4 zeigt die Übersetzungen einiger (völlig unsinniger) gramatischer Regeln.
Gehört ein Satz zur Sprache dieser Grammatik?
Der Satz [die,schlange,beisst,die,maus] ist darauf zu überprüfen, ob er ein Satz, der durch die gegebene Grammatik definierte Sprache ist. folglich muß dieser Satz bei der Herleitung aus der Grammatik rekonstruiert werden. Das finke Argument des Prädikates satz enthält also den zu untersuchenden Satz und das rechte Argument die leere Liste, denn bei der Ableitung des Satzes dürfen keine unidentifizierten Satzbestandteile übrigbleiben. Abb. 5 zeigt den Weg der Ableitung im Baum von Abb. 1 mit den zugehörigen Instanzierungen. Der Aufruf in Prolog erfolgt einfach mit satz[die,schlange,beisst,die, maus],[]). Das yes von Prolog ist als Zustimmung zur korrekten Syntax zu bewerten. Will man sich alle syntaktisch korrekten Sätze dieser Sprache ansehen, so genügt in Prolog die Eingabe satz(S,D)- Daraufhin instanziert Prolog die Variable S mit allen syntaktisch korrekten Sätzen dieser Sprache. Leider haben Benutzer von Salix Prolog hier ihre Schwierigkeiten. Zwar ist in dem Lieferumfang ein Übersetzer nach Clocksin & Mellish enthalten, leider aber werden die Regeln unserer Beispielgrammatik nicht korrekt übersetzt (siehe auch [3]).
Eine Anwendung aus dem Bereich der Computersprachen
Ein Programm, welches eine Datei auf korrekte Syntax einer Sprache untersucht, heißt ein Parser. Und wie man diesem Aufsatz entnommen haben sollte, ist Prolog in idealer Weise geeignet, die Funktion eines Parsers zu übernehmen. Ein Beispiel hierzu ist Abb. 6 gegeben. Die im schwarzen Bereich gegebene Grammatik definiert die korrekte Syntax einer stark vereinfachten If-Then Anweisung. Im dunkel punktierten Bereich wird ein syntaktisch korrekter Satz untersucht. Prolog quittiert die Korrektheit nüchtern mit yes. Im hell punktierten Bereich wird ein syntaktisch falscher Satz untersucht und als solchei^r-kannt. So einfach dieses Beispiel auch ist, es zeigt, daß Prolog mehr ist als nur eine Sprache zur Abfrage einer Wissensbasis.
Dr. Sarnow
Literatur
Hanus M. Problemlosen mit PROLOG. B.G. Teubner, Stuttgart, 1986.
Kleine Bütgen, H., S. Schmitgen. PROLOG. B.G. Teubner, Stuttgart, 1986.
Sarnow, K. Salix Prolog Review, ST Computer.
Turing, Alan M. Computing Machinery and Intelligence. Mind, Bd. LDC, Nr. 236, 1950.
