Interpréteur d’expressions arithmétiques (unaire → décimal)

4 rubans

20 états

Cette machine prend en entrée une expression arithmétique avec les nombres en unaire, c’est à dire générée par la grammaire suivante:

e,f ::= nb | (e + f) | (e * f)

Où nb est la représentation unaire d’un nombre: le nombre n est représentée par une séquence de 1 de longueur n. Par exemple, l’expression 2 × 3 s’écrit (11 * 111). Notez que 0 (zéro) s’écrit comme une chaîne vide, puisqu’il s’agit d’une séquence de 1 de longueur 0. On écrit donc 0 + (2 × 0) comme ceci : ( + ( 11 * ) ).

La machine calcule le résultat de l’expression donnée en entrée, et le convertit en décimal.

Pour cela, la machine procède comme suit.

Tout d’abord, elle transforme son entrée, pour la mettre en notation polonaise (états parser et parser.retour) sur le ruban 4.
Ensuite, la machine effectue le calcul, en maintenant sur le ruban 3 une pile d’arguments. À chaque opération, on dépile les deux premiers arguments, on calcule le résultat (en utilisant les rubans 1 et 2 si besoin pour le calcul). Le résultat est devient l’argument sur le sommet de la pile.
Enfin, on convertit le résultat en décimal. Pour cela, on écrit 0sur le premier ruban, puis :
1. on efface le premier 1 du ruban 3;
2. on incrémente le nombre écrit sur le premier ruban;
3. on tente de répéter l’opération.
Lorsequ’on voit un 0sur le ruban 3, on a notre résultat!

Simulateur

Spécification de la machine

nom     : Interpréteur
initial : début
final   : fin
sortie  : 1

