:: Enseignements :: ESIPE :: E4INFO :: 2011-2012 :: Génération de code ::

Langset - Correction

L'objectif de ce TD est d'implanter une grammaire pour un langage exprimant des ensembles d'entiers et ensuite d'évaluer des expressions exprimées à l'aide de ce langage.

Présentation du langage Langset

Le langage Langset permet d'exprimer des ensembles d'entiers ; voici quelques exemples d'opérations sur les ensembles utilisant Langset :

1 représente l'ensemble à un élément {1}.
1 + 2 + 3 + 5 + 8 + 5 permet d'exprimer l'ensemble des entiers {1, 2, 3, 5, 8} (on rappelle qu'un ensemble ne contient au plus qu'un exemplaire d'un élément) : + est l'opérateur d'union d'ensembles.
1 + 2 * 2 + 4 représente l'intersection des ensembles {1, 2} et {2,4} soit l'ensemble {2} : * est l'opérateur d'intersection d'ensembles
1 + 2 + 3 - 1 + 2 représente l'ensemble {1, 2, 3} privé des éléments de l'ensemble {1, 2} : - est l'opérateur de soustraction d'ensemble.

Préparation du projet

On se rapportera aux consignes du TD 0 préliminaire pour la préparation d'un projet utilisant Tatoo. Les sources de ce projet seront situées dans le paquetage fr.upemlv.langset et le projet sera nommé Langset.

Fichier EBNF et construction des tables des automates

La première étape est d'exprimer le lexique (tokens) et la grammaire de Langset dans le fichier grammar.ebnf. On exprimera pour l'instant les tokens entier et l'opérateur d'union + dans le lexique. Nous écrivons les règles de la grammaire afin de supporter des expressions composée d'un entier (ensemble singleton) ou d'une union de deux ensembles. On ne se préoccupe pas pour l'instant de la priorité et de l'associativité de l'opérateur d'union.

Compiler le fichier EBNF pour générer les tables des automates en utilisant la règle "enbf" du fichier build.xml (ant ebnf).
Observer la réaction du compilateur de Tatoo et corriger les éventuelles erreurs. Il faudra notamment gérer la priorité/associativité de l'opérateur + afin d'éliminer un conflit shift/reduce. Les éventuels conflits rencontrés sont reportés dans le fichier log.xml qu'il est conseillé de consulter attentivement.
Ajouter le support des opérateurs * (intersection) et - (soustraction) en gérant judicieusement priorité et associativité.
Quelquefois les priorités par défaut des opérateurs ne sont pas adaptées. On souhaiterait forcer les opérations réalisées en les parenthésant. Par exemple nous pourrions exprimer 1 + ( 2 * 2 ) + 4 = { 1, 2, 4 }, les parenthèses étant nécessaires car l'opérateur + est naturellement prioritaire sur *. Ajouter les tokens nécessaires et modifier la grammaire pour supporter le parenthésage.

Analyse lexicale

On écrit maintenant un analyseur lexical (LangsetLexer) décomposant une expression Langset en une suite de lexèmes. L'expression est fournie sur l'entrée standard ou dans un fichier et l'on retourne sur la sortie standard la suite des lexèmes (un lexème par ligne).

On implante un LexerListener réalisant ce travail d'écriture de lexèmes : pour chaque lexème on indique son type (entier, opérateur +, -, *...) ainsi que sa valeur textuelle et si possible sa localisation dans le code . Il faudra implanter la méthode de signature void ruleVerified(LangsetRuleEnum rule, int lastTokenLength, B buffer) (l'argument lastTokenLength ne sert à rien ici).

Une fois l'implantation et la compilation réalisée avec la règle Ant ad-hoc, on teste l'analyseur sur quelques entrées valides (exemple : 1 + 2 * 4) mais également invalides (exemple : 1.2 + a - 3).

Évaluateur

On souhaite maintenant évaluer les expressions représentant des ensembles dans une classe LangsetEvaluator. On initialise à cet effet un analyseur syntaxique lisant l'entrée standard ou un fichier et retournant l'expression évaluée. On lui fournit une implantation de ToolsListener avec quatre méthodes à implanter :

comment() appelée lors qu'un commentaire est reconnu ;
shift() appelée lorsqu'un décalagage (lecture de token) est effectué ;
reduce() appelée lors qu'une réduction est réalisée ;
accept() appelée lorsque le texte en entrée est accepté par l'analyseur.

Nous utiliserons à cet effet une pile d'ensembles d'entiers (Stack<Set<Integer>>). Lors d'un shift d'un entier, nous pouvons empiler un ensemble singleton de cet entier ; lors d'une réduction sur une opération binaire, nous pouvons dépiler les deux ensembles en haut de pile, réaliser l'opération et réempiler son résultat.

Une archive avec une proposition de correction peut être trouvée ici