9.7 Un exemple concret

Discutons un exemple concret du monde de l'informatique permettant d'illustrer l'usage de l'instruction CASE. Il s'agit de la conception d'un automate pour l'analyse de constantes réelles. Avant de pouvoir passer au véritable problème, nous avons besoin de quelques explications supplémentaires.

Dès que les instructions d'un langage diffèrent de quelque façon que ce soit de celle du code, elles deviennent incompréhensibles par l'ordinateur. Il faut donc les traduire en une séquence d'instructions en langage-machine. Le programme écrit en un langage de niveau plus élevé que le langage-machine est appelé programme-source, le programme en langage-machine qui lui correspond après traduction est appelé programme-objet ou souvent encore le code, malgré l'ambiguïté de ce terme. Un homme ne pourrait effectuer une telle traduction à une vitesse suffisante, le traducteur doit être un programme et la traduction est donc "automatique". Un compilateur est un tel programme de traduction d'un programme-source en un programme-objet. A la fin de la compilation on obtient le programme-objet équivalant au programme à traduire. Il faudra, dans une autre phase, utiliser ce programme-objet pour obtenir le résultat. Un langage de programmation est dit compilé s'il existe un compilateur pour traduire les programmes écrits en ce langage.

Généralement un compilateur est structuré en plusieurs composantes:

- l'analyseur lexical [angl. scanner];
- l'analyseur syntaxique [angl. parser];
- l'analyseur sémantique;
- le générateur de code.

Les fonctions de chacune de ces composantes sont précisément définies:

• l'analyseur lexical inspecte le programme source, caractère par caractère, élimine les caractères superflus, construit les terminaux à partir de ces caractères et passe à l'analyseur syntaxique;

• l'analyseur syntaxique effectue une analyse syntaxique du programme source en se basant sur les terminaux que lui passe l'analyseur lexical. L'analyseur syntaxique consiste à vérifier si le programme est syntaxiquement correct, c'est-à-dire si la séquence des symboles dans le programme respecte les règles de production de la grammaire du langage;

• l'analyseur sémantique vérifie si le programme syntaxiquement correct l'est aussi sémantiquement. Il effectue l'analyse de la portée des identificateurs et l'analyse des types;

• le générateur de code est la partie du compilateur qui s'occupe de générer le code. Le code généré peut être du code-machine, un code intermédiaire, etc. C'est donc la composante du compilateur qui réalise effectivement la traduction.

Un analyseur lexical est un automate fini déterministe. Rappelons qu'un tel automate est représenté par un 7-tuple de la forme (voir chapitre 1.4):

< S >< A >< Q >< F >< G >< Z0 >< E >

avec:

< S >: ensemble fini des signaux d'entrée;
< A >: ensemble fini des signaux de sortie;
< Q >: ensemble fini des états initiaux;
< F >: application de SxQ dans P(Q);
< G >: application de SxQ dans A;
< Z0 >: état initial, Z0ÎQ;
< E >: ensemble des états finaux.

Ici P(Q) représente une partie de Q.

Un tel automate peut être utilisé, à part dans sa fonction de lire le texte source d'un programme et de reconnaître les terminaux lors de la compilation, pour valider les données d'entrée dans un programme. En général, ces données sont stockées dans le fichier standard d'entrée, puis elles sont évaluées par l'automate. Dans ce paragraphe, nous allons construire un tel automate pour l'entrée validée d'un nombre réel.

En Turbo-Pascal, un nombre réel se construit d'après les règles de production suivantes:

< digit > ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< digit sequence > ::= < digit > { < digit > }
< signed real > ::= [ < sign > ] < unsigned real >
< unsigned real > ::= < digit sequence > < scale factor > |
< digit sequence > "." < digit sequence > [ < scale factor > ]
< sign > ::= [ "+" | "-" ]
< scale factor > ::= "E" | "e" [ < sign > ] < digit sequence >

L'automate correspondant peut être construit comme suit (pour des raisons de simplicité, A et G ne sont pas considérés ici):

< S > ::= tous les caractères imprimables ainsi que eof (end of file)
< Q > ::= Begining (B) | Okay | Error | SignReal (SR) | SignScaleFactor (SSF) | ScaleFactor (SF) | BeforeDecimalPoint (BDP) | AfterDecimalPoint (ADP) | E | e
< Z0 > ::= Begining
< E > ::= Okay | Error

