Machine virtuelle pour le projet de compilation

1 Description

1.1 Organisation de la machine

Il s'agit d'une machine à pile (par opposition à une machine à registres), composée d'une pile d'exécution, d'une pile d'appels, d'un code, de deux tas et de quatre registres.

La pile d'exécution contient des valeurs, qui peuvent être des entiers, des réels ou des adresses.

Les deux tas contiennent respectivement des chaînes de caractères et des blocs structurés, tous deux repérés par leurs adresses. Un bloc structuré contient un certain nombre de valeurs (de la même nature que celles se trouvant sur la pile).

Une adresse peut être de quatre natures différentes : vers le code, vers la pile, vers un bloc structuré dans le tas ou vers une chaîne.

Trois registres permettent d'accéder à différentes parties de la pile :

Le registre sp (stack pointer) repère le sommet courant de la pile, il pointe sur la première case libre de la pile.
Le registre fp (frame pointer) repère l'adresse de base des variables locales.
Le registre gp contient l'adresse de base des variables globales.

La machine comporte un registre pc qui pointe sur l'instruction courante du code à exécuter.

La pile d'appels permet de sauvegarder les appels : elle contient des couples de pointeurs, l'un sauvegardant le registre d'instructions pc et l'autre le registre fp.

1.2 Instructions

Les instructions sont désignées par un nom et peuvent prendre un ou deux arguments. Ceux-ci peuvent être:

des constantes entières,
des constantes réelles,
des chaînes de caractères entre guillemets avec les mêmes conventions que le langage C pour ce qui concerne les caractères spéciaux \", \n, \\,
une étiquette symbolique désignant un emplacement dans le code.

1.2.1 Terminologie

On utilisera les conventions suivantes:

Empiler une valeur x signifie stocker x à l'emplacement P[sp] et incrémenter sp de 1.
Empiler n fois une valeur x signifie itérer n fois l'opération précédente.
Dépiler n valeurs revient à décrémenter de n la valeur de sp.
Le sommet de la pile représente la dernière valeur stockée dans la pile soit P[sp - 1], le sous-somment de la pile représente l'avant dernière valeur stockée dans la pile soit P[sp - 2].

1.2.2 Opérations de base

Les opérations arithmétiques ou flottantes s'effectuent entre le sommet et le sous-sommet de la pile, les deux arguments sont dépilés et le résultat est empilé à la place. Le résultat des opérations de comparaison est un entier qui vaut 0 ou 1. L'entier 0 représente la valeur booléenne "faux" tandis que 1 représente la valeur booléenne "vrai".

Opérations sur les entiers

Instruction	Description
ADD	dépile n puis m qui doivent être entiers et empile le résultat m+n
SUB	dépile n puis m qui doivent être entiers et empile le résultat m-n
MUL	dépile n puis m qui doivent être entiers et empile le résultat m× n
DIV	dépile n puis m qui doivent être entiers et empile le résultat m/n
MOD	dépile n puis m qui doivent être entiers et empile le résultat m mod n
NOT	dépile n qui doit être un entier et empile le résultat de n=0
INF	dépile n puis m qui doivent être entiers et empile le résultat m < n
INFEQ	dépile n puis m qui doivent être entiers et empile le résultat m £ n
SUP	dépile n puis m qui doivent être entiers et empile le résultat m > n
SUPEQ	dépile n puis m qui doivent être entiers et empile le résultat m ³ n

Opérations sur les réels

Instruction	Description
FADD	dépile n puis m qui doivent être réels et empile le résultat m+n
FSUB	dépile n puis m qui doivent être réels et empile le résultat m-n
FMUL	dépile n puis m qui doivent être réels et empile le résultat m× n
FDIV	dépile n puis m qui doivent être réels et empile le résultat m/n
FINF	dépile n puis m qui doivent être réels et empile le résultat m < n
FINFEQ	dépile n puis m qui doivent être réels et empile le résultat m £ n
FSUP	dépile n puis m qui doivent être réels et empile le résultat m > n
FSUPEQ	dépile n puis m qui doivent être réels et empile le résultat m ³ n

Opérations sur les chaînes

