Chapter 4 Analyse lexicale et syntaxique

L'analyse lexicale et syntaxique permet d'obtenir l'arbre de syntaxe abstraite (ASA) à partir d'un texte MiniJaJa, en se basant sur les définitions de lexèmes et les règles de grammaire. L'arbre ainsi obtenu permet d'appliquer les règles d'interpétation, de compilation ou encore le contrôleur de type. C'est la base du projet.

4.1 Idée générale

Un compilateur transforme un programme écrit en langage évolué en une suite d'instructions élémentaires exécutables par une machine. La compilation d'un programme est réalisée en trois phases. La première (analyse lexicale) consiste à découper le programme en petites entités : opérateurs, mots réservés, variables, constantes numériques, alphabétiques, etc. La deuxième phase (analyse syntaxique) consiste à expliciter la structure du programme sous forme d'un arbre, appelé arbre de syntaxe, chaque noeud de cet arbre correspondant à un opérateur et ses fils aux opérandes sur lesquels il agit. La troisième phase (génération de code) construit la suite d'instructions du micro-processeur à partir de l'arbre de syntaxe. En se basant sur les règles de grammaire du MiniJaja, il est nécessaire d'identifier les mots du langage pour pouvoir réussir à construire un arbre qui sera utilisé par l'interpréteur MiniJaja ou le compilateur. En simplifiant, transformer un code source en une structure de données exploitable.

4.2 Choix de réalisation

4.2.1 Langage

Les possibilités

Deux solutions nous ont été proposées pour réaliser les deux premières phases :

JavaCC de Sun Microsystems;
Flex++ et Bison++ du MIT.

Le premier a été développé en Java, il est donc facilement exploitable à l'aide d'une interface Java. Nous l'avons étudié lors du cursus de 2^ème annèe d'IUP. JavaCC intègre en un seul programme les fonctions d'analyse lexicale et syntaxique. Les seconds ont été développés en C++, Flex++ permet de faire l'analyse lexicale et Bison++ réalise la partie syntaxique. Nous n'avons pas eu l'occasion de l'utiliser auparavant. C'est donc naturellement que nous nous somme tournés vers JavaCC pour développer la partie de l'analyse lexicale et syntaxique et ainsi réaliser la totalité du projet en Java. D'une part JavaCC est assez facile d'utilisation et la prise en main a déjà été faite l'année dernière et d'autre part le développement d'une interface homme-machine est plus facile en Java qu'en C++.

Présentation de JavaCC

JavaCC signifie Java Compiler Compiler pour Java compilateur de compilateur. Il permet de générer des analyseurs lexicaux et syntaxiques à partir de grammaires de langage. Il se décompose en deux outils principaux :

JJTree
JavaCC

JJTree permet de générer l'analyseur avec l'aide d'un arbre. Il va introduire dans l'analyseur toutes les commandes permettant d'obtenir un arbre à la fin du traitement. Il est nécessaire de préciser en en-tête du fichier source pour jjtree certaines options pour obtenir le bon résultat :

DEBUG_PARSER = true | false: permet d'analyser lors du développement les résultats obtenus et notamment la manière dont l'analyseur fonctionne. Une fois le développement terminée, l'option doit être mise à false.
VISITOR = true | false: lorsque la valeur est true, JJTree va ajouter dans chaque classe de nooeud une méthode jjtAccept() et génère aussi une interface visitor qui peut être implantée et passée aux noeuds à accepter.
NODE_PACKAGE = ``nom'': , permet de générer les classes dans un package.

Il existe d'autres options mais nous ne les avons pas utilisées. Le résultat de l'exécution de jjtree permet de générer l'analyseur en utilisant l'outil JavaCC. On obtient pour chaque noeud une classe Java plus les fichiers de classes de bases qui une fois qu'ils sont tous compilés, donnent un objet qui nous permettra d'analyser un source pour en obtenir son arbre de syntaxe abstraite (ASA).

4.2.2 Modification de la grammaire

Il a été nécessaire d'adapter la grammaire fournie afin de pouvoir l'utiliser avec JJTree et JavaCC. Nous avons du supprimer toutes les récursivités à gauche et factoriser certains termes pour qu'il n'y ait qu'un seul point de choix possible et donc aucune ambiguité dans la grammaire. La grammaire telle qu'elle a été modifiée se trouve sur la page suivante. Elle est utilisée dans JJTree mais les différents noeuds nil et omega ne sont pas représentés car ils ne font rien.

4.3 Gestion des erreurs

4.3.1 Principe

Lors de l'analyse d'un fichier source il est probable de trouver des erreurs lexicales ou syntaxiques. Il est nécessaire d'en informer l'utilisateur en indiquant la ligne, le problème et ce à quoi l'analyseur s'attendait. L'un des défauts de JavaCC est justement la gestion des erreurs. En effet, JavaCC ne permet d'obtenir que la première erreur lors de l'analyse puis s'arrête. L'erreur qu'il retourne reste toutefois très complète. Il existe plusieurs méthodes permettant d'obtenir toutes les erreurs sans arrêter l'analyse mais elles sont fastidieuses à mettre en place. Plusieurs essais dans ce sens ont été réalisés sans succès.

4.3.2 Essais effectués ou envisagés

L'utilisation d'un noeud permettant de sauter l'erreur a été envisagée. Lorsque l'on est devant un point de choix non resolvable, un noeud permet d'avancer jusqu'à la fin de la ligne. Il se présente comme une règle de la grammaire MiniJaja mais il appelle un code Java qui fait avancer l'analyse jusqu'au prochain retour à la ligne. C'est ce point de choix supplémentaire qui permet de générer une exception Java. Cette première tentative n'a pu être mise en place de manière fonctionnelle, plusieurs problèmes ont été rencontrés. Seconde méthode, pour chaque non terminal on utilise un bloc try ... catch. Cela nous permet d'intercepter les exceptions avant le moteur de l'analyse. On gère un tableau dans lequel on stocke toutes les exceptions levées lors de l'analyse. Méthode un peu fastidieuse à mettre en place et non implantée par manque de temps. En fonction du temps restant, il est envisagé de l'intégrer dans le programme.

4.4 Jeux de test

Pour garantir le bon résultat de l'analyse, il est nécessaire de posséder des jeux de tests dont on connait le résultat escompté. Les jeux de tests varient par leur complexité et les règles de la grammaire qu'ils utilisent, cela va du simple test avec la commande minimum jusqu'au test ou toutes les règles sont utilisées.

Un test atomique : premier test utilisé non fourni par la suite, il contenait tout simplement le plus petit programme MiniJaja possible.
```
    class toto {
      main {
        
      }
    }
```
testSimple.mjj : un test un peu plus poussé, on a rajouté la déclaration de deux variables.
testfacile.mjj : sensiblement identique au précédent.
testErreur.mjj : fichier source comportant une à plusieurs erreurs ayant permis de contrôler la gestion des erreurs multiples.
testmoyen.mjj : test beaucoup plus poussé, accès sur la validation de l'ASA.
testTD.mjj : issu d'un TD de compilation dont nous avons corrigé l'ASA.
testComplet.mjj : test comportant tous les cas possibles de la grammaire MiniJaja. Utilisé pour valider définitivement les résultats et le bon fonctionnement des règles.