Les règles de passage d'un état à l'autre sont données par l'application F:SxQ ¾>P(Q) décrite dans le tableau ci-dessous.

L'automate décrit par ce tableau peut être facilement implémenté en Turbo-Pascal sous forme d'une procédure. La fonction F à deux arguments est implémentée en utilisant des instructions CASE imbriquées. Le fichier d'entrée est lu caractère après caractère jusqu'à la fin du fichier. Pour ce faire, nous supposons que l'analyseur lexical dispose d'une procédure GetCharacter qui retourne respectivement le caractère suivant ou eof, s'il n'y a plus de caractères.

TYPE
S = Char;
Q = ( B, Error, Okay, SR, SSF, SF, BDP, ADP, E, e, SF );

PROCEDURE ScanReal;
VAR Status: Q;
Ch: S;
BEGIN {ScanReal}
Status := B; {état initial}
WHILE NOT ( Status IN [ Error, Okay ] ) DO BEGIN
GetCharacter( Ch );
CASE Ch OF
'0' .. '9': CASE Status OF
B: Status := BDP;
SSF: Status := BDP;
BDP: Status := BDP;
ADP: Status := ADP;
E, e: Status := SF;
SSF: Status := SF;
SF: Status := SF
END; {-- CASE}
'+', '-': CASE Status OF
B: Status := SR;
SSF: Status := Error;
BDP: Status := Error;
ADP: Status := Error;
E, e: Status := SSF;
SSF: Status := Error;
SF: Status := Error
END; {-- CASE}
'.': CASE Status OF
B: Status := Error;
SSF: Status := Error;
BDP: Status := ADP;
ADP: Status := Error;
E, e: Status := Error;
SSF: Status := Error;
SF: Status := Error
END; {-- CASE}
'E', 'e': CASE Status OF
B: Status := Error;
SSF: Status := Error;
BDP: Status := E;
ADP: Status := E;
E, e: Status := Error;
SSF: Status := Error;
SF: Status := Error
END; {-- CASE}
Eof: CASE Status OF
B: Status := Error;
SSF: Status := Error;
BDP: Status := Error;
ADP: Status := Okay;
E, e: Status := Error;
SSF: Status := Error;
SF: Status := Okay
END {-- CASE}
END {-- CASE}
END; {-- WHILE, Status IN [ Error, Okay ]}
IF Status=Error THEN BEGIN
Writeln( 'Error: This is not a (signed) real!' );
END;
END; {-- ScanReal}

Une formulation améliorée de la procédure précédente est atteinte en utilisant une partie ELSE dans chacune des instructions CASE ainsi que d'éventuelles transformations de l'instruction CASE en une instruction IF.

PROCEDURE ScanReal;
VAR Status: Q;
Ch: S;
BEGIN {ScanReal}
Status := B; {état initial}
WHILE NOT ( Status IN [ Error, Okay ] ) DO BEGIN
GetCharacter( Ch );
CASE Ch OF
'0' .. '9': CASE Status OF
B, SSF, BDP: Status := BDP;
ADP: Status := ADP;
E, e, SSF, SF: Status := SF;
END; {-- CASE}
'+', '-': CASE Status OF
B: Status := SR;
E, e: Status := SSF
ELSE Status := Error;
END; {-- CASE}
'.': IF Status=BDP THEN BEGIN
Status := ADP;
END ELSE BEGIN
Status := Error;
END;
'E', 'e': IF ( Status=BDP ) OR ( Status=ADP ) THEN BEGIN
Status := E;
END ELSE BEGIN
Status := Error;
END;
eof: CASE Status OF
ADP, SF: Status := Okay;
ELSE Status := Error;
END; {-- CASE}
END; {-- CASE}
END; {-- WHILE, Status IN [ Error, Okay ] }
IF Status=Error THEN Writeln( 'Error: This is not a (signed) real!' )
END; {-- ScanReal}

Cet exemple montre qu'il est parfois préférable d'utiliser une instruction IF au lieu d'une instruction CASE.

© Aflo Informatique , 2003-2004