Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrigé du TD de L2 N°1 Patrick Poulingeas. • Exercice 1 . 1.a) Un identificate

Corrigé du TD de L2 N°1 Patrick Poulingeas. • Exercice 1 . 1.a) Un identificateur commence par une lettre (majuscule ou minuscule) suivi d'un nombre quelconque (éventuellement aucun) de symboles. Ces symboles sont constitués des lettres, des chiffres, et du caractère '_'. Exemples d'idenficateurs valides : i, i1, Une_variable, a____1 Exemples d'idenficateurs incorrects : 3a, _i, Une variable N.B. Dans les réponses aux questions suivantes, on se contentera de donner les règles de production des grammaires. L'axiome de la grammaire sera le premier symbole non terminal apparaissant en partie gauche de la première règle. Le vocabulaire non terminal et le vocabulaire terminal se déduiront implicitement de l'écriture des règles. <identificateur> ::= <lettre><suite de symboles> <suite de symboles> ::= <symbole><suite de symboles> | ^ <symbole> ::= <lettre> | <chiffre> | _ <lettre> ::= a | b | ... | z | A | B | ... | Z <chiffre> ::= 0 | 1 | ... | 9 1.b) Une constante (ou plus rigoureusement un littéral) de type chaîne de caractères est délimitée par des apostrophes et constituée d'un nombre quelconque de caractères. Pour permettre à une apostrophe de faire partie d'une chaîne de caractères, on double celle-ci. Ce sont les règles syntaxiques employées par Turbo Pascal. <constante chaîne> ::= '<suite de caractères>' <suite de caractères> ::= <caractère><suite de caractères> | ^ <caractère> ::= <lettre> | <chiffre> | '' | @ | ... 1.c) On se limitera à un sous-ensemble des déclarations de constantes possibles en Turbo Pascal. Exemple de déclarations de constantes simples : CONST c1 = 20000; { constante entière } c2 = 0.141; { constante réelle } c3 = 'a'; { constante caractère } c4 = 'chaine'; { constante chaîne de caractères } Exemple de déclarations de constantes typées : CONST c1 : Integer = 42; c2 : Real = 14.1E-2; c3 : Char = 'z'; c4 : String = 'foo'; c5 : String[30] = 'bar'; { 30 est le nombre maximum de caractères autorisés dans la chaîne } <déclaration de constantes> ::= CONST <suite de constantes> <suite de constantes> ::= <déclaration de constante>; | <déclaration de constante>;<suite de constantes> <déclaration de constante> ::= <identificateur> = <valeur numérique> | <identificateur> = '<caractère>' | <identificateur> = <constante chaîne> | <identificateur> : Integer = <constante entière> | <identificateur> : Real = <constante réelle> | <identificateur> : Char = '<caractère>' | <identificateur> : String = <constante chaîne> | <identificateur> : String[<nombre positif>] = <constante chaîne> <valeur numérique> ::= <constante entière> | <constante réelle> <constante entière> ::= <signe><nombre positif> | <nombre positif> <signe> ::= + | - <nombre positif> ::= <chiffre> | <chiffre><nombre positif> <constante réelle> ::= <constante entière><exposant> | <constante entière>.<nombre positif><exposant> <exposant> ::= ^ | E<constante entière> 1.d) Exemple de déclarations de variables (même remarque qu'au 1.c) : VAR i1 : Integer; i2 : Real; { Et les types Boolean, Char, String } i3, i4 : Integer; i5 : String[42]; i6 : Array [1..5] of Real; { tableau à une dimension } i7 : Array [3..7,1..8] of Char; { tableau à deux dimensions } <déclaration de variables> ::= VAR <suite de variables> <suite de variables> ::= <déclaration de variable>; | <déclaration de variable>;<suite de variables> <déclaration de variable> ::= <liste d'identificateurs> : <type> <liste d'identificateurs> ::= <identificateur> | <identificateur>,<liste d'identificateurs> <type> ::= Integer | Real | Boolean | Char | String | String[<nombre positif>] | <tableau> <tableau> ::= Array[<intervalles>] of <type> <intervalles> ::= <nombre positif>..<nombre positif> | <nombre positif>..<nombre positif>,<intervalles> 1.e) Exemple de déclarations de types (même remarque qu'au 1.c) : TYPE chaine = String[10]; tableau = Array[1..100] of chaine; personne = Record nom : String; prenom : String; age : Integer; end; <déclaration de types> ::= TYPE <suite de types> <suite de types> ::= <déclaration de type>; | <déclaration de type>;<suite de types> <déclaration de type> ::= <identificateur> = <type> <type> ::= Integer | Real | Boolean | Char | String | String[<nombre positif>] | <tableau2> | <enregistrement> <tableau2> ::= Array[<intervalles>] of <nom> <nom> ::= <type> | <identificateur> <enregistrement> ::= Record <suite de variables> end Dans les règles de productions que l'on vient d'écrire, pour la définition d'un nouveau type reprenant un type déclaré précédemment, on s'est limité au cas d'un type tableau, c'est-à-dire à la forme : Array[min..max] of “type déclaré précédemment” (comme dans l'exemple). Cette grammaire ne permet donc pas d'engendrer des déclarations du style : TYPE premier_type = Char; second_type = premier_type; { autorisé en Turbo Pascal } Pour gérer des déclarations de ce genre, il faudrait mettre le non-terminal <identificateur> dans une alternative de la règle de production définissant <type>. 1.f) Exemple de programme (c'est-à-dire un élément du langage considéré) : Algo exemple Variables a,b : entier; c : réel; Début a ← (3*5); b ← c; Ecrire(a); Ecrire(b+1); Ecrire(a,c); Lire(b); Si (a<b) et (b<2-3) alors c ← 42; Fin Si; Tant que non(a<b) faire Lire(b,c); a ← a+1; Fin Tant que; Pour i de 1 à 10 faire Ecrire(i); Fin Pour; Répéter a ← a+1; Jusqu'à (a=10) ou (7+b*68); Fin Remarques : – On interdira les programmes “vides” en rendant la partie contenant les instructions obligatoire (c'est-à-dire la partie commençant par le mot-clé Début et se terminant par le mot-clé Fin). – Le titre (c'est-à-dire la ligne commençant par le mot-clé Algo) et la section de déclaration des variables ne sont pas obligatoires. – Le ';' joue le rôle d'un terminateur d'instructions (comme en C, C++ ou Java) et non pas le rôle d'un séparateur d'instructions (comme avec Turbo Pascal). <programme> ::= <titre><ensemble de déclarations><ensemble d'instructions> <titre> ::= Algo <identificateur> | ^ <ensemble de déclarations> ::= Variables <suite de déclarations> | ^ <suite de déclarations> ::= <déclaration> | <déclaration><suite de déclarations> <déclaration> ::= <suite d'identificateurs> : <type>; <suite d'identificateurs> ::= <identificateur> | <identificateur>,<suite d'identificateurs> <type> ::= entier | réel <ensemble d'instructions> ::= Début <suite d'instructions> Fin <suite d'instructions> ::= <instruction>; | <instruction>;<suite d'instructions> <instruction> ::= <affectation> | <conditionnelle> | <itération> | <lecture> | <écriture> <affectation> ::= <identificateur> ← <EA> <conditionnelle> ::= Si <condition> alors <suite d'instructions><suite conditionnelle> <suite conditionnelle> ::= FinSi | Sinon <suite d'instructions> FinSi <itération> ::= Répéter <suite d'instructions> Jusqu'à <condition> | Tant que <condition> faire <suite d'instructions> Fin Tant que | Pour <identificateur> de <EA> à <EA> faire <suite d'instructions> Fin Pour <lecture> ::= lire (<suite d'identificateurs>) <écriture> ::= écrire (<suite d'expressions>) <suite d'expressions> ::= <EA> | <EA>,<suite d'expressions> <EA> ::= <EA1> | <EA>+<EA1> | <EA>-<EA1> <EA1> ::= <EA2> | <EA1>*<EA2> | <EA1>/<EA2> <EA2> ::= (<EA>) | <signe><opérande> <opérande> ::= <identificateur> | <entier> | <réel> <signe> ::= ^ | + | - <condition> ::= <expression booléenne> | (<expression booléenne>) | <expression booléenne><connecteur><expression booléenne> <expression booléenne> ::= <EA><comparaison><EA> | (<EA><comparaison><EA>) | non(<condition>) <connecteur> ::= et | ou <comparaison> ::= < | > |  |  | = |  Avec la formulation d'une expression conditionnelle donnée ci-dessus, la grammaire est ambiguë. Considérons en effet l'expression : Si (ab) alors ... On peut l'obtenir en effectuant les dérivations à gauche suivantes : Si <condition> alors <suite d'instructions><suite conditionnelle> ® Si <expression booléenne> alors <suite d'instructions><suite conditionnelle> ® Si (<EA><comparaison><EA>) alors <suite d'instructions><suite conditionnelle> ou en faisant les dérivations à gauche suivantes : Si <condition> alors <suite d'instructions><suite conditionnelle> ® Si (<expression booléenne>) alors <suite d'instructions><suite conditionnelle> ® Si (<EA><comparaison><EA>) alors <suite d'instructions><suite conditionnelle> Voici un autre ensemble de règles de productions pour une expression booléenne et dont l'avantage est d'introduire une priorité des opérateurs logiques : <condition> ::= <condition> ou <expression booléenne> | <expression booléenne> <expression booléenne> ::= <expression booléenne> et <terme booléen> | <terme booléen> <terme booléen> ::= (<condition>) | non(<condition>) | <EA><comparaison><EA> Avec cette grammaire, on a, pour les opérateurs logiques, l'ordre de priorité décroissant suivant : non, et, ou (C'est la convention utilisée par C, C++, Java et Turbo Pascal). • E xercice 2 . Pour le stockage en mémoire centrale, on se préoccupe essentiellement des règles de productions de la grammaire. Etudions sur un exemple la méthode de stockage que nous allons employer. On considère les règles de productions suivantes : <A> ::= a<B> | b <B> ::= ^ | <A>d Remarque : Des conventions que nous suivons depuis le 1.a, on déduit que : – le vocabulaire terminal est l'ensemble VT = {a,b,d} – le vocabulaire non-terminal est l'ensemble VN = {<A>,<B>} – l'axiome est <A> Pour représenter une règle, on introduit le type suivant : Type Règle = Enregistrement nom : Chaîne premiere_alternative : Entier positif Fin Enregistrement Le champ 'nom' est une chaîne de caractère correspondant à l'élément non-terminal en partie gauche de la règle. Quant au champ 'premiere_alternative', il correspond à un indice dans un tableau contenant les alternatives (appellé tab_alter) et sert à indiquer le début de la partie droite de la règle de production (c'est-à-dire le premier symbole de la première alternative). Les règles sont stockées dans un tableau d'éléments de type Règle appellé tab_règles. Pour représenter une alternative, on se sert du type suivant : Type Partie_d_alternative = Enregistrement symbole : Chaîne symbole_suivant : Entier positif alternative_suivante : Entier positif Fin Enregistrement Les alternatives sont stockées dans un tableau d'éléments du type uploads/s3/ exo-sur-identificateur-grammaire.pdf