Instruction	Description
CONCAT	dépile n puis m qui doivent être des adresses de chaîne, empile l'adresse d'une chaîne égale à la concaténation de la chaîne d'adresse n et de celle d'adresse m.

Opérations sur le tas

Instruction	Argument	Description
ALLOC	n entier	alloue sur le tas un bloc structuré de taille n et empile l'adresse correspondante
ALLOCN		dépile un entier n, alloue sur le tas un bloc structuré de taille n et empile l'adresse correspondante
FREE		dépile une adresse a et libère le bloc structuré alloué à l'adresse a

Égalité

Le test d'égalité teste que les deux objets (entiers, réels ou adresses) sur la pile sont égaux, Une erreur d'exécution a lieu si les deux objets ne sont pas de même type. Deux chaînes égales sont stockées à la même adresse, cette instruction permet donc de tester de l'égalité de deux chaînes.

Instruction	Description
EQUAL	dépile n puis m qui doivent être de même type et empile le résultat de n=m

Conversions

Différentes instructions permettent de convertir une chaîne de caractères en entier ou réel et réciproquement.

Instruction	Description
ATOI	dépile l'adresse d'une chaîne et empile sa conversion en nombre entier, échoue si la chaîne ne représente pas un entier.
ATOF	dépile l'adresse d'une chaîne et empile sa conversion en nombre réel, échoue si la chaîne ne représente pas un réel.
ITOF	dépile un entier et empile sa conversion en nombre réel.
FTOI	dépile un réel et empile l'entier représentant sa partie entière (obtenue en supprimant les décimales).
STRI	dépile un entier et empile l'adresse d'une chaîne représentant cet entier
STRF	dépile un réel et empile l'adresse d'une chaîne représentant ce réel

1.2.3 Manipuler des données

Si x désigne une adresse dans la pile alors x[n] désigne une adresse située n cases au-dessus.

Empiler

Instruction	Argument	Description
PUSHI	n entier	empile n
PUSHN	n entier	empile n fois la valeur entière 0
PUSHF	n réel	empile n
PUSHS	n chaîne	stocke n dans la zone des chaînes et empile l'adresse
PUSHG	n entier	empile la valeur située en gp[n]
PUSHL	n entier	empile la valeur située en fp[n]
PUSHSP		empile la valeur du registre sp
PUSHFP		empile la valeur du registre fp
PUSHGP		empile la valeur du registre gp
LOAD	n entier	dépile une adresse a et empile la valeur dans la pile ou le tas située en a[n]
LOADN		dépile un entier n, une adresse a et empile la valeur dans la pile ou le tas située en a[n]
DUP	n entier	duplique et empile les n valeurs en sommet de pile
DUPN		dépile un entier n, puis duplique et empile les n valeurs en sommet de pile

Dépiler

Instruction	Argument	Description
POP	n entier	dépile n valeurs dans la pile
POPN		dépile un entier n puis dépile n valeurs dans la pile

Stocker

Instruction	Argument	Description
STOREL	n entier	dépile une valeur et la stocke dans la pile en fp[n]
STOREG	n entier	dépile une valeur et la stocke dans la pile en gp[n]
STORE	n entier	dépile une valeur v et une adresse a, stocke v à l'adresse a[n] dans la pile ou le tas
STOREN		dépile une valeur v, un entier n et une adresse a, stocke v à l'adresse a[n] dans la pile ou le tas

Divers

Instruction	Argument(s)	Description
CHECK	n,p entiers	vérifie que le sommet de la pile est un entier i tel que n £ i £ p, sinon déclenche une erreur
SWAP		dépile n puis m et rempile n puis m

1.2.4 Entrées-Sorties

Les instructions suivantes permettent de gérer les entrées-sorties.

Instruction	Description
WRITEI	dépile un entier et l'imprime sur la sortie standard
WRITEF	dépile un réel et l'imprime sur la sortie standard
WRITES	dépile l'adresse d'une chaîne et imprime la chaîne correspondante sur la sortie standard
READ	lit une chaîne de caractères au clavier, terminée par un retour-chariot, stocke la chaîne (sans le retour-chariot) et empile l'adresse.

1.2.5 Opérations de contrôle

Après l'exécution d'une instruction le registre pc est habituellement incrémenté de 1. Les opérations de contrôle permettent de modifier ce comportement par défaut.

