Archive for mai, 2008

mai 19 2008

Compilation : génération d’une table LR0 en Java

Published by Romain Bouleis under Developpement

Après un long moment d’inactivité, voici une réalisation à laquelle j’ai énormément contribuée.

Extrait du cahier des charges :

La construction d’une table de reconnaissance LR0 répond à un besoin bien précis dans la phase de conception d’un compilateur : l’analyse syntaxique. Selon la complexité de la grammaire, la table LR0 pourrait ne pas être suffisante pour une analyse syntaxique complète, il faudrait envisager dans ce cas là une table LR1 ou LALR. De plus, on dit d’une grammaire qu’elle est compatible avec une analyse LR si :

  • Les alternatives ont été supprimées,
  • Un axiome supplémentaire a été rajouté.

Notre travail est donc d’établir cette table à partir des productions d’une grammaire donnée. Si, au cours du programme, il apparaissait que la grammaire est ambigüe, un message d’erreur le signalera, mais n’empêchera pas le programme de se terminer. Il en résultera une table non exploitable telle quel.

En plus d’être fournie au groupe chargé de l’analyse syntaxique, il convient de la fournir sous un format très facilement compréhensible afin de vérifier manuellement sa validité. La construction d’une table LR0 se répartit de la manière suivante :

  • Suppression des alternatives,
  • Ajout de l’axiome pour obtenir une grammaire augmentée,
  • Déduction de la collection d’item initiale issue de la grammaire augmentée grâce à fermeture(I) ou I est l’axiome ajouté,
  • Détermination de la table des fermetures,
  • Déduction de la table des transitions,
  • Détermination des suivants,
  • Construction de la table LR0 à partir de la table des transitions et des suivants.

Ce mini projet a été réalisé en Java, voici toutes les ressources :

Toutes les remarques seront les bienvenues.

No responses yet