// On initialise les rubans 2 et 4 avec un 0,
// représentant le fond d'une pile.  
début,[_1(],_,_,_
parser,$1,0,_,0,-,>,-,<

// 1. Mise en notation polonaise
// Les parenthèses ouvrantes ajoutent des ? sur une pile
// que l'on maintient sur le ruban 2.
parser,(,_,_,_
parser,_,?,_,_,>,>,-,-

// Les 1 sont transcrits directement sur le ruban 4.
parser,1,_,_,_
parser,_,_,_,1,>,-,-,<

// Lorsequ'une opération est détectée, on écrit un 0 sur
// le ruban 4 (pour séparer les deux opérandes), ...
parser,[+*],_,_,_
parser,$1,_,_,0,-,<,-,<

// ... on recherche le ? le plus récent sur le ruban 2...
parser,[+*],[+*],_,_
parser,$1,$2,_,_,-,<,-,-

// ... et on le remplace par l'opérateur en question.
parser,[+*],?,_,_
parser.retour,$1,$1,_,_,-,>,-,-

// On prend soin ensuite de replacer la tête de lecture au
// sommet de la pile, c'est à dire à droite. 
parser.retour,[+*],[+*],_,_
parser.retour,$1,$2,_,_,-,>,-,-

parser.retour,[+*],_,_,_
parser,_,_,_,_,>,-,-,-

// Pour une parenthèse fermante, on regarde l'opérateur au
// sommet de la pile...
parser,),_,_,_
parser,_,_,_,_,-,<,-,-

// ... et on le recopie sur le ruban 4.
parser,_,[+*],_,_
parser,_,_,_,$2,>,-,-,<

// Une fois l'entrée lue en entier...
parser,_,_,_,_
parser,_,_,_,_,-,<,-,-

// ... et on efface le 0 de fond de pile du ruban 2.
parser,_,0,_,_
calcul.retour,_,_,_,_,-,-,-,>

// 2. Calcul
// Avant le calcul à proprement parler, on positionne
// la tête de lecture du ruban 4 tout à droite de
// l'expression transformée.
calcul.retour,_,_,_,[01+*]
calcul.retour,_,_,_,$4,-,-,-,>

calcul.retour,_,_,_,_
calcul,_,_,_,_,-,-,-,<

// Le calcul procède en lisant le ruban 4
// de droite à gauche. Les 0 et les 1 sont
// recopiés sur le ruban 3.
calcul,_,_,_,[01]
calcul,_,_,$4,_,-,-,<,<

// Lorsequ'on lit un opérateur, on va sur l'état
// correspondant, pour effectuer le calcul spécifié.
calcul,_,_,_,+
addition,_,_,_,_,-,-,>,-

calcul,_,_,_,*
mult,_,_,_,_,-,-,>,-

// 3. Addition
// L'addition des deux premiers nombres de la pile
// est très simple. Si le premier argument est nul,
// i.e. la pile commence par un 0, alors il suffit
// d'effacer ce symbole.
addition,_,_,0,_
calcul,_,_,_,_,-,-,-,<

// Sinon, on efface le premier 1, ...
addition,_,_,1,_
addition.arg1,_,_,_,_,-,-,>,-

// ... on cherche le 0 séparant premier et second argument...
addition.arg1,_,_,1,_
addition.arg1,_,_,1,_,-,-,>,-

// ... et on le remplace par un 1.
addition.arg1,_,_,0,_
addition.fin,_,_,1,_,-,-,<,-

// Il ne reste ensuite qu'à repositionner la tête de lecture.
addition.fin,_,_,1,_
addition.fin,_,_,1,_,-,-,<,-

addition.fin,_,_,_,_
calcul,_,_,_,_,-,-,-,<

// 4. Multiplication
// Si le premier argument est nul, il convient de renvoyer 0,
// et donc d'effacer le 0 séparant les deux arguments, ...
mult,_,_,0,_
mult.efface,_,_,_,_,-,-,>,-

// ... ainsi que le deuxième argument lui-même.
mult.efface,_,_,1,_
mult.efface,_,_,_,_,-,-,>,-

mult.efface,_,_,0,_
calcul,_,_,0,_,-,-,<,<

// Dans le cas contraire, on déplace le premier argument sur
// le ruban 2, ...
mult,_,_,1,_
mult.arg1,_,1,_,_,-,>,>,-

mult.arg1,_,_,1,_
mult.arg1,_,1,_,_,-,>,>,-

// ... puis le deuxième argument sur le ruban 1.
mult.arg1,_,_,0,_
mult.arg2,_,_,_,_,-,-,>,-

mult.arg2,_,_,1,_
mult.arg2,1,_,_,_,>,-,>,-

// Ensuite, on commence une boucle.
mult.arg2,_,_,0,_
mult.boucle,_,_,0,_,<,-,<,-

// À chaque itération, on efface le 1 le plus à droite
// du premier ruban, ...
mult.boucle,1,_,_,_
mult.recopier,_,_,_,_,-,<,-,-

// ... on recopie le second ruban sur le troisième...
mult.recopier,_,1,_,_
mult.recopier,_,1,1,_,-,<,<,-

// ... et on se repositionne sur le second ruban.
mult.recopier,_,_,_,_
mult.retour,_,_,_,_,-,>,-,-

mult.retour,_,1,_,_
mult.retour,_,1,_,_,-,>,-,-

mult.retour,_,_,_,_
mult.boucle,_,_,_,_,<,-,-,-

// Lorsque le premier ruban est vidé, on efface le second...
mult.boucle,_,_,_,_
mult.fin,_,_,_,_,-,<,-,-

mult.fin,_,1,_,_
mult.fin,_,_,_,_,-,<,-,-

// ... et on poursuit le calcul.
mult.fin,_,_,_,_
calcul,_,_,_,_,-,-,-,<

// 5. Conversion unaire -> décimal.
// Lorsque le calcul est fini, le ruban 3 contient
// le résultat en unaire, avec un zéro à droite,
// et la tête de lecture tout à gauche. Les autres
// rubans sont vides.
// Pour convertir le résultat en notation décimale,
// on initialise le premier ruban avec 0, ...
calcul,_,_,_,_
convertir,0,_,_,_,>,-,>,-

// ... puis, on entre dans une boucle.
// À chaque itération, on efface le 1 le plus à gauche
// du ruban 3, ...
convertir,_,_,1,_
incrémenter,_,_,_,_,<,-,-,-

// ... et on incrémente le résultat sur le ruban 1.
// Pour les chiffres de 0 à 8, il s'agit simplement
// de remplacer le chiffre par son successeur, ...
incrémenter,0,_,_,_
incr.retour,1,_,_,_,>,-,-,-

incrémenter,_,_,_,_
incr.retour,1,_,_,_,>,-,-,-

incrémenter,1,_,_,_
incr.retour,2,_,_,_,>,-,-,-

incrémenter,2,_,_,_
incr.retour,3,_,_,_,>,-,-,-

incrémenter,3,_,_,_
incr.retour,4,_,_,_,>,-,-,-

incrémenter,4,_,_,_
incr.retour,5,_,_,_,>,-,-,-

incrémenter,5,_,_,_
incr.retour,6,_,_,_,>,-,-,-

incrémenter,6,_,_,_
incr.retour,7,_,_,_,>,-,-,-

incrémenter,7,_,_,_
incr.retour,8,_,_,_,>,-,-,-

incrémenter,8,_,_,_
incr.retour,9,_,_,_,>,-,-,-

// ... et pour le chiffre 9, on le remplace par 0
// et on essaie d'incrémenter à partir de la position
// suivante (pour propager la retenue).
incrémenter,9,_,_,_
incrémenter,0,_,_,_,<,-,-,-

// L'itération se termine en repositionnant la tête de
// lecture du premier ruban à droite du résultat.
incr.retour,[0123456789],_,_,_
incr.retour,$1,_,_,_,>,-,-,-

incr.retour,_,_,_,_
convertir,_,_,_,_,-,-,>,-

// Lorsque le zéro à droite du résultat sur le ruban 3
// est atteint, le calcul est terminé.
convertir,_,_,0,_
fin,_,_,_,_,<,-,-,-

Paul Brunet

Interpréteur d’expressions arithmétiques (unaire → décimal)

Simulateur

Spécification de la machine

Messages de sortie du compilateur