Modification du registre pc

Instruction	Argument	Description
JUMP	label étiquette	affecte au registre pc l'adresse dans le programme correspondant à label qui peut être un entier ou une valeur symbolique.
JZ	label étiquette	dépile une valeur, si elle est nulle affecte au registre pc l'adresse dans le programme correspondant à label sinon incrémente pc de 1.
PUSHA	label étiquette	empile l'adresse dans le code correspondant à l'étiquette label

Procédure

Lors de l'appel de procédure il est nécessaire de sauvegarder les registre d'instructions et de variables locales qui seront restaurées au moment du retour.

Instruction	Description
CALL	dépile une adresse de code a, sauvegarde pc et fp dans la pile des appels, affecte à fp la valeur courante de sp et à pc la valeur a.
RETURN	affecte à sp la valeur courante de fp, restaure de la pile des appels les valeurs de fp et pc et incrémente pc de 1 pour se retrouver à l'instruction suivant celle d'appel.

Le comportement des instructions CALL et RETURN est décrit sur les schémas suivants où seuls les registres modifiés ont été dessinés:

1.2.6 Initialisation et fin

Dans l'état initial, le registre pc pointe sur la première instruction du programme. La pile des appels et la pile d'exécution sont vides. Les registre gp et sp pointent sur la base de la pile d'exécution tandis que fp n'est pas défini. Le registre fp doit être initialisé par l'instruction START qui ne peut être utilisée qu'une seule fois. Les instructions suivantes servent à stopper la machine à la fin du programme ou en cas d'erreur.

Instruction	Argument	Description
START		Affecte la valeur de sp à fp
NOP		ne fait rien.
ERR	x chaîne	déclenche une erreur d'instruction avec le message x.
STOP		arrête l'exécution du programme

2 Réalisation

Une réalisation de la machine virtuelle est fournie, sous la forme de deux programmes vm et gvm.

2.1 Syntaxe concrète

Les programmes pour la machine virtuelle obéissent à la syntaxe décrite ci-dessous.

2.1.1 Conventions lexicales

Espaces, tabulations et retour-chariots constituent les blancs. Les commentaires débutent par // et se poursuivent jusqu'à la fin de la ligne. Les identificateurs obéissent à l'expression régulière áidentñ suivante :

ádigitñ	::=	`0`--`9`
áalphañ	::=	`a`--`z` \| `A`--`Z`
áidentñ	::=	(áalphañ \| `_`) (áalphañ \| ádigitñ \| `_` \| `'`)*

Les constantes entières et réelles sont définies par les expressions régulières suivantes :

áintegerñ	::=	`-`? ádigitñ+
áfloatñ	::=	`-`? ádigitñ+ (`.` ádigitñ)? ((`e` \| `E`) (`+` \| `-`)? ádigit*ñ+)?

avec la convention qu'une constante est réelle seulement si elle n'est pas aussi une constante entière (autrement dit, une constante réelle comporte au moins un point décimal ou un exposant).

Les chaînes de caractères sont délimitées par le caractère ", et peuvent contenir ce même caractère seulement s'il est précédé du caractère \. En d'autres termes, les chaînes obéissent à l'expression régulière suivante :

ástringñ ::= " ([^ "] | \ ")* "

Tous les identificateurs constituant des instructions (voir la syntaxe ci-dessous) sont réservés et peuvent être écrits dans une casse quelconque.

2.1.2 Syntaxe

Les programmes obéissent à la syntaxe donnée figure 1.

ácodeñ ::= áinstrñ*

áinstrñ ::= áidentñ :

| áinstr_atomñ

| áinstr_intñ áintegerñ

| pushf áfloatñ

| (pushs | err) ástringñ

| check áintegerñ , áintegerñ

| (jump | jz | pusha) áidentñ

áinstr_atomñ ::= add | sub | mul | div | mod | not | inf | infeq | sup |

| supeq | fadd | fsub | fmul | fdiv | finf | finfeq | fsup |

| fsupeq | concat | equal | atoi | atof |

| itof | ftoi | stri | strf |

| pushsp | pushfp | pushgp | loadn | storen | swap |

| writei | writef | writes | read | call | return |

