Eine Beispielsprache


... [Seminar Programmierkonzepte und -sprachen] ... [↑ Gliederung] ... [← Eine Beispielsprache] ... [→ Operationelle Semantik der Beispielsprache] ...

Übersicht: eine Beispielsprache


Arithmetische Ausdrücke

Syntax:

expr ::= expr '+' term | expr '-' term | term
term ::= term '*' factor | factor
factor ::= '('expr')' | number
number ::= number digit | digit
digit ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'

Beispiel:
2 + 3 * 4, (2 + 3) * 4

Semantik:
Der Wert des Ausdrucks - 14, 20


Zuweisungen

Syntax:

factor ::= '('expr')' | number | identifier
programm ::= stmt-list
stmt-list ::= stmt ';' stmt-list | stmt
stmt ::= identifier ':=' expr
identifier ::= identifier letter | letter
letter ::= 'a'|'b'|'c'|...|'z'

Beispiel:
a := 2 + 3;
b := a * 4;
a := b - 5;

Semantik:
Die Semantik dieses Programms wird durch die Menge von Werten, die den dazugehörigen Bezeichnern zugeordnet sind, repräsentiert.

Die Zuordnung der Attribute (in unserem Fall sind es die Integerwerte) zu den Namen (Bezeichner) wird Bindung genannt. Die Bindungen werden vom Übersetzer verwaltet, indem er Datenstrukturen erzeugt, die die Informationen beinhalten. Die genauen Details über die Datenstrukturen sind für uns nicht von Interesse. Wir werden sie einfach als eine Funktion betrachten, die die Bindung der Attributte an die Namen ausdruckt.
Man schreibt:

Sprechweise: Funkfion f von Namen nach Attribute.

Unsere Menge ist nichts anderes als die als eine Funktion von Bezeichner nach Integerwerte. Wir nennen diese Funktion Environment oder auch Umgebung. Wir schreiben:

Die Funktion Environment bildet die Menge der Bezeichner auf die Menge der Integerwerte vereinigt mit der Menge mit nur einem Element - undef, der einem Bezeichner zugeordnet wird, falls diesem noch kein Integerwert durch eine Zuweisung zugeordnet wurde. Für unser Beispielprogramm kann die Environment-Funktion folgendermaßen definiert werden:

Um das Hinzufügen eines neuen Wertes n für einen Bezeichner I zur Umgebung benutzen wir folgende Notation:

Die Funktionsdefinition:

Und schließlich die Notation für Leere Umgebung:

Die Funktionsdefinition:


Kontroll-Anweisungen

Syntax:

stmt ::= assign-stmt | if-stmt | while-stmt
assign-stmt ::= identifier ':=' expr
if-stmt ::= 'if' expr 'then' stmt-list 'else' stmt-list 'fi'
while-stmt ::= 'while' expr 'do' stmt-list 'od'

Beispiel:
n := 0 - 5;
if n then i := n else i :=0 - n fi;
fact := 1;
while i do
          fact := fact * i;
          i := i - 1;
          od

Die Semantik:
Die Bedeutung von if-stmt ist, dass zuerst die expr in der aktuellen Umgebung ausgewertet werden muss. Wird expr zu einem Wert größer 0 ausgewertet, wird die stmt-list nach dem 'then' ausgeführt, wenn nicht wird stmt-list nach 'else' ausgeführt.
Bei while-stmt ist es ähnlich. Solange die expr zu einem Wert größer 0 ausgewertet wird, wird die stmt-list ausgeführt und die expr neu ausgewertet. Die Semantik des Beispielprogramms ist durch folgende Umgebung gegeben:


Vereinfachte Syntax

Bei der Semantikdefinition orientieren wir uns an der Syntax. Wir werden aber eine vereinfachte Version von der eben vorgestellten Syntax benutzen. Da wir annehmen können, dass der Syntaxbaum des Programms bereits vorliegt und da die Semantik nur für syntaktisch korrekte Konstrukte definiert werden darf, kann für die Semantikdefinition auch eine mehrdeutige Grammatik benutzt werden. Weiter werden die nichtterminalen Symbole durch einzelne Buchstaben ersetzt. Diese Art der Syntaxspezifikation wird auch abstrakte Syntax genannt. Die abstrakte Syntax für unsere Beispielsprache sieht folgendermaßen aus:

P : Programm
L : Statement-list
S : Statement
E : Expression
N : Number
D : Digit
I : Identifier
A : Letter

Die Buchstaben auf der rechten Seite der Syntax-Darstellung müssen durchnummeriert werden, wenn sie die selbe Syntaktische Einheit repräsentieren. Damit können wir die jeweilige Wahl kennzeichnen. Ein weiterer wichtiger Punkt ist auch, dass die terminalen Symbole in Hochkommata eingeschlossen sind, denn wir müssen zwischen dem Symbol '+' für Addition und der Operation Addition + unterscheiden können.

... [Seminar Programmierkonzepte und -sprachen] ... [↑ Gliederung] ... [← Eine Beispielsprache] ... [→ Operationelle Semantik der Beispielsprache] ...