Il linguaggio

Prima di definire la semantica, occorre porre le basi del linguaggio da definire, per questo motivo andremo a costruire un modello matematico per programmi scritti in tale linguaggio.

Insiemi di base

Come insiemi di simboli terminali useremo:

• Booleani: $\{tt,ff\}$ metavariabili $t, t_1, t'\in T$;
• Naturali: $\{0,1,...\}$ metavariabili $n,m,p\in\N$;
• Variabili: $\{a,b,\dots,x\}$ metavariabili $v\in Var$.

Dove le metavariabili sono una qualsiasi variabile dell'insieme, senza specificare se si stia usando a, b, un numero, ecc.

Insiemi derivati

Partendo dai 3 insiemi di base, possiamo derivare tramite BNF i seguenti insiemi:

• Espressioni aritmetiche $e\in Exp$ $e:=m\space|\space v\space|\space e+e\space|\space e-e\space|\space e*e$
• Espressioni booleane $b\in Bexp$ $b:=t\space|\space e=e\space|\space b\space or\space b\space|\space\sim b$
• Comandi $c\in Com$ $c:= skip\space|\space v:=e\space|\space c;c\space|\space while\space b\space do\space c\space|\space if\space b\space then\space c\space else\space d$

<aside> 💡 Si noti che al momento la sintassi è ancora ambigua, per questo proseguiamo a definire la semantica.

</aside>

Semantica

Per ogni categoria sintattica sopra definita ($Exp, Bexp, Com$) si definisce un modello detto sistema di transizione.

Def.: Un sistema di transizione è una tripla $<\Gamma, T,\rarr>$ dove:

• $\Gamma$ è l'insieme degli stati possibili;
• $T\sube\Gamma$ è l'insieme degli stati terminali;