Mein PrologCompiler

Mein PrologCompiler
Im Rahmen der KI-Vorlesung verlangt man von uns einen PrologCompiler und eine dazugehörige Maschine.

Projekt Das Projekt SimpleProlog

Hier gelangen Sie direkt zum Online-Prolog: SimplePrologPlus.

Aufgabenstellung

Schreibe in der Programmiersprache deiner Wahl einen simplen PrologCompiler mit der dazugehörigen abstrakten Maschine gemäß den Beschreibungen von den Herren Wilhelm und Maurer [COMPILER97]!

Idee

Dieses Projekt findet seinen Anstoß in der Philosophie meines Erlanger KI-Professors Prof. Dr. H. Stoyan. Stoyan ist der Auffassung, dass ein Informatiker jederzeit in der Lage sein muss, eine eigene Programmiersprache zu entwickeln.

Zudem eignet sich im Rahmen der KI-Vorlesung die Nachimplementierung der Programmiersprache Prolog besonders gut, da man mit ihr den Umgang mit einer Wissensbasis eines KI-Systems ohne viel Aufwand üben kann. Des Weiteren bietet Prolog eine praxisnahe Anwendungsmöglichkeit der Prädikatenlogik erster Stufe.

Schwierigkeiten

So gut wie keiner der bei Stoyans Vorlesung hat jemals mit Prolog oder mit einem anderen Vertreter des Logik-Kalküls (wie z. B. mit CLP) zu tun gehabt. :-(
Deshalb mussten wir zunächst so schnell wie möglich die Programmiersprache Prolog erlernen, um diese dann später implementieren zu können. In den Übungsstunden sahen wir uns mit einem Crashkurs in Prolog konfrontiert. Da wir dank des Grundstudiums auf funktionale Programmiersprachen (SCHEME oder SML) aufbauen konnten, haben wir recht schnell das Gesamtkonzept dieser Sprache begriffen.

Ausführung

Ich selbst nenne dieses Projekt SimpleProlog und verwende zu dessen Realisierung die Programmiersprache PHP in Zusammenhang mit HTML/CSS.
Meine Idee gleicht der Idee eines jeden PHP-Liebhabers:

Ein Projekt onlinefähig machen, ein onlinefähiges Prolog mit user-interface!

Resultat

So habe ich ein lauffähiges OnlineProlog, welches alle Anforderungen der Aufgabenstellung erfüllt, implementiert.

Genauer gesagt gibt es nun zwei Versionen:

SimpleProlog
Die Version gemäß den Anforderungen.
PHP-Source-Codes sowie einige kleine SimpleProlog-Programmbeispiele sind dabei.
SimplePrologPlus
Diese Version enthält zusätzlich die Operationen:
- CUT und
- FAIL.
Die Prolog-Grammatik sowie die abstrakte Maschine WiM mussten etwas erweitert werden. Aber der Aufwand lohnte sich, da nun kompliziertere Algorithmen, wie zum Beispiel Sortieralgorithmen, formuliert werden können.
PHP-Source-Codes sowie viele kleine SimplePrologPlus-Programmbeispiele sind dabei.

Dieses OnlineProlog erfüllt lediglich die Minimalvoraussetzungen eines PrologInterpreters. Der Umgang mit Konstanten wie zum Beispiel Zahlen oder Strings ist nicht integriert. Ebenso können keine Module geladen werden.

Selbst der allseits beliebte syntaktische Zucker fehlt!
Zum Beispiel können Listen nicht wie üblich mit eckigen Klammern gebildet, sondern nur mittels Strukturtermen konstruiert werden, also statt [a, b, c] empfiehlt es sich, cons(a, cons(b, cons(c, nil))) bzw. mylist(mylist(mylist(nix, a), b), c) zu schreiben und dementsprechend zu behandeln.

Trotz dieser Einschränkungen kann SimpleProlog einiges zum allgemeinen Verständnis von Prolog beitragen, zumal Prolog-Beispiele reichlich vorhanden sind.

Der Umgang mit Listen unter SimpleProlog


% Das Konkatenieren zweier Listen bezeichnet man als append.



append(nil, L, L).

append(cons(X, XL), YL, cons(X, ZL)) :- append(XL, YL, ZL).



?- append(cons(a, cons(b, nil)), cons(c, nil), Result).



% ergibt:

%         Result = cons(a, cons(b, cons(c, nil)))

⇑ Der Umgang mit Listen unter SimpleProlog ⇑

Man muss nur die folgende Prolog-Listenschreibung

[X|XL] in cons(X, XL),
[a, b, c] in cons(a, cons(b, cons(c, nil)))

umwandeln. Denn Listen sind ja nichts anderes als einfach verkettete Tupel (cons) mit Terminierung (nil), ähnlich wie in SCHEME.

Fazit

Da wir ja einen Prologcompiler entwickeln mussten, haben wir zwangsläufig die Hintergründe von Prolog besser kennen gelernt, nach dem Motto: „Willst du eine Sprache lernen, dann schreibe einen Compiler für diese Sprache!” :-)

