:: Enseignements :: ESIPE :: E4INFO :: 2009-2010 :: Génération de code ::

Analyse syntaxique et évaluation

Le but de ce TD est d'implémenter un évaluateur d'expressions arithmétiques. Cet évaluateur sera basé sur un analyseur syntaxique construit à l'aide de Tatoo.

Introduction

Le but de ce TD est d'implémenter un évaluateur d'expressions arithmétiques. Les expressions traitées auront des valeurs réelles et accepteront les opérations d'additions, soustractions et multiplications. L'évaluateur sera basé sur un analyseur syntaxique construit à l'aide de Tatoo. Durant cette séance, la construction d'un analyseur à l'aide de tatoo se fait de la manière suivante:

Ecriture des règles du lexeur et d'une grammaire dans un fichier EBNF.
Génération par Tatoo des classes fondamentales du lexeur et du parseur, à l'aide d'une tâche ANT.
Ecriture en Java de l'analyseur au moyen de l'implémentation de listeners.

Exercice 1 - Procédure préliminaire

Ressources disponibles :

Télécharger l'archive gc-ir2-td1.zip contenant:

les librairies Tatoo: tatoo.jar et le répertoire motocity dans build-lib et tatoo-runtime.jar dans le répertoire lib.
tatoo.jar est utilisé pour générer le lexeur (et le parseur) à partir d'une grammaire. tatoo-runtime.jar contient les classes nécessaires à l'exécution du lexeur (et du parseur).
les données nécessaires pour construire l'évaluateur d'expressions arithmétiques (répertoire td1).

Procédure préliminaire à suivre :

Décompresser l'archive.
Sous Eclipse, créer un nouveau projet pour les TD de génération de code. Les classes compilées devront être placées dans le répertoire classes.
Si vous etes grands, vous pouvez même avoir un répertoire classes par TD.
Importer les sous-répertoires lib, build-lib et td1.
Ajouter td1/src et td1/gen-src dans le sourcepath. (click bouton droit sur le répertoire, puis Build Path > Add). Pour info, le répertoire gen-src contiendra le code source des classes générées par Tatoo.
Ajouter le fichier tatoo-runtime.jar se trouvant dans lib dans le buildpath (toujours avec le bouton droit).

Exercice 2 - Construction de l'automate des items et priorités

Nous travaillons dorénavant dans le répertoire td1. La tâche ANT (définie dans le fichier build.xml) est chargée de générer les classes fondamentales du lexeur et du parseur définis dans le fichier td1.ebnf. L'attribut parserType indique le type d'analyseur ascendant (LR ) donc lr,slr ou lalr). Pour plus de détails sur le fichier de spécification EBNF, il existe un petite documentation (sinon le reste se trouve dans le cours).

Ouvrir le fichier td1.ebnf. Que décrit-il?
Générer les classes fondamentales du lexeur et du parseur décrit par ce fichier. Que se passe-t-il?
Pour corriger le problème. Ouvrir le fichier log.xml qui a été généré. Celui-ci décrit l'automate des items construit. Trouver l'état qui pose problème.
Résoudre ce problème à l'aide des priorités et règles d'associativités vues en cours.
Ajouter maintenant les soustractions dans les opérations possibles. Générer les classes. Résoudre les problèmes, s'il y en a.
Puis, ajouter les multiplications. Générer les classes. Résoudre les problèmes, s'il y en a.

Exercice 3 - Analyseur lexical

On souhaite maintenant écrire un analyseur qui affiche les tokens lus (type et valeur) en entrée standard ou dans un fichier passé en argument. Ouvrir le code source LexerMain.java qui contient une implémentation incomplète d'un tel analyseur. Il se base sur les classes Td1RuleEnum et Td1LexerDataTable générées à l'exercice précédent. Td1RuleEnum est l'énumération des règles lexicales utilisées. Td1LexerDataTable implémente la table des automates décrits par les règles lexicales.

On vous demande de compléter l'implémentation du LexerListener qui contient une méthode ruleVerified qui sera appelée à chaque fois qu'un nouveau token sera lu. La méthode a trois paramètres: le type de la règle qui a permis de reconnaitre le token, la taille du dernier token (qui ici ne sert à rien) et le buffer contenant les tokens lus.

Tester sur des entrées valides (ex. 12.4 + 5.1) et non valides (ex. 12.3 / 12.2).

Exercice 4 - Evaluateur

On vous demande maintenant d'implémenter un évaluateur des expressions arithmétiques données en entrée standard ou dans un fichier passé en argument. Par exemple, l'évaluation de l'expression 10.2-2.5*2.0 donnera 5.2.

Ouvrir le code source EvalAnalyzerMain.java qui contient une implémentation incomplète de l'évaluateur. Il utilise les classes fondamentales du parseur et du lexeur, générées par Tatoo:

pour le lexeur (cf. exercice précédent): Td1LexerDataTable et Td1RuleEnum
pour le parseur : Td1NonTerminalEnum (enumération des non-terminaux), Td1TerminalEnum (Enumération des terminaux), Td1ProductionEnum (Enumération des noms des productions), Td1ParserDataTable (l'automate LR sous la forme de la table d'analyse);
pour le lien entre parseur et lexeur: Td1ToolsDataTable (table de correspondance entre tokens et terminaux)

Compléter ce code pour qu'il affiche le résultat de l'évaluation de l'expression arithmétique en entrée.

Il faut compléter l'implémentation du ToolsListener qui possède 4 méthodes:

comment appelée à chaque fois q'un commentaire est reconnu ;
shift appelée à chaque fois qu'un décalage (shift) est réalisé ;
reduce appelée à chaque fois d'une réduction (reduce) est réalisée ;
accept appelée quand le texte en entrée est acceptée (accept) par le parseur.

Indication : Utiliser une pile de réels (java.util.ArrayDeque).