Les meilleurs développeurs informatique freelances sont sur Codeur.com
Fermé·Moins de 500 €·4 offres·1033 vues·9 interactions
Nous cherchons un freelance pour le développement d’un outil informatique qui consiste en un générateur d’analyseur lexical.
Autrement dit, ce qu’il vous est demandé ici est de créer une nouvelle version, simplifiée bien entendu, du logiciel Lex.
Plus précisément, étant donnée n’importe quelle expression rationnelle donnée en entrée, l’outil développé doit créer in fine l’analyseur lexical qui lui est associé, i.e. l’automate fini déterministe minimal permettant de
reconnaître n’importe quel mot appartement au langage rationnel défini par l’expression rationnelle fournie.
Le dévéloppement sera en langage C.
Celui-ci prend une expression rationnelle simple en entrée, définie dans un fichier.
Une expression rationnelle simple est une expression rationnelle définie uniquement à partir de la répétition de Kleene (représentée par l’opérateur unaire *, e.g a* signifiant « l’expression a zéro ou plusieurs fois »), la concaténation (représentée par deux sous-expressions rationnelles qui se suivent, e.g. ab signifiant « l’expression
a suivie de l’expression b ») et la disjonction (représentée par l’opérateur binaire |, e.g. a | b
signifiant « l’expression a ou l’expression b », le « ou » étant ici à comprendre dans son sens exclusif).
Le fichier contenant la définition de l’expression rationnelle sur laquelle le générateur doit être créé est de la forme :
La première ligne du fichier doit contenir la définition de l’expression rationnelle simple
qui doit forcément être suivie d’un caractère newline.
(a|(bc))*(ba(ca|ba)).
Depuis l’expression rationnelle e donnée en entrée, le générateur devra construire séquentiellement :
— l’arbre de syntaxe abstraite T de e (construit de la gauche vers la droite);
— l’automate fini non déterministe N associé à T contenant potentiellement des -
transitions, par l’application de l’algorithme de McNaughton, Yamada et Thompson ;
— l’automate fini déterministe D associé à N par application de l’algorithme de construction
de sa table de transition Dtrans;
— l’automate fini déterministe minimal D0 de e.
Fournir également une représentation graphique de chacun des « objets » T , N,D et D0. La création de telles représentations devra être automatisée à l’aide d’un logiciel de représentation de graphe tel que graphviz.
À partir de l’automate D0, le générateur devra automatiquement engendrer le code d’un programme C dont l’exécutable obtenu par compilation avec gcc implantera l’analyseur lexical de e. En prenant un mot m en entrée, cet analyseur lexical devra alors répondre :
— “m appartient au langage rationnel défini par e.” si m est reconnu par D0 ;
— “m n’appartient pas au langage rationnel défini par e.” sinon.
Budget indicatif : Moins de 500 €
Publication : 16 avril 2020 à 10h36
Profils recherchés : Développeur spécifique freelance
4 freelances ont répondu à ce projet
4 propositions de devis en moins de 2h