| start | nop | stop | allocn | free | dupn | popn |

áinstr_intñ ::= pushi | pushn | pushg | pushl | load |

| dup | pop | storel | storeg | alloc

Figure 1: Syntaxe des programmes

2.2 Utilisation

2.2.1 Machine en mode texte `vm`

Cette machine est destinée à un usage non-interactif, pour obtenir le résultat d'une exécution. Elle s'utilise ainsi

    vm [options] [fichier.vm]

Lorsque le fichier est omis, le code est lu sur l'entrée standard. Les options sont les suivantes :

-dump: affiche quelques informations sur la machine à la fin de l'exécution (valeurs des registres, sommet de la pile, etc.)
-silent: exécution silencieuse : rien n'est affiché pendant l'exécution
-count: affiche le nombre d'instructions exécutées
-ssize entier: fixe la taille de la pile (10000 par défaut)
-csize entier: fixe la taille de la pile d'appels (100 par défaut)

2.2.2 Interface graphique `gvm`

Cette machine est destinée à un usage interactif, pour visualiser l'exécution d'un programme. L'exécution peut se faire pas à pas, ou être lancée jusqu'à l'arrêt du programme, avec mise à jour des différents composants de la machine (animation) ou non (exécution non interactive). Elle s'utilise ainsi

    gvm [options] [fichier.vm]

Les seules options sont -ssize et -csize, similaires à celles de la machine vm.

Seuls les éléments de la pile en dessous de SP sont visualisés (SP a donc pour valeur l'indice de la première ligne vide). La ligne colorée en vert correspond à FP. Les valeurs de SP, FP et GP et PC sont affichées en bas à droite. Une instruction READ déclenche l'ouverture d'une boîte de dialogue pour y saisir une chaîne de caractères, et une instruction d'affichage (WRITEI, WRITEF ou WRITES) a pour effet d'écrire dans la barre située en bas de l'interface.

2.3 Messages d'erreurs

Les différentes erreurs d'exécution possibles sont les suivantes :

Illegal Operand: déclenchée lorsque la ou les valeur(s) sur la pile ne sont pas de la nature attendue
Segmentation Fault: déclenchée pour tout accès à une zone illégale du code, de la pile ou de l'un des deux tas
Stack Overflow: déclenchée pour toute tentative d'addition au sommet d'une pile pleine (pile d'exécution ou pile d'appels)
Division By Zero: déclenchée en cas de division (entière) par zéro
Error "message": déclenchée lorsque l'instruction err est exécutée
Anomaly: cette erreur-là ne doit normalement jamais se produire ; si c'est le cas, merci de le signaler aux enseignants, en joignant autant que possible le programme l'ayant déclenchée.

This document was translated from L^AT_EX by H^EV^EA.

ácodeñ	::=	áinstrñ*
áinstrñ	::=	áidentñ `:`
	\|	áinstr_atomñ
	\|	áinstr_intñ áintegerñ
	\|	`pushf` áfloatñ
	\|	(`pushs` \| `err`) ástringñ
	\|	`check` áintegerñ `,` áintegerñ
	\|	(`jump` \| `jz` \| `pusha`) áidentñ
áinstr_atomñ	::=	`add` \| `sub` \| `mul` \| `div` \| `mod` \| `not` \| `inf` \| `infeq` \| `sup` \|
	\|	`supeq` \| `fadd` \| `fsub` \| `fmul` \| `fdiv` \| `finf` \| `finfeq` \| `fsup` \|
	\|	`fsupeq` \| `concat` \| `equal` \| `atoi` \| `atof` \|
	\|	`itof` \| `ftoi` \| `stri` \| `strf` \|
	\|	`pushsp` \| `pushfp` \| `pushgp` \| `loadn` \| `storen` \| `swap` \|
	\|	`writei` \| `writef` \| `writes` \| `read` \| `call` \| `return` \|
	\|	`start` \| `nop` \| `stop` \| `allocn` \| `free` \| `dupn` \| `popn` \|
áinstr_intñ	::=	`pushi` \| `pushn` \| `pushg` \| `pushl` \| `load` \|
	\|	`dup` \| `pop` \| `storel` \| `storeg` \| `alloc`