Implementierung der operationellen Semantik in einer Programmiersprache


... [Seminar Programmierkonzepte und -sprachen] ... [↑ Gliederung] ... [← Die Opeartionale Semantik der Beispielsprache] ... [→ Literaturverzeichnis] ...

Implementierung der operationellen Semantik in einer Programmiersprache

Es ist möglich die Reduktionsregeln direkt in einer Programmiersprache zu implementieren. Man bekommt eine sogenannte ausführbare Spezifikation. Der Sinn dieser Implementierung ist, dass man dadurch praktisch einen Interpreter der Sprache erhält, der uns dann die Prüfung der Korrektheit der zugrundeliegenden Spezifikation ermöglicht. Da die Reduktionsregeln, die wir definiert haben ähnlich den Inferenzregeln sind, ist eine logische Programmiersprache (z. B. Prolog) eine natürliche Wahl für die Implementierungsprache. Wir wollen eine mögliche Prolog-Implementierung der Reduktionsregeln für arithmetische Ausdrücke unserer kleinen Beispielsprache kurz erläutern.

Wir überlegen zuerst, wie ein arithmetischer Ausdruck aus unserer Beispielsprache in Prolog dargestellt werden kann. Der Ausdruck 3 * (4 + 5) kann in Prolog zum Beispiel folgendermaßen dargestellt werden:

times(3,plus(4,5))

und der Ausdruck 3 * 4 + 5:

plus(5,times(3,4))

Man sieht, dass diese Form der Darstellung eines arithmetischen Ausdrucks einen Baum repräsentiert und dass keine Klammern nötig sind, die die Gruppierung kennzeichnen. All die Regeln, die die Klammern enthalten, sind deswegen nicht erforderlich. Dass sind Regeln 6 und 13. Die Regeln 1 und 2 können auch eliminiert werden, da Prolog automatisch den Wert einer Zahl berechnet.

Wir überlegen uns, wie man die restlichen Reduktionsregeln implementieren könnte. Wir können eine allgemeine Reduktionsregel folgendermaßen schreiben:
reduziere(X,Y) :- ...
Wobei X ein arithmetischer Ausdruck ist und Y das Resultat eines Reduktionsschrittes.

Die Regel 3 kann dann wie folgt aussehen:
reduziere(plus(V1,V2),R) :- integer(V1), integer(v2),!, R is V1 + V2.
Hier testet erstmal das Prädikat integer, ob sein Argument ein Integerwert ist. Dann wird R mit dem Ergebnis der Addition instanziert.

In gleicher Weise kann die Regel 7 implementiert werden:
reduziere(plus(E,E2),plus(E1,E2)) :- reduziere(E,E1).

Die Regel 10:
reduziere(plus(V,E),plus(V,E1)) :- integer(V),!,reduziere(E,E1)

Die Regel 14 stellt ein Problem dar. Wenn wir sie folgendermaßen schreiben:
reduziere(E,E2) :- reduziere(E,E1), reduziere(E1,E2).
erhalten wir eine Rekursion, die nicht abbricht. Wir müssen daher eine Unterscheidung machen zwischen einem einzelnen Reduktionsschritt - reduziere, und der mehrfachen Reduktion - reduziere_alles. So können wir jetzt die Regel 14 mit Hilfe von zwei Regeln implementieren (die erste Regel ist die Abbruchsbedingung für die Rekursion):
reduziere_alles(E,V) :- integer(V),!.
reduziere_alles(E,E2) :- reduziere(E,E1), reduziere_alles(E1,E2).


... [Seminar Programmierkonzepte und -sprachen] ... [↑ Gliederung] ... [← Die Opeartionale Semantik der Beispielsprache] ... [→ Literaturverzeichnis] ...