Compiler Prolog -> WiMAssembler

Der PrologCompiler

Der Ansatz, ein Prolog-Programm in einen entsprechenden Assembler-Code zu übersetzen, liegt in der prozeduralen Betrachtungsweise. Die Zusammenfassung von Klauseln mit gleichnamigen Köpfen sei eine Prozedur, wobei jede einzelne Klausel eine Alternative innerhalb der Prozedur sei.

Der schließlich erzeugte Assembler-Code kommt dann auf einer abstrakten Maschine, hier der sogenannten WiM, zur Ausführung.

Der PrologCompiler übersetzt ein Prolog-Programm in einen WiM-Assembler-Code und besteht aus drei Hauptkomponenten:

Scanner
Der Scanner liest den Zeichenstrom als Tokenstrom und wird vom Parser benutzt. Da Prolog lediglich die Prädikatenlogik erster Stufe verkörpert und der Sprachumfang sehr klein ist, gibt es auch nicht viele unterschiedliche Tokens, sodass der Scanner durchaus auch per Hand programmiert werden kann, ohne dabei an Übersichtlichkeit zu verlieren.
Parser
Dieser Parser ist ein Top-Down-Parser und erkennt die Grammatik des Prolog-Programms. Er gibt die wesentlichen Informationen an die Bestandteile des CodeGenerators weiter (Aufbau des Syntaxbaumes).
CodeGenerator
Nach dem Parse-Vorgang kann der CodeGenerator den Assembler-Code erzeugen bzw. ausgeben. Der CodeGenerator wird hier nur vom Parser verwendet.

Maschine Die WiM-Maschine

Die WiM-Maschine

Diese Maschine haben sich Wi-lhelm und M-aurer ausgedacht. Sie simuliert eine stackorientierte Rechenmaschine, auf der ein übersetztes Prolog-Programm, ein bestimmter WiM-Assembler-Code, zur Ausführung kommt.

Die Arbeitsweise der WiM gleicht in etwa derjenigen eines Prozessors. Nach dem das Assembler-Programm geladen wurde, sieht die Abarbeitung des Programms wie folgt aus:

Lese Instruktion von Programm[PC].
Zähle PC um eins hoch.
Führe die Instruktion aus.
Gehe wieder zu 1.

Arbeitsweise der WiM


1. Instruction := ReadInstruction(Program[ProgramCounter])

2. ProgramCounter++

3. ExecuteInstruction(Instruction)

4. Goto 1

⇑ Arbeitsweise der WiM ⇑

Wie nun die WiM-Maschine im Detail funktioniert und der dazugehörige Assembler-Code aufgebaut sein muss, können Sie unter [COMPILER97] nachlesen.

Startseite Sitemap Downloads Hilfe Impressum

Quellenangabe

[COMPILER97] Übersetzerbau: Prof. Dr. Reinhard Wilhelm, Dr. Dieter Maurer, 1997 Auflage2, Springer-Verlag ISBN 3-540-61692-6 Theorie, Konstruktion, Generierung