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
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:
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:
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] ...