Discussion :

[other1234]

Bonjour,

je suis en train de créer un programme qui reçoit en entrée un fichier contenant une grammaire EBNF et qui va nous donner en sortie la procédure correspondante.

Par exemple, on a la grammaire suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

identificateur = lettre {lettre|chiffre}

Je ne sais pas comment rendre cette grammaire en une procédure ou méthode écrite en Java ou même une classe ??

Sachant que ça se passe de manière dynamique, c'est-à-dire que quelle que soit la grammaire en entrée, il va nous donner la classe correspondante.

Merci

[captaindidou]

Salut,

ce dont tu parles, c'est l'essence même de l'analyse lexicale, celle qui est modélisable par automates à états finis.

D'une part, au préalable, si j'ai bien compris, tu as besoin de définir une syntaxe de définition de grammaires pour prendre en compte les grammaires qui seront soumises en paramètre (ce que tu désignes par le terme dynamique). Après tu utilises ton générateur d'analyseur syntaxique qui te plait le plus en Java par exemple: Bison, BYACC, JavaCC, ANTLR ou Xtext.

Une fois cette analyseur de grammaire, fait, tu obtiendras une représentation informatique des grammaires passées en paramètre. On l'appelle la syntaxe abstraite.

De cette structure de données, tu pourras en déduire facilement un automate à états finis, mais potentiellement non déterministe.

Il est non déterministe si pour l'un de ses états au moins, il existe deux transitions sortantes vers deux états suivants différents mais qui ont une étiquette identique. Les deux états suivants doivent alors être fusionnés pour obtenir l'automate déterministe.

La génération de code à partir de cet automate déterministe est alors simple :

Une procédure par état, dans chaque procédure, un switch avec chaque entrée correspondant à l'étiquette d'une transition possible depuis cet état suivi de l'appel à la procédure correspondant à l'état cible de la transition.

Dans le cas que tu présentes, l'analyseur doit d'abord attendre une lettre puis une lettre ou un chiffre ou rien du tout.
Donc : traduit litéralement en automate, cela donne ça (voir pièce jointe)


[0] est l'état initial, [2], l'état final, synonyme d'acceptation de la chaine de caractères.

Toute autre entrée que 'lettre' dans l'état 0 est une erreur, comme toute entrée autre que lettre, chiffre ou chaine vide est aussi une erreur.