Remerciez-le!

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

1/6 Université de Rennes 1 L3 INFORMATIQUE EXAMEN DE CMPL Vendredi 26 Avril 201

1/6 Université de Rennes 1 L3 INFORMATIQUE EXAMEN DE CMPL Vendredi 26 Avril 2019 à 14h Durée : 2 heures Notation : Exercice 1 = 4 points ; Exercice 2 = 6 points ; Exercice 3 = 10 points Nombre de pages : 6 (dont la grammaire du langage Projet, rappelée page 6) Seul document autorisé : résumé personnel au format A4 recto-verso EXERCICE 1 (4 points) - Grammaire LL(1) et analyse DGD Soit la grammaire hors contexte suivante : G = (VN , VT , P , S) , VN = {S, X, U, T, Y, R} , VT = {a, b, c, d, e, f, #}, l’axiome est S et l’ensemble P des productions est : S  X # X  U a | R T U  b U |  T  Y a Y |  Y  c | d R T R  e R f |  Cette grammaire est LL(1). QUESTIONS 1.1 Donner les ensembles de prédiction Pred pour toutes les règles associées aux non-terminaux X, T et R. 1.2 Donner les procédures Java d’analyse syntaxique descendante déterministe associées aux non-terminaux X et T uniquement. Mot: S -> X -> U->3->a 2/6 EXERCICE 2 (6 points) - Automate fini On considère le langage rationnel L généré par la grammaire suivante : <suite_fiches>  ( <fiche> ; )* / <fiche>  <début_loc> | <fin_loc> <début_loc>  <client> <horaire>0/1 DEBUT <quantité_louée> <quantité_louée>  <qté> ADULTE <qté> ENFANT | <qté> ADULTE | <qté> ENFANT <client>  ident <horaire>  nbentier HEURES <qté>  nbentier <fin_loc>  <client> <horaire>0/1 FIN Les <horaire> concernent une même journée. Une fiche de début de location sans <horaire> cor respond à un début à 8h et une fiche de fin de location sans <horaire> correspond à une fin à 18h. Pour faciliter la gestion du parc de vélos, on dispose de : private static class InfosClient { public int heureD, qteA, qteE ; // heure de début, nb vélos adultes et nb vélos enfant loués } private static void debuterLoc ( int nId, InfosClient infoC) { / met à jour la structure de données nécessaire à la mémorisation des informations de location infoC liées au client de numId nId / } private static InfosClient recupInfos (int nId) { / retourne les informations de location mémorisées pour le client de numId nId / } On dispose aussi des attributs lexicaux Lex.valNb (associé à nbentier), Lex.numId (associé à ident) et de la procédure Lex.repId(int numId) qui permet d’obtenir la chaîne associée à un numId. Les fiches sont supposées sans erreur et aucun contrôle n’est demandé dans les actions. QUESTIONS 2.1 Proposer un automate fini déterministe, pour le vocabulaire terminal VT = {ident, nbentier, ADULTE, DEBUT, ENFANT, FIN, HEURES , ; , / }, réalisant l’analyse syntaxique de L. 2.2 Placer, dans cet automate d’analyse syntaxique, des numéros d’actions et fournir les traitements associés afin de répondre aux demandes suivantes : - forcer l’heure (si elle n’est pas indiquée) à 8 pour un début de location et à 18 pour une fin de location. - écrire, à chaque fin de location, la somme due par le client. Le tarif horaire est 4€ pour un vélo adulte et 2€ pour un vélo enfant. 3/6 - écrire, en fin d’analyse, le nombre de vélos non ramenés pour chacune des deux catégories. Exemple : Grazon DEBUT 3 ADULTE 1 ENFANT ; Masson 10 HEURES DEBUT 8 ADULTE ; Grazon 14 HEURES FIN ; Girard 15 HEURES DEBUT 6 ADULTE ; Girard FIN / signifie ce qui suit Grazon : a loué 3 vélos adulte et 1 vélo enfant de 8h à 14h (soit 6h) et doit payer 3x6x4+1x6x2 = 84€, Girard : a loué 6 vélos adulte de 15h à 18h (soit 3h) et doit payer 6x3x4 = 72€, à la fin de la journée, 8 vélos adulte n’ont pas été ramenés. EXERCICE 3 (10 points) - Compilation On considère le langage PROJET, sans procédures ni compilation séparée, que l’on souhaite enrichir par de nouvelles constructions. On suppose déclarés et disponibles : - la table des symboles tabSymb[code, categorie, type, info], d’indice de remplissage it ainsi que les utilitaires presentIdent(int bInf), placeIdent(int code, int categorie, int type, int info), - l’instance po de la classe ProgObjet et les méthodes po.produire(int codeOuArg), po.modifier(int i, int codeOuArg), po.getIpo(), po.getElt(int i), - l’intance pileRep (pile de reprise) de la classe TPileRep et les méthodes pileRep.empi ler(int x), pileRep.depiler(), - la variable tCour, - les instructions de la machine à pile MAPILE RESERVER, EMPILER, CONTENUG, AFFECTERG, OU, ET, NON, INF, INFEG, SUP, SUPEG, EG, DIFF, ADD, SOUS, MUL, DIV, BSIFAUX, BINCOND, LIRENT, LIREBOOL, ECRENT, ECRBOOL, ARRET. - les fonctions : verifEnt(), verifBool(), UtilLex.messErr(String m)... - les attributs lexicaux : UtilLex.valNb, UtilLex.numId QUESTIONS - (les 4 questions sont indépendantes) 3.1 On ajoute la règle : primaire : ’precedent’ ’(’ expression ’,’ expression ’)’ ; où, pour des expressions entières e1 et e2 , l’exécution de precedent ( e1 , e2 ) rend vrai si la valeur de l’expression entière e1 est égale à la valeur de l’expression entière e2-1 et faux sinon. Placer les points de génération et donner les traitements associés (code MAPILE produit et/ou contrôles éventuels) afin de prendre en compte la compilation de ce nouveau primaire. 4/6 3.2 On ajoute la règle : primaire : ’necessaire’ ’(’ expression ’,’ expression ’)’ | ’suffisant’ ’(’ expression ’,’ expression ’)’ ; où, pour des expressions booléennes e1 et e2 , l’exécution de : - necessaire ( e1 , e2 ) rend vrai si e1 ou non e2, faux sinon, - suffisant ( e1 , e2 ) rend vrai si non e1 ou e2, faux sinon. Placer les points de génération et donner les traitements associés (code MAPILE produit et/ou contrôles éventuels) afin de compiler ces nouveaux primaires. 3.3 On ajoute une règle d’instruction : instruction : bouclebis ; bouclebis : ’boucle’ instructions ’;’ ( ’continuersi’ expression ’;’ instructions ’;’ )+ ’fboucle’ où l’itération s’arrête dès que l’exécution atteint une alternative continuersi dont l’expression booléenne vaut faux (noter que l’itération bouclebis peut contenir un nombre quelconque strictement positif d’alternatives continuersi expression). Placer les points de génération et donner les traitements associés (code MAPILE produit et/ou contrôles éventuels) afin de compiler cette nouvelle instruction. 3.4 On ajoute la règle : primaire : ’croissant’ ’(’ expression ( ’,’ expression )+ ’)’ ; où, pour les expressions entières e1 , e2 , ..., en, l’exécution de croissant ( e1 , e2 , ... , en ) rend vrai si e1 e2 ... en et faux sinon. 3.4.1 On rappelle le fonctionnement de l’ordre MAPILE infeg déjà existant : • infeg val2=pileExec.depiler(); val1=pileExec.depiler(); if (val1<=val2) pileExec.empiler(VRAI); else pileExec.empiler(FAUX); Expliquer pourquoi l’ordre infeg ne permet pas de produire le code objet pour cette question. 5/6 3.4.2 On introduit deux nouveaux ordres MAPILE: • nouvinfeg {à compléter} • decrementerSommetPileExec ip := ip-1; Compléter le nouvel ordre nouvinfeg. 3.4.3 Donner le code MAPILE produit pour le programme source suivant : programme croiss : var ent x1, x2, x3, x4; debut lire (x1, x2, x3, x4); ecrire (croissant (x1, x2+1, x3, 2*x4) ; fin NB: ici, on ne demande pas les points de générations associés. exp3 exp2 ip -> PileExec exp4 … val2 = depile val1 = depile val2 = empile primaire : ’croissant’ ’(’ expression ( ’,’ expression )+ ’)’ ; Vrai exp1 Vrai ou Faux Vrai ou Faux Vrai ou Faux 6/6 Grammaire du langage PROJET : unite : unitprog | unitmodule ; unitprog :: ’ programme ’ ident ’ : ’ declarations corps ; unitmodule :: ’ module ’ ident ’ : ’ declarations ; declarations : partiedef ? partieref ? consts ? vars ? decprocs ? ; partiedef : ’ def ’ ident ( ’ , ’ ident ) ptvg ; partieref : ’ ref ’ specif ( ’ , ’ specif ) ptvg ; specif : ident ( ’ fixe ’ ’ ( ’ type ( ’ , ’ type ) ’ ) ’ ) ? ( ’ mod ’ ’ ( ’ type ( ’ , ’ type ) ’ ) ’ ) ? ; consts : ’ const ’ ( ident ’ = ’ valeur ptvg )+ ; vars : ’ var ’ ( type ident ( ’ , ’ ident ) ptvg )+ ; type : ’ ent ’ | ’ bool ’ ; decprocs : ( decproc ptvg )+ ; decproc : ’ proc ’ ident parfixe ? parmod ? consts ? vars ? corps ; ptvg : ’ ; ’ | ; corps : ’ debut ’ instructions ’ fin ’ ; parfixe : ’ fixe ’ ’ ( ’ pf ( ’; ’ pf ) ’ ) ’ ; pf : type ident ( ’ , ’ ident ) ; parmod : ’ mod ’ ’ ( ’ pm ( ’ ; ’ pm ) ’ ) ’ ; pm : type ident ( ’ , ’ ident ) ; instructions : instruction ( ’ ; uploads/s3/ sujet-examen-avril2019.pdf