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

4 rubans

30 é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 binaire.

Pour cela, la machine procède comme suit.

Tout d’abord, elle transforme son entrée, pour la mettre en notation polonaise inverse 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 binaire. 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

name:interpreter
init:trad0
accept:interprOK
output:1

trad0,1,_,_,_
trad0,_,_,1,_,>,-,>,-

trad0,(,_,_,_
trad0,_,_,_,_,>,-,-,-

trad0,+,_,_,_
trad0,_,+,0,_,>,>,>,-

trad0,*,_,_,_
trad0,_,*,0,_,>,>,>,-

trad0,),_,_,_
trad1,),_,_,_,-,<,-,-

trad1,),+,_,_
trad0,_,_,+,_,>,-,>,-

trad1,),*,_,_
trad0,_,_,*,_,>,-,>,-

trad0,_,_,_,_
trad2,_,_,_,_,-,-,<,-

trad2,_,_,1,_
trad2,1,_,_,_,<,-,<,-
trad2,_,_,0,_
trad2,0,_,_,_,<,-,<,-
trad2,_,_,+,_
trad2,+,_,_,_,<,-,<,-
trad2,_,_,*,_
trad2,*,_,_,_,<,-,<,-
trad2,_,_,_,_
exec0,_,_,_,_,>,-,-,-

exec0,1,_,_,_
exec1,1,0,_,_,-,>,-,-
exec0,0,_,_,_
exec1,0,0,_,_,-,>,-,-
exec0,_,_,_,_
interprOK,0,_,_,_,-,-,-,-
exec1,1,_,_,_
exec1,_,1,_,_,>,>,-,-

exec1,0,_,_,_
exec1,_,0,_,_,>,>,-,-

exec1,+,_,_,_
exec_add,_,_,_,_,-,<,-,-

exec_add,_,1,_,_
exec_add,_,1,_,_,-,<,-,-

exec_add,_,0,_,_
exec_add2,_,0,_,_,-,<,-,-

exec_add2,_,1,_,_
exec_add2,_,1,_,_,-,<,-,-

exec_add2,_,0,_,_
add0,_,0,_,_,-,>,-,-

exec1,*,_,_,_
exec_mult,_,_,_,_,-,<,-,-

exec_mult,_,1,_,_
exec_mult,_,1,_,_,-,<,-,-

exec_mult,_,0,_,_
exec_mult2,_,0,_,_,-,<,-,-

exec_mult2,_,1,_,_
exec_mult2,_,1,_,_,-,<,-,-

exec_mult2,_,0,_,_
mult0,_,0,_,_,-,>,-,-

mult0,_,1,_,_
mult0,_,_,1,_,-,>,>,-

mult0,_,0,_,_
mult1,_,_,_,_,-,>,-,-

mult1,_,1,_,_
mult1,_,_,_,1,-,>,-,>

mult1,_,_,_,_
mult5,_,_,_,_,-,<,-,-

mult5,_,_,_,_
mult5,_,_,_,_,-,<,-,-

mult5,_,0,_,_
mult2,_,0,_,_,-,>,-,<

mult2,_,_,_,1
mult3,_,_,_,_,-,-,<,-

mult2,_,_,_,_
mult6,_,_,_,_,-,-,<,-

mult3,_,_,1,_
mult3,_,1,1,_,-,>,<,-

mult3,_,_,_,_
mult4,_,_,_,_,-,-,>,-

mult4,_,_,1,_
mult4,_,_,1,_,-,-,>,-

mult4,_,_,_,_
mult2,_,_,_,_,-,-,-,<

mult6,_,_,1,_
mult6,_,_,_,_,-,-,<,-

mult6,_,_,_,_
exec1,_,_,_,_,>,-,-,-

add0,_,1,_,_
add0,_,1,_,_,-,>,-,-

add0,_,0,_,_
add1,_,0,_,_,-,>,-,-

add1,_,1,_,_
add1,_,1,_,_,-,>,-,-

add1,_,_,_,_
add2,_,_,_,_,-,<,-,-

add2,_,1,_,_
add3,_,_,_,_,-,<,-,-

add2,_,0,_,_
add4,_,_,_,_,-,<,-,-

add3,_,1,_,_
add3,_,1,_,_,-,<,-,-

add3,_,0,_,_
add4,_,1,_,_,-,<,-,-

add4,_,1,_,_
add4,_,1,_,_,-,<,-,-

add4,_,0,_,_
addOK,_,0,_,_,-,>,-,-

addOK,_,1,_,_
addOK,_,1,_,_,-,>,-,-

addOK,_,_,_,_
exec1,_,_,_,_,>,-,-,-

exec1,_,_,_,_
exec_res,_,_,_,_,-,<,-,-

exec_res,_,1,_,_
exec_res,1,_,_,_,<,<,-,-

exec_res,_,0,_,_
conv0,_,_,_,_,>,-,-,-

conv0,1,_,_,_
conv0,_,1,_,_,>,>,-,-
conv0,_,_,_,_
conv1,0,_,_,_,<,<,-,-

conv1,_,1,_,_
conv_incr0,_,_,_,_,>,-,-,-

conv_incr0,0,_,_,_
conv_incr0,0,_,_,_,>,-,-,-

conv_incr0,1,_,_,_
conv_incr0,1,_,_,_,>,-,-,-

conv_incr0,_,_,_,_
conv_incr1,_,_,_,_,<,-,-,-

conv_incr1,0,_,_,_
conv_incr2,1,_,_,_,<,-,-,-

conv_incr1,1,_,_,_
conv_incr1,0,_,_,_,<,-,-,-

conv_incr1,_,_,_,_
conv_incrOK,1,_,_,_,<,-,-,-

conv_incr2,0,_,_,_
conv_incr2,0,_,_,_,<,-,-,-

conv_incr2,1,_,_,_
conv_incr2,1,_,_,_,<,-,-,-

conv_incr2,_,_,_,_
conv_incrOK,_,_,_,_,-,-,-,-

conv_incrOK,_,_,_,_
conv1,_,_,_,_,-,<,-,-

conv1,_,_,_,_
interprOK,_,_,_,_,>,-,-,-

Paul Brunet

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

Simulateur

Spécification de la machine

Messages de sortie du compilateur