Conversion d’expressions arithmétiques (infixe → suffixe)

3 rubans

4 états

Cette machine prend en entrée une expression arithmétique (bien formée) 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 * ) ).

Elle convertit son entrée pour la mettre en notation polonaise inverse, c’est à dire en écrivant une opération a + b comme a b +. Plus précisément, on utilise le symbole 0 comme séparateur entre les deux arguments, et on suffixe le tout de l’opération. Par exemple, l’expression (2+3)× 4, codée par ((11+111)*1111), donnera 110111+01111*.

Simulateur

Spécification de la machine

name:Traducteur infixe-suffixe init:trad0 accept:tradOK output: 1 // Les 1 sont déplacés vers le ruban 3. trad0,1,_,_ trad0,_,_,1,>,-,> // Les parenthèses ouvrantes sont oubliées. // (attention: si l'entrée n'est pas bien formattée, // cette machine ne le détectera pas forcément! // On considère son comportement comme non spécifié // pour les entrées illicites). trad0,(,_,_ trad0,_,_,_,>,-,- // Les opérateurs sont ajoutés à une pile sur le ruban 2, // et en les lisant on ajoute un 0 sur le ruban 3, pour // marquer la séparation entre les deux arguments. trad0,[+*],_,_ trad0,_,$1,0,>,>,> // En voyant une parenthèse fermante... trad0,),_,_ trad1,),_,_,-,<,- // ... on réccupère au sommet de la pile // l'opérateur correspondant. trad1,),[+*],_ trad0,_,_,$2,>,-,> // Lorsque la lecture est terminée, ... trad0,_,_,_ trad2,_,_,_,-,-,< // ... on déplace le résultat du ruban 3 au ruban 1. trad2,_,_,[10+*] trad2,$3,_,_,<,-,< trad2,_,_,_ tradOK,_,_,_,>,-,-

Messages de sortie du compilateur

https://machines.brunet-zamansky.fr