[PDF] Université Paris 7 – MASTER 2 – 05/06 Algorithmique avancée et

View - Download Université Paris 7 – MASTER 2 – 05/06 Algorithmique avancée et

Previous PDF

Next PDF

Universit´e Paris 7 - MASTER 2 - 05/06Compilation

Algorithmique avanc´ee et compilation

Devoir en temps limit´e

Dur´ee : 2 heures.

Documents autoris´es

1. On suppose qu"on d´ecrit des automatesd´eterministessous la forme de suites

d""instructions" comme illustr´e par les deux exemples suivants : init A ; A--a->B ; B--a->A ; B--b->B ; final B. a A Ba b

A--a->B ;

A--b->C ;

B--a->C ;

B--b->B ;

B--c->D ;

C--b->A ;

C--c->D ;

D--c->E ;

E--c->B ;

init A ; final C, E. c A B C DEa a b bb c c c Donner une grammaire pour ce langage (la grammaire n"a pas pour fonction de v´erifier qu"il s"agit d"un automate d´eterministe) Ecrire un coupleparser/lexerpour reconnaˆıtre les mots de ce langage.

2. D´efinir une structure de donn´ees pour stocker un automate fini d´eterministe. Pour

simplifier la tˆache, on supposera qu"on a au plus 26 ´etats correspondants aux lettres majuscules, et au plus 26 transitions correspondant aux lettres minuscules. Associer au parser pr´ec´edent les actions permettant de construire en m´emoire l"au- tomate d´ecrit. On suppose que l"automate est syntaxiquement et s´emantiquement bien form´e.

3. Ajouter dans l"interfaceyaccla possibilit´e de proposer un mot au parser (par

exemple abbcc?) pour v´erifier que ce mot est reconnu par l"automate (il fautdonc impl´ementer une fonction de parcours de l"automate).

4. [Bonus] Ajouter au parser du contrˆole d"erreur pour ne pas construire en m´emoire

un automate qui serait non d´eterministe.

Renvoyer par mail en fin d"´epreuve un fichier (tgzde pr´ef´erence) contenant : le codeyacc, le

codelex, le code C additionnel, le makefile, et un fichier texte contenant une trace d"ex´ecution.

quotesdbs_dbs23.pdfusesText_29

[PDF] td algorithme avancé

[PDF] algorithme equation 2eme degré pascal

[PDF] algorithme equation du second degré nombre complexe

[PDF] organigramme equation second degré

[PDF] exercice algorithme avec correction pdf

[PDF] exercices corrigés algorithme pdf

[PDF] exercices corrigés algorithme tableau

[PDF] algorithme moyenne generale

[PDF] exercice corrigé d'algorithme

[PDF] ecrire un programme en c qui calcule la moyenne

[PDF] des exercice avec le corrige sur les tableau de l'algorithme

[PDF] langage c moyenne tableau

[PDF] cours d algorithme sur les tableaux

[PDF] ecrire un algorithme qui calcule la racine carré

[PDF] algorithme racine carrée entière