Sémantique opérationnelle

En informatique, la sémantique opérationnelle est l'une des approches qui servent à donner une signification aux programmes informatiques d'une manière rigoureuse, mathématiquement parlant (voir Sémantique des langages de programmation).

Une sémantique opérationnelle d'un langage de programmation particulier décrit comment chaque programme valide du langage doit être interprété en termes de suite d'états successifs dans la machine.

Cette suite d'états est la signification du programme.

Dans le cas d'un programme fonctionnel, l'état final d'une suite qui termine donne la valeur de retour du programme. Dans le cas général, il peut y avoir plusieurs suites de calculs et plusieurs valeurs de retour pour un seul programme, parce que celui-ci pourrait être non déterministe.

Un des moyens les plus courants pour définir rigoureusement une sémantique opérationnelle est de fournir un système de transition d'états rendant compte du comportement attendu du programme considéré. Une telle définition autorise une analyse formelle du langage, permettant l'étude de relations entre les programmes. Parmi les relations importantes, les pré-ordres de simulation et les bisimulations sont très utiles dans le cadre du parallélisme.

Définir une sémantique opérationnelle au travers d'un système de transition se fait habituellement en donnant une définition inductive de l'ensemble des transitions possibles. Habituellement, cela prend la forme d'un ensemble de règles d'inférence définissant les transitions valides du système. Le système devient ainsi représentable sous la forme d'un arbre de dérivation des états du programme lors de l’exécution.

La sémantique opérationnelle est reliée à la sémantique dénotationnelle au travers du concept d'abstraction.

Principe généraux

La syntaxe d'un langage de programmation définit l'ensemble des programmes acceptés par le compilateur lors de la première phase. La sémantique quant à elle vise à donner une interprétation aux programmes construit par cette grammaire. Elle définit des règles de dérivations qui indiquent comment les instructions du langage modifient l'état de la mémoire.

État mémoire

Un état mémoire est noté $\sigma$. C'est une fonction partielle qui à l'ensemble des variables associe leurs valeurs respectives.

Fonction sémantique

La syntaxe définit les suites de caractères pouvant être interprétées comme des programmes valides. Ces caractères ne sont pas des nombres, mais des expressions rationnelles (ou suite de token lors de la compilation). Ces dernières doivent donc être traduites en nombre pour pouvoir être stockées dans la machine.

Exemple d'implémentation d'une sémantique opérationnelle

Langage "While"

Le langage while est l'exemple typique pour expliquer les concepts principaux d'une sémantique opérationnelle pour un langage de programmation turing-equivalent. Il implémente les instructions de base (conditionnelles et boucles), et les types principaux (booléen, variables, entiers naturels). Des versions plus avancées de ces langages existent et introduisent les sémantiques des procédures et les notions de scope dynamique et statique (language proc & bloc). Ces deux langages ont cependant une implémentation bien plus complexe.

Syntaxe

Définition des catégories syntaxiques

On définit tout d'abord les différents ensembles de catégories syntaxiques que le langage doit être capable de représenter. Ces définitions peuvent être inductives, ou sous forme de grammaires.

Nombre : n $\in$ Num = {0,...,9}+

Variable : x $\in$ Var

Expression arithmétique :

a $\in$ Aexp

a  ::= n | x | a $\bigoplus$ a tel que $\bigoplus$ $\in$ { +, -, /, * }

Expression booléenne :

b $\in$ Bexp

b  ::= true | false | $\neg$ b | b $\bigoplus$ b tel que $\bigoplus$ $\in$ { $\land ,\lor$ }

Instructions :

S := x:=a | skip

| S ; S

| if b then S else fi

| while b do S od

Ou S $\in$ Statement est un non terminal.

Sémantique

La définition sémantique consiste a définir un ensemble de règles de transition permettant de passer d'un état mémoire $\sigma$. à un état mémoire $\sigma$'.

Fonction sémantique

Une fonction sémantique associe un élément appartenant à une catégorie syntaxique à son équivalent mathématique.

Articles connexes

• Machine de Krivine
• Machine SECD
• Substitution explicite