Remerciez-le!

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

Exercices dirigés séance n°1- corrigé Exercice 1 : compilation, analyse d’un pr

Exercices dirigés séance n°1- corrigé Exercice 1 : compilation, analyse d’un programme On définit le langage simplifié suivant au moyen de règles BNF : <phrase> ::= <déclaration> | <instruction> <déclaration> ::= <identificateur> : <type> ; <type> ::= réel | entier <instruction> ::= <identificateur> = <nombre> ; <nombre> ::= <nombre entier> | <nombre réel> Les identificateurs sont des unités lexicales constituées d’une lettre. Les nombres entiers sont des unités lexicales constituées d’un chiffre et les nombres réels des unités lexicales constituées de deux chiffres séparés par une virgule. Question 1 Rappeler les différentes phases de l’analyse d’un programme et leur rôle. Question 2 : analyse lexicale Un chiffre et une lettre sont définis par : <chiffre> ::= 0 | 1 | 2 | ….| 9 <lettre> ::= A | B …| Z o Définir sous forme de règles BNF identificateur, nombre entier et nombre réel. o Quelles sont les unités lexicales du langage autres que identificateur, nombre entier, nombre réel ? Solution o <identificateur> ::= <lettre> <nombre entier> ::= <chiffre> <nombre reel> ::= <chiffre> , <chiffre> o les autres unités lexicales sont : ; = entier réel L’espace est sans signification mais ne peut se trouver à l’intérieur d’une unité lexicale. Faire l’analyse lexicale de chaque ligne(phrase) du programme : A : reel $ B : entier ; = A 5,3,2 ; A B = 6,2 ; C = 4 ; VARI – ED n°1 – grammaires – corrigé 1 Pour cela, on recopiera les lignes en encadrant chaque unité lexicale reconnue par l’analyseur et on identifiera les erreurs lexicales en justifiant pourquoi ce sont des erreurs. Solution A : reel $ erreur $ n’est pas une unité lexicale B : entier ; analyse lexicale correcte = A 5,3,2 ; erreur , n’est pas une unité lexicale A B = 6,2 ; analyse lexicale correcte C = 4 ; analyse lexicale correcte Question 4 : analyse syntaxique On considère le programme suivant lexicalement correct : A : reel ; B : entier ; = A 5,3 ; A B = 6,2 ; C = 4 ; Décrire sous forme d’arbres, l’analyse syntaxique de chaque ligne du programme. On commentera les erreurs syntaxiques rencontrées. VARI – ED n°1 – grammaires – corrigé 2 Solution Analyse syntaxique correcte Analyse syntaxique correcte Erreur : on ne peut dériver ni <déclaration> ni <instruction> (aucune ne commence par =) VARI – ED n°1 – grammaires – corrigé 3 A : reel ; <déclaration> <identificateur> : <type> ; A reel B : entier ; <déclaration> <identificateur> : <type> ; B entier = A 5,3 A B = 6,2 ; Analyse syntaxique correcte Question 4 : analyse sémantique On considère le programme suivant lexicalement et syntaxiquement correct : A : réel ; B : entier ; A = 5,3 ; B = 6,2 ; C = 4 ; Un programme est en fait défini syntaxiquement comme une suite de déclarations, suivie d’une suite d’instructions : <programme> ::= {<déclaration>} {<instruction>} Le programme ci-dessus est correct vis à vis de cette définition. On introduit les règles suivantes pour l’analyse sémantique : - tout identificateur utilisé dans une instruction doit être déclaré. - dans une instruction, l’identificateur à gauche du = et le nombre à droite doivent être de même type. VARI – ED n°1 – grammaires – corrigé 4 <phrase> <déclaration> <identificateur> <identificateur> A Erreur on attend : et on trouve un identificateur B A B = 6,2 ; <instruction> <identificateur> <identificateur> A Erreur on attend = et on trouve un identificateur B C = 4 ; <instruction> <identificateur> = <nombre> ; C <entier> 4 o Quelles sont les erreurs signalées par l’analyse sémantique du programme ? Justifier la réponse. Solution B est déclaré en entier et on lui affecte un réel. C n’est pas déclaré. VARI – ED n°1 – grammaires – corrigé 5 Exercice 2 : une grammaire pour exprimer des dates On souhaite écrire une grammaire pour définir un petit langage permettant d’exprimer des dates sous les formes suivantes :  jj/mm/aaaa  mm/jj/aaaa  jj mois aaaa  mois jj aaaa Les symboles du vocabulaire terminal de ce langage sont les caractères alphanumériques. Question 1 Parmi les dates qui suivent, lesquelles seraient valides dans ce langage : 12/08/1992, 13/15/2000,05/30/2002, 08 juillet 1954,juin 43 1912, avril 23 1964, 38/09/3456 Question 2 Ecrire une grammaire pour ce langage VARI – ED n°1 – grammaires – corrigé 6 --- Exercice 2 ------ Solutions -------------------------------------------------------------------------------- Question 1 les dates suivantes seraient valides : 12/08/1992, 05/30/2002, 08 juillet 1954, avril 23 1964, les dates suivantes seraient invalides : 13/15/2000,juin 43 1912, 38/09/3456 Question 2 <date> ::= <date_paire>|<date_impaire> | <date_fevrier> <date_paire> ::= <jj_pair> / <mm_pair> / <aaaa> |<mm_pair> / <jj_pair> / <aaaa> |<jj_pair> <mois_pair> <aaaa> |<mois_pair> <jj_pair> <aaaa> <jj_pair> :: = 0 <de1a9> | <1ou2> <chiffre> | 3 0 <mm_pair> :: = 0 <4ou6ou9> | 1 1 <4ou6ou9> ::= 4 | 6 | 9 <aaaa> ::= <chiffre><chiffre><chiffre><chiffre> <mois_pair> ::= avril | juin | septembre | novembre <chiffre > ::= 0|1|2|3|4|5|6|7|8|9 <date_impaire>::= <jj_impair> / <mm_impair> / <aaaa> |<mm_impair> / <jj_impair> / <aaaa> |<jj_impair> <mois_impair> <aaaa> |<mois_impair> <jj_impair> <aaaa> <jj_impair> ::= 0 <de1a9> | <1ou2> <chiffre> | 3 <0ou1> <0ou1> ::= 0 | 1 <mm_impair> ::= 0 1 | 0 3 | 0 5 | 0 7 | 0 8 | 1 <0ou2> <0ou2> ::= 0 | 2 <mois_impair> ::= janvier | mars | mai | juillet | aout | octobre | décembre <date_fevrier> ::= <jj_fevrier> / 0 2 / <aaaa> | 0 2 / <jj_fevrier> / <aaaa> |<jj_fevrier> février <aaaa> |février <jj_fevrier> <aaaa> <jj_fevrier> ::= 0 <de1a9> | <1ou2> <chiffre> VARI – ED n°1 – grammaires – corrigé 7 Exercice 3 : une grammaire simplifiée pour les expressions booléennes <expr_bool> ::= <facteur> or <expr_bool> |<facteur> <facteur> ::= <terme> and <facteur> |<terme> <terme> ::= <identificateur> |<valeur> |(<expr_bool>) |not <terme> <identificateur> ::= <lettre>{<lettre>} <valeur> ::= vrai|faux <lettre> ::= ‘a’…’z’ Question 1 Les expressions suivantes sont elles syntaxiquement valides ? a and b or not (a or c) a and (b or not a) or c Question 2 Exprimer l’analyse des expressions précédentes sous la forme d’arbres syntaxiques. Question 3 Evaluer les expressions ci-dessus à partir de l’arbre syntaxique lorsque : a=vrai, b=faux, c=vrai VARI – ED n°1 – grammaires – corrigé 8 --- Exercice 3 ------ Solutions -------------------------------------------------------------------------------- Question 1 a and b or not (a or c) reconnue a and (b or not a) or c reconnue Question 2 arbre syntaxique de l’expression : a and b or not (a or c) VARI – ED n°1 – grammaires – corrigé 9 arbre syntaxique de l’expression : a and (b or not a) or c Question 3 Evaluation des expressions à partir de l’arbre syntaxique : faux vrai VARI – ED n°1 – grammaires – corrigé 10 Exercice 4 : un petit langage de programmation Soit la grammaire définissant un petit langage de programmation : <programme> ::= <instruction>{<instruction>} <instruction> ::= <affectation>|<conditionnelle> <conditionnelle> ::= ? <condition> : <affectation> <condition> ::= <expression> (=|#) <expression> <affectation> ::= <identificateur> = <expression> <expression> ::= <facteur> (+|-) <expression>|<facteur> <facteur> ::= <terme> (*|/) <facteur>|<terme> <terme> ::= <identificateur>|<nombre>|(<expression>) <identificateur> ::= ’a’…’z’ <nombre> ::= <chiffre><nombre>|<chiffre> <chiffre> ::= 0…9 Les symboles terminaux sont en gras. Question Les programmes suivants sont-ils syntaxiquement corrects ? Tracer l’arbre syntaxique. Si l’analyse n’aboutit pas, proposer une forme syntaxiquement valide. Chaque ligne est considérée comme un programme : c=6 b=c+(?(c=a):b=c) b=?(c#a):b=a b=b*a ?(b+c)#0:b=c y=+a/z VARI – ED n°1 – grammaires – corrigé 11 --- Exercice 4 ------ Solutions -------------------------------------------------------------------------------- c=6 programme instruction affectation identificateur = expression c facteur terme nombre chiffre 6 VARI – ED n°1 – grammaires – corrigé 12 b=c+ (? (c=a) : b=c) programme instruction affectation identificateur = expression b facteur + expression terme facteur identificateur terme c ( expression ) VARI – ED n°1 – grammaires – corrigé 13 ( non reconnue b=? (c#a) : b=a programme instruction affectation identificateur = expression b b=b*a programme instruction affectation identificateur = expression b facteur terme * facteur identificateur terme b identificateur a VARI – ED n°1 – grammaires – corrigé 14 ? non reconnue ?(b+c)#0:b=c programme instruction conditionnelle ? condition : affectation expression # expression identificateur = expression facteur facteur b facteur terme terme terme ( expression ) nombre identificateur facteur + expression chiffre c terme facteur 0 identificateur terme b identificateur c y=+a/z programme instruction affectation identificateur = expression VARI – ED n°1 – grammaires – corrigé 15 ? non reconnue uploads/Management/ ed1-corrige-2 2 .pdf