Test de correction syntaxique d’expressions arithmétiques

2 rubans

5 états

Cette machine vérifie si son entrée est 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 * ) ).

Une expression mal formée a généralement un défaut de parenthèsage: soit à cause d’une incohérence entre le nombre de parenthèses et celui d’opérateurs (par exemple (1+11+111) ou (1)), soit plus simplement parceque des parenthèses sont ouvertes sans être fermées (1+1, ou fermées sans avoir été ouvertes 1+1).

Simulateur

Spécification de la machine

name:Test de correction syntaxique init:test0 accept:testOK // La machine parcourt son entrée de gauche à droite, // en maintenant une pile sur le second ruban. // À chaque parenthèse ouvrante, un 1 est déposé sur la pile. // Un symbole 1 sur la pile représente donc une parenthèse // ouvrante pour laquelle on n'a pas encore trouvé // l'opérateur associé. test0,(,_ test0,(,1,>,> // En lisant un opérateur ou une parenthèse fermante, // on va inspecter la pile. test0,[+*)],_ test1,$1,_,-,< // Pour un opérateur, on veut trouver un 1 au sommet // de la pile, et le remplacer par un 2. Un symbole 2 sur // la pile représente donc une parenthèse ouvrante pour // laquelle on a déjà trouvé l'opérateur associé. test1,[+*],1 test0,$1,2,>,> // Pour une parenthèse fermante, on veut trouver un 2 // au sommet de la pile. Si c'est le cas, on l'efface, // puisque la sous-expression qui lui correspond est // maintenant complète. test1,),2 test0,),_,>,- // En lisant un 1, on vérifie que l'on est dans un des // deux cas de figure suivants: test0,1,_ test2,1,_,>,- test2,1,_ test2,1,_,>,- // 1. soit on lit un nombre seul // (i.e. l'entrée était de la forme `11...1`) test2,_,_ test4,_,_,<,< // 2. soit le nombre lu est un argument dans une opération. // Dans ce dernier cas, on vérifie la validité de l'opérateur // ou de la parenthèse fermante comme précédemment. test2,[+*)],_ test1,$1,_,-,< // Une fois l'entrée lue en entier, on repositionne // la tête de lecture... test0,_,_ test4,_,_,<,< test4,[1+*()],_ test4,$1,_,<,- // ... et on accepte l'entrée. test4,_,_ testOK,_,_,>,-

Messages de sortie du compilateur

https://machines.brunet-zamansky.fr