Beispiel : Integer Arithmetik


[Die Semantischen Funktionen] ... [Der Zustand]
Um das eben besprochene zu vertiefen soll hier eine einfache Integer Arithmetik definiert werden, die es erlaubt jeden Integer Ausdruck auszuwerten, der auf den grundlegenden Operationen beruht. Dazu definieren wir zunächst die vollständige Semantik, um dann einige Beispielausdrücke auszuwerten.

Syntaktische Domänen
E : Expression
N : Number
D : Digit

E -> E1 '+' E2 | E1 '-' E2 | E1 '*' E2 | E1 '/' E2 | E1 % E2 | | N
N -> N D | D
D -> '0' | '1' | ... | '9'

Semantische Domänen Domäne v: Integer = {..., -2, -1, 0, 1, 2, ...}
Operationen
+:Integer x Integer->Integer
-:Integer x Integer->Integer
*:Integer x Integer->Integer
/:Integer x Integer->Integer
%:Integer x Integer->Integer

Semantische Funktionen

E : Expression -> Integer
E[[E1 '+' E2]] = E[[E1]] + E[[E2]]
E[[E1 '-' E2]] = E[[E1]] - E[[E2]]
E[[E1 '*' E2]] = E[[E1]] * E[[E2]]
E[[E1 '/' E2]] = E[[E1]] / E[[E2]]
E[[E1 '%' E2]] = E[[E1]] % E[[E2]]
E[[N]] = N[[N]]

N : Number -> Integer
N[[ND]] = 10 * N[[N]] + N[[D]]
N[[D]] = D[[D]]

D : Digit -> Integer
D[['0']] = 0
D[['1']] = 1
D[['2']] = 2
D[['3']] = 3
D[['4']] = 4
D[['5']] = 5
D[['6']] = 6
D[['7']] = 7
D[['8']] = 8
D[['9']] = 9

Nachdem die denotationelle Definition abgeschlossen ist kann nun ein Beispielausdruck ausgewertet werden.

E [[ '('2 '+' 4')' '*' 4 ]]
= E [[ 2 '+' 4 ]] * N [[ 4 ]]
= ( E [[ 2 ]] + E [[ 4 ]] ) * D [[ 4 ]]
= ( N [[ 2 ]] + N [[ 4 ]] ) * 4
= ( D [[ 2 ]] + D [[ 4 ]] ) * 4
= ( 2 + 4 ) * 4
= 6 * 4
= 24

[Zurück] ... [Nach oben] ... [Weiter]