Par Christopher Lopes, étudiant à la Eastern Washington University
Cet article est le troisième d'une série commencée dans le numéro d'avril 1999 de la Linux Gazette. Voir : Outils de Construction de Compilateurs partie I. La Partie II, qui donne des instructions détaillées quant à l'installation de JFlex et de CUP, est également disponible dans ce même numéro.
L'exemple présenté ici est une version modifiée de l'exemple de calculatrice présentée dans le manuel de CUP. En particulier, le fichier de spécification JFlex qui va avec est fourni. De plus, ce fichier et sa spécification CUP associée sont abondamment commentés. L'exemple de la calculatrice est le traditionnel premier exemple que l'on choisit pour montrer l'utilisation des outils de la famille lex/yacc. Nous travaillons actuellement sur un projet qui présenterait un exemple plus complexe : un langage d'initialisation pour un moteur de logique floue destiné à être utilisé dans des applications de prise de décision. Si l'intérêt exprimé pour ce projet à plus long terme est suffisamment important, nous lui consacrerons un article.
Le but de JFlex dans ce projet est de construire un analyseur lexical pour notre calculatrice. Cet analyseur lexical, ou scanneur, vérifiera les entrées dans notre calculatrice et la validité des groupements de caractères.
Le fichier de spécification lexical pour JFlex est divisé en trois sections,
chacune de ces sections étant séparée par %%.
Section de Code Utilisateur
%%
Section des Déclarations et Options
%%
Section des Règles Lexicales
Tout ce qui se trouve dans cette section sera copié dans la classe générée du
lexer avant la déclaration de la classe. Dans cette section, on trouve
généralement des instructions package et import. Notre
spécification lexicale pour cette section importe deux classes: sym et
java_cup.runtime.* et ressemble à ce qui suit:
import java_cup.runtime.*;
import sym;
Dans notre exemple, la classe sym est générée (avec le parseur) par CUP.
Cette section abrite les options, les états lexicaux et les déclarations de
macro. Les options de configuration vont inclure du code supplémentaire qui va
être inclus dans la classe générée du scanneur. Les options doivent commencer et
finir une ligne avec %. Un grand nombre d'options peut être inclus. Pour
en obtenir une liste, consultez le manuel fourni avec JFlex. Les options
utilisées dans notre spécification lexicale sont les suivantes:
%class Lexer
%line
%column
%cup
La première option, class Lexer, dit à JFlex d'appeler la classe générée
Lexer et d'écrire le code dans un fichier appelé
Lexer.java. L'option line active le comptage des lignes qui vous
permet d'accéder au numéro de la ligne courante par le biais de la variable
yyline. L'option column fait la même chose, mais pour les
colonnes et avec la variable yycolumn. La dernière option,
cup met JFlex dans un mode compatible avec un parseur généré par CUP.
Vous pouvez alors déclarer des variables et des fonctions membres destinées à
être utilisées dans le scanneur. Le code que l'on peut rajouter doit
être écrit en Java et est placé entre %{ et }%. Il sera
copié dans le code source de la classe lexer générée. Pour notre
spécification lexicale, deux fonctions membres doivent être
déclarées. Ces fonctions créent des objets
java_cup.runtime.Symbol. Le premier ne contient que des
informations de position sur le jeton [token] courant. Le second contient ces
informations en plus de la valeur effective du jeton.
La dernière partie de cette section contient des déclarations de macros. Les
macros sont utilisées comme abréviations d'expressions régulières. Une
déclaration de macro consiste en un identifiant de macro suivi de = et de
l'expression régulière qu'elle représente. Suit un lien vers les déclarations
de macro utilisées dans notre spécification lexicale. Un autre lien est
également fourni qui indique une liste de ce qui peut être utilisé pour créer
une expression régulière et de ce que signifie chaque élément de la liste.
Une expression régulière consiste en les éléments suivants:
caractère qui correspond à ce caractère.
'[' (Caractère|Caractère'-'Caractère)+ ']'
correspond à n'importe quel caractère de cette classe. Un caractère
doit être considéré comme un élément de la classe s'il est déclaré
dans la classe ou si son code se trouve dans l'intervalle de
caractères listé dans caractère-caractère. Ainsi,
[a0-3\n] correspond par exemple aux caractères:
a 0 1 2 3 \n.
'[^'(Caractère|Caractère'-'Caractère)+']' correspond à tous
les caractères non déclarés dans cette classe.
'"' + CaractèreDeChaîne + '"'
correspond au texte exact contenu dans les guillemets. Tous les
méta-caractères à l'exception de \ et de " perdent
leur caractère spécial à l'intérieur d'une chaîne de caractères.
'{' Identifiant '}' correspond à
toute entrée qui correspond au membre de droite de la macro de nom
"Identifiant".
.correspond à tous les caractères sauf \n.
a|bsi a et b sont des expressions
régulières, on obtient l'union des expressions régulières, à savoir qu'elle
correspond à tout ce qui correspond à a ou à b.
abest la concaténation des deux expressions régulières
a et b et correspond à a suivie de b.
a*correspond à une répétition de a zéro ou plusieurs
fois.
a+est l'équivalent de aa*: répétition de a
une ou plusieurs fois.
a?correspond à une chaîne vide ou à a.
a{n}est l'équivalent de n fois la concaténation de
a. Ainsi a{4} est par exemple l'équivalent de l'expression
aaaa. L'entier décimal n doit être positif.
a{n,m}est l'équivalent d'au moins n fois et d'au plus
m fois la concaténation de a. Ainsi a{2,4} est par
exemple l'équivalent de l'expression aaa?a?. À la fois n
et m sont des entiers décimaux non négatifs et m ne doit pas
être plus petit que n.
(a)correspond à la même entrée que a.
Dans une règle lexicale, une expression régulière r peut être précédée
par un '^' (l'opérateur de début de ligne). r ne correspond
alors à l'entrée que si elle se trouve en début de ligne. Une nouvelle ligne
commence après \r|\n|\r\n et au début de l'entrée. Le terminateur de
ligne précédente de l'entrée n'est pas consommé et peut correspondre à une
autre règle.
La dernière section de la spécification lexicale contient des expressions régulières et des actions à exécuter lorsque le scanneur rencontrera une chaîne à laquelle correspond l'expression régulière. Le scanneur va activer l'expression régulière qui a la plus longue portée. Ainsi, si il existe deux expressions régulières to et too, le scanneur va faire corespondre l'expression régulière too dans la mesure où c'est la plus longue. Si deux expressions régulières sont identiques et ont la même longueur, le scanneur fera correspondre celle qui apparaît la première dans la spécification. Si le scanneur lit la chaîne to et qu'il cherchait une expression régulière à faire correspondre à ce qu'il avait lu, il pourrait faire correspondre les deux expressions énoncées plus haut. La deuxième expression régulière reste seule en lice car elle contient une classe de caractères qui permet de prendre la chaîne to. Le scanneur prendrait alors la première expression régulière de la liste dans la mesure où elle a été déclarée la première.
"to"
[a-z]*
Des actions peuvent être attachées à chaque expression régulière activable par le scanneur quand il établit une correspondance avec elle. Les actions possibles pour chaque expression régulière sont juste des fragments de code Java. Par exemple, vous pourriez afficher quelque chose ou bien retourner au parseur le jeton que le scanneur vient de trouver. On pourrait par exemple faire comme suit pour afficher le jeton qui vient d'être trouvé et le retourner au parseur :
"+" { System.out.print(" + "); return symbol(sym.PLUS); }
"-" { System.out.print(" - "); return symbol(sym.MINUS); }
"*" { System.out.print(" * "); return symbol(sym.TIMES); }
"/" { System.out.print(" / "); return symbol(sym.DIVIDE); }
JFlex permet au programmeur d'affiner la spécification en définissant des
états lexicaux spéciaux utilisés comme conditions
initiales. YYINITIAL est un état lexical prédéfini, c'est celui dans
lequel l'analyseur se trouve avant de commencer son analyse. C'est le seul que
nous allons utiliser. Par conséquent, toutes les expressions régulières seront
reconnues en partant de cet état lexical. Cependant, chacun peut définir de
nouveaux états qui vont constituer une nouvelle branche de la machine à
états. Dans l'exemple qui suit, l'état lexical <STRING> est atteint
par une transition provenant de YYINITIAL. Les expressions régulières
définies dans cette section d'état <STRING> ne seront reconnues que
dans cette branche.
<YYINITIAL> {
\" { string.setLength(0); yybegin(STRING); }
"=" { return symbol(sym.EQ); }
"==" { return symbol(sym.EQEQ); }
"+" { return symbol(sym.PLUS); }
}
<STRING> {
\" { yybegin(YYINITIAL);
return symbol(sym.STRINGLITERAL,
string.toString()); }
[^\n\r\"\]+ { string.append( yytext() ); }
}
Dans le code ci-dessus, le scanneur commencera dans l'état
YYINITIAL. Quand il rencontrera l'expression régulières \", à savoir
quand il aura trouvé un guillemet, il passera dans l'état STRING. Les
seules expressions régulières qui pourront alors correspondre seront celles qui
ont été déclarées pour cet état. Le scanneur restera donc dans cette branche
jusqu'à ce qu'il rencontre un autre guillemet, auquel cas il retournera dans
l'état YYINITIAL. Encore une fois, pour notre calculatrice, nous
n'employons pas d'autres conditions initiales que l'état originel
YYINITIAL. Vous trouverez ci-dessous un lien vers les règles
lexicales que nous utilisons.
Voici le fichier JFlex:
/*
Commenté Par: Christopher Lopes
Nom du fichier: lcalc.flex
Pour l'utiliser: jflex lcalc.flex
et, une fois le parseur créé:
javac Lexer.java
*/
/* --------------------------Section de Code Utilisateur---------------------*/
/* importer ces classes:
java_cup.runtime.*
sym --classe créée avec CUP
*/
import java_cup.runtime.*;
import sym;
%%
/* -----------------Section des Déclarations et Options----------------------*/
/* Le nom de la classe que JFlex va créer sera Lexer.
Le code en sera écrit dans le fichier Lexer.java.
*/
%class Lexer
/* Le numéro de la ligne courante peut être obtenu par le biais de la variable
yyline et le numéro de la colonne courante dans la variable yycolumn.
*/
%line
%column
/* Permet le passage en mode de compatibilité CUP pour s'interfacer avec un
parseur généré par CUP.
*/
%cup
/* Déclarations
Le code entre %{ et %}, chacun de ces délimiteurs devant se trouver au début
d'une ligne, sera copié lettre par lettre dans le code source du Lexer. C'est
ici que vous déclarez les attributs et les fonctions qui sont utilisées à
l'intérieur des actions du scanneur.
*/
%{
/* Pour créer un nouvel objet java_cup.runtime.Symbol contenant des
informations sur le jeton courant, le jeton n'aura pas de valeur dans ce
cas. */
private Symbol symbol(int type) {
return new Symbol(type, yyline, yycolumn);
}
/* Créé également un nouvel objet java_cup.runtime.Symbol avec des
informations sur le jeton courant mais cet objet dispose d'une valeur.
*/
private Symbol symbol(int type, Object value) {
return new Symbol(type, yyline, yycolumn, value);
}
%}
/*
Déclarations de Macro
Ces déclarations sont des expressions régulières qui seront utilisées
plus loin dans la Section des Règles Lexicales.
*/
/* Un terminateur de ligne est un \r (retour chariot), un \n (saut de
ligne) ou \r\n.
*/
LineTerminator = \r|\n|\r\n
/* Un espace est un terminateur de ligne, un espace, une tabulation ou
un saut de ligne.
*/
WhiteSpace = {LineTerminator} | [ \t\f]
/* Un entier littéral est un nombre commençant par un chiffre entre un et neuf,
suivi de zéro ou plusieurs chiffres entres zéro et neuf, ou un simple zéro.
*/
dec_int_lit = 0 | [1-9][0-9]*
/* Un identifiant d'entier est un mot commençant par une lettre entre
A et Z, a et z ou un soulignement suivi de zéro ou plusieurs lettres
entre A et Z, a et z, zéro et neuf ou un underscore. */
dec_int_id = [A-Za-z_][A-Za-z_0-9]*
%%
/* ------------------------Section des Règles Lexicales----------------------*/
/* Cette section contient des expressions régulières et des actions,
i.e. du code Java qui sera exécuté quand le scanneur reconnaîtra
l'expression régulière associée.
*/
/* YYINITIAL est l'état dans lequel le lexer commence son analyse. Les
expressions régulières suivantes ne seront donc reconnues que si le
scanneur est dans l'état de départ YYINITIAL. */
<YYINITIAL> {
/* Renvoie le jeton SEMI déclaré dans la classe sym. */
";"
{ return symbol(sym.SEMI); }
/* Renvoie le jeton trouvé déclaré dans la classe sym.*/
"+"
{ System.out.print(" + "); return symbol(sym.PLUS); }
"-"
{ System.out.print(" - "); return symbol(sym.MINUS); }
"*"
{ System.out.print(" * "); return symbol(sym.TIMES); }
"/"
{ System.out.print(" / "); return symbol(sym.DIVIDE); }
"("
{ System.out.print(" ( "); return symbol(sym.LPAREN); }
")"
{ System.out.print(" ) "); return symbol(sym.RPAREN); }
/* Si un entier est trouvé, on retourne le jeton NUMBER qui représente un
entier, la valeur de cet entier se trouve dans la chaîne de caractères yytext
qui va être transformée en entier avant d'être renvoyée.
*/
{dec_int_lit}
{ System.out.print(yytext());
return symbol(sym.NUMBER, new Integer(yytext())); }
/* Si un identifiant est trouvé, l'afficher, renvoyer le jeton ID qui
représente un identifiant et la valeur par défaut de 1 qui est donnée à tous
les identifiants. */
{dec_int_id}
{ System.out.print(yytext());
return symbol(sym.ID, new Integer(1));}
/* Ne rien faire si l'on rencontre un espace */
{WhiteSpace}
{ /* il suffit d'ignorer ce que l'on a trouvé */ }
}
/* Aucun jeton n'a été trouvé ce qui provoque une erreur. Affiche un message
'Illegal character' qui contient le caractère illégal trouvé.*/
.
{ throw new Error("Illegal character <"+yytext()+">");}
C'est la spécification lexicale utilisée par notre calculatrice. Vous y
trouverez de nombreux commentaires expliquant ce qui se passe. Il peut être
copié, de même que les fichiers Main et CUP fournis afin de faire
fonctionner ce projet exemple. Les instructions pour savoir comment
préparer les fichiers et faire tourner la calculatrice sont
fournies. Le JDK, JFlex et CUP sont nécessaires pour le
faire et peuvent être gratuitement téléchargés sur les sites web
mentionnés dans cet article.
Pour plus d'informations sur JFlex, veuillez consulter le manuel JFlex disponible quand vous téléchargez JFlex sur le site mentionné dans cet article.
Le but de CUP dans ce projet est de construire un analyseur syntaxique pour notre calculatrice. Cet analyseur syntaxique, ou parseur, vérifiera les entrées de notre calculatrice et s'assurera que celles-ci sont syntaxiquement correctes. Tout cela pour dire que les expressions données en entrée sont rangées dans un ordre valide conforme à notre spécification de syntaxe.
La spécification de syntaxe pour un fichier CUP est divisée en quatre sections.
Cette section fournit des déclarations préliminaires et diverses pour
spécifier comment le parseur va être généré et afin de rajouter du
code. Cette section est optionnelle et son inclusion n'est pas
nécessaire dans un fichier de spécification CUP. Pour notre
calculatrice, nous allons mettre trois éléments dans cette section. Le
premier va être une déclaration d'importation de paquetage. Nous
allons importer la classe java_cup.runtime.*.
import java_cup.runtime.*;
L'élément que nous allons ensuite ajouter est du code pour le parseur. Le code
pour le parseur sera ajouté directement dans la classe générée par le
parseur. Cet élément commence avec parser code {: et se finit
avec :} : tout ce qui se situe entre les deux est directement
inséré. Dans le code pour le parseur, nous allons changer deux
méthodes: report_error et report_fatal_error. Nous allons
modifier ces deux méthodes de telle sorte que si une erreur syntaxique
ou une erreur fatale est détectée dans l'entrée, le message d'erreur
qui sera affiché contiendra les numéro de ligne et de colonne dans
l'erreur où l'erreur est intervenue. Cette information supplémentaire
dans les messages d'erreur peut se révéler très utile pour déterminer
l'emplacement des erreurs dans l'entrée.
Le dernier élément que nous allons ajouter dans cette section indique comment
le parseur devrait demander le prochain jeton au scanneur. Il est de la forme
scan with {: ... :}. Nous allons utiliser cette fonctionnalité pour dire
au parseur d'appeler le scanneur que nous avons créé avec JFlex.
scan with {: return lexer.yylex(); :};
Cette section contient la liste des symboles ainsi que les déclarations en
charge du nommage et du typage de chaque terminal et non-terminal. Cette
section est obligatoire dans une spécification CUP. Les terminaux sont déclarés
avec la syntaxe terminal nom_de_classe nom1, nom2, ...;.
Nom_de_classe est le type de l'objet, par exemple Integer. Si aucun
nom de classe n'est donné, le lexeur n'a pas de contenu à passer au parseur
pour le terminal. Après le nom de classe, les noms des terminaux que vous
voulez déclarer de ce type sont déclarés comme suit:
terminal PLUS, MINUS, TIMES, DIVIDE, SEMI;
terminal Integer NUMBER;
Veuillez noter que seul NUMBER dispose d'un nom de classe. Dans notre
exemple, c'est le terminal qui porte du sens. Par exemple, quand le lexeur
reconnait un PLUS, il passe le code associé au parseur. Quand il reconnait
un NUMBER, il passe non seulement le code associé à NUMBER mais aussi
la valeur associée au type encapsulant, Integer. Les non-terminaux sont
déclarés de la même manière. La seule différence, c'est que le début de la
déclaration réflète le fait qu'il s'agit d'un non-terminal plutôt que d'un
terminal.
non terminal expr_list, expr_part;
non terminal Integer expr;
Cette section spécifie la priorité et l'associativité des terminaux : c'est
une section qu'il n'est pas nécessaire d'inclure. Elle peut être utilisée lors
de l'analyse de terminaux ambigus. Au lieu d'utiliser cette section,
vous pouvez structurer votre grammaire de manière à la rendre non
ambiguë. Par exemple, TIMES devrait avoir une priorité plus
importante que PLUS. Quand le parseur traite une expression telle
que 5+4*3, il ne sait pas si l'expression doit être calculée
5+(4*3) ou (5+4)*3. Pour éliminer cette ambiguïté, cette
section doit déclarer la priorité comme indiqué plus bas. La priorité
la plus grande est mise à la fin de la liste et l'importance de la
priorité diminue à mesure que l'on remonte. Le mot left indique
que l'associativité des terminaux à ce niveau de priorité va de gauche
à droite.
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;
Pour structurer une grammaire afin d'éliminer l'ambiguïté, il vous faut créer
une structure similaire à celle qui figure ci-dessous. Cette structure élimine
l'ambiguïté dans la mesure où TIMES se trouve plus bas dans la grammaire
que PLUS. TIMES sera donc traité avant PLUS en
remontant dans la grammaire.
La dernière section de la syntaxe de la spécification contient la grammaire du
parseur. Chaque règle de production de la grammaire possède un membre
de gauche non-terminal suivi de ::= suivi lui-même de zéro ou
plusieurs actions, terminaux ou non-terminaux. On finit l'expression
de la règle avec un point-virgule. Chaque symbole du membre de droite
peut recevoir un nom, nom qui peut être utilisé pour transporter de
l'information (à savoir une valeur) vers le haut de l'arbre d'analyse
syntaxique. Un nom est donné en mettant un deux-point après le symbole
puis le nom du symbole, exactement comme ce qui suit où e1 et
e2 sont des noms pour expr. Le membre de gauche reçoit
automatiquement le nom RESULT. Un exemple d'utilisation du nom
RESULT est disponible plus loin dans cette section.
expr ::= expr:e1 PLUS expr:e2
Les noms doivent être uniques dans la règle de production. S'il existe
plusieurs productions pour le même non-terminal, elles peuvent être déclarées
ensemble et séparées par |. Le point-virgule doit alors être placé à la
fin de la dernière production comme dans l'exemple suivant.
expr ::= expr PLUS expr
| expr MINUS expr
;
Des actions peuvent également être insérées dans les règles de
production. L'action consiste en du code Java et sera exécutée quand
la production aura été reconnue. L'action est placée entre les
délimiteurs {: et :}. Un exemple partiel de grammaire avec
ces options est disponible ci-dessous.
expr ::= factor:f PLUS expr:e
{: RESULT = new Integer(f.intValue() + e.intValue()); :}
|
factor:f MINUS expr:e
{: RESULT = new Integer(f.intValue() - e.intValue()); :}
|
factor:f
{: RESULT = new Integer(f.intValue()); :}
;
Voici le fichier ycalc.cup de syntaxe de spécification pour CUP. La
grammaire qu'il contient vaut le coup d'être étudiée.
/*
Commenté par: Christopher Lopes
Nom du fichier: ycalc.cup
Pour l'utiliser: java java_cup.Main > ycalc.cup
*/
/* ----------------------Section des déclarations préliminaires--------------*/
/* Import de la classe java_cup.runtime.* */
import java_cup.runtime.*;
/* Code pour le parseur afin qu'il puisse s'interfacer avec le scanneur créé
avec JFlex. On change également la manière de rapporter les erreurs en
incluant la ligne et la colonne de l'erreur. */
parser code {:
Lexer lexer;
public parser(Lexer lexer) {
this.lexer = lexer;
}
/* Change la méthode report_error de manière à ce qu'elle affiche la ligne et
la colonne auxquelles est apparue l'erreur. La cause de l'erreur est également
affichée: elle est passée à la méthode par le biais de la String
"message" */
public void report_error(String message, Object info) {
/* Crée un StringBuffer appelé 'm' qui contient la chaîne de caractères
'Error'. */
StringBuffer m = new StringBuffer("Error");
/* Vérifie si l'information passée à la méthode est du même type que le type
java_cup.runtime.Symbol. */
if (info instanceof java_cup.runtime.Symbol) {
/* Déclare un objet java_cup.runtime.Symbol 's' qui transtype les informations
de l'objet en un objet du type java_cup.runtime.Symbol. */
java_cup.runtime.Symbol s = ((java_cup.runtime.Symbol) info);
/* Vérifie si le numéro de ligne de l'entrée est positif ou nul. */
if (s.left >= 0) {
/* Ajoute le numéro de ligne de l'erreur à la fin du message d'erreur contenu
dans le StringBuffer. */
m.append(" in line "+(s.left+1));
/* Vérifie si le numéro de colonne de l'entrée est positif ou nul. */
if (s.right >= 0)
/* Ajoute le numéro de colonne de l'erreur à la fin du message d'erreur
contenu dans le StringBuffer. */
m.append(", column "+(s.right+1));
}
}
/* Ajoute le message qui a été passé à la méthode à la fin du message
d'erreur. */
m.append(" : "+message);
/* Affiche le contenu du StringBuffer 'm' qui contient un message
d'erreur sur une ligne. */
System.err.println(m);
}
/* Modifie la méthode report_fatal_error de manière à ce qu'elle affiche le
numéro de ligne et le numéro de colonne à laquelle l'erreur fatale est
survenue. La cause de l'erreur fatale, passée à la méthode dans l'objet
'message' est également affichée.*/
public void report_fatal_error(String message, Object info) {
report_error(message, info);
System.exit(1);
}
:};
/* Utiliser le scanneur créé avec JFlex */
scan with {: return lexer.yylex(); :};
/* ------------Section de Déclaration des Terminaux et non Terminaux---------*/
/* Terminaux (jetons retournés par le scanneur).
Les terminaux qui ne possèdent pas de valeur sont déclarés en premier, suivis
des terminaux qui ont une valeur, dans notre cas une valeur entière.
*/
terminal SEMI, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN;
terminal Integer NUMBER, ID;
/* Non Terminaux utilisés dans la section grammaire.
Les non-terminaux qui ont une valeur objet sont déclarés en premier, suivis des
non-terminaux qui ont une valeur entière. Une valeur objet signifie qu'elle
peut être de n'importe quel type, qu'aucun type spécifique n'est imposé. Cela
pourrait par exemple être un entier ou une String...
*/
non terminal Object expr_list, expr_part;
non terminal Integer expr, factor, term;
/* -------------Section de Priorité et Associativité des Terminaux----------*/
/* La priorité des non-terminaux peut être définie ici. Si vous définissez les
règles de priorité ici, vous n'avez plus à vous en soucier dans la section
Grammaire. TIMES devrait par exemple avoir une priorité plus haute que PLUS.
Les règles de priorité définies ici devraient ressembler à ce qui suit avec la
convention que la priorité augmente avec les numéros de ligne dans le fichier.
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;
*/
/* ----------------------------Section Grammaire-----------------------------*/
/* La grammaire de notre parseur. */
expr_list ::= expr_list expr_part
| expr_part
expr_part ::= expr SEMI
expr ::= factor PLUS expr
| factor MINUS expr
| factor
factor ::= factor TIMES term
| factor DIVIDE term
| term
primary ::= LPAREN expr RPAREN
| NUMBER
| ID
/* 'expr_list' est le point de départ de notre grammaire. Il peut produire un
autre 'expr_list' suivi d'un 'expr_part' ou il peut produire seulement un
'expr_part'. Le membre de gauche des non-terminaux 'expr_list' et 'expr_part'
qui apparaissent dans le membre de droite de la règle de production doivent
être présents. Les membres de droite de ces non-terminaux doivent alors être
traités de la même manière, à savoir que s'il se trouve un non-terminal dans le
membre de droite de ces productions, les productions de ces non-terminaux
doivent être trouvées et ces membres de droite traités. Ce processus suit son
cours jusqu'à ce que seuls des terminaux apparaissent dans le membre de droite
de la règle de production. Nous pouvons alors aller consulter la grammaire pour
en ramener les valeurs assignées à un terminal. */
expr_list ::= expr_list expr_part
| expr_part;
/* 'expr_part' est une 'expr' suivi du terminal 'SEMI'. Le ':e' après le non
terminal 'expr' est une étiquette qui est utilisée pour accéder à la valeur de
'expr' qui se trouve être un entier. L'action associée à cette règle de
production se trouve entre {: et :}. Cette action va afficher la ligne " = + e"
où e est la valeur de 'expr'. Avant l'exécution de l'action, il nous faut
descendre dans la grammaire compte tenu du fait que 'expr' est un non-terminal.
Toutes les fois que l'on rencontre un non-terminal dans le membre de droite
d'une règle de production, il nous faut trouver le membre de droite de
ce non-terminal jusqu'à ce qu'il n'y ait plus de non-terminaux dans le
membre de droite. Ainsi, quand nous avons fini de parcourir la
grammaire et que nous ne rencontrons plus de non-terminaux dans les
productions du membre de droite, nous revenons à 'expr': celui-ci
contient alors une valeur entière. */
expr_part ::= expr:e
{: System.out.println(" = " + e); :}
SEMI
;
/* 'expr' peut conduire à 'factor PLUS expr', 'factor MINUS expr' ou à
'factor'. Les productions 'TIMES' et 'DIVIDE' n'apparaissent pas à ce
niveau. Elles se trouvent plus bas dans la grammaire ce qui leur donne une
priorité plus grande. Les actions du membre de droite du non-terminal 'expr'
renvoient une valeur à 'expr'. La valeur créée est un entier et se trouve
stocké dans 'RESULT'. RESULT est l'étiquette assignée automatiquement au
membre de gauche, dans ce cas 'expr'. Si le membre de droite ne comporte que
'factor', 'f' se réfère au non-terminal 'factor'. La valeur de 'f' se récupère
via la méthode 'intValue()' et se trouvera stockée dans 'RESULT'. Dans les deux
autres cas, 'f' et 'e' se réfèrent aux non-terminaux 'factor' et 'expr'
respectivement avec un non-terminal entre les deux, soit 'PLUS', soit
'MINUS'. La valeur de chacun d'entre eux se récupère avec la même méthode
'intValue'. Les valeurs seront soit ajoutées soit soustraites, l'entier
résultant étant stocké dans 'RESULT'.*/
expr ::= factor:f PLUS expr:e
{: RESULT = new Integer(f.intValue() + e.intValue()); :}
|
factor:f MINUS expr:e
{: RESULT = new Integer(f.intValue() - e.intValue()); :}
|
factor:f
{: RESULT = new Integer(f.intValue()); :}
;
/* 'factor' peut donner 'factor TIMES term', 'factor DIVIDE term' ou
'term'. Compte tenu du fait que les règles de production de TIMES et DIVIDE se
trouvent plus bas dans la grammaire que celles de 'PLUS' et 'MINUS', elles
auront une priorité plus importante. Dans le membre de droite de 'factor', on
trouve le même genre d'actions que dans celui de 'expr'. La seule différence
tient dans les opérations qui sont effectuées sur les valeurs retournées par
'intValue()', multiplié et divisé au lieu de plus et moins. */
factor ::= factor:f TIMES term:t
{: RESULT = new Integer(f.intValue() * t.intValue()); :}
|
factor:f DIVIDE term:t
{: RESULT = new Integer(f.intValue() / t.intValue()); :}
|
term:t
{: RESULT = new Integer(t.intValue()); :}
;
/* 'term' peut conduire à 'LPAREN expr RPAREN', 'NUMBER' ou 'ID'. La première
production contient le non-terminal 'expr' ce qui fait que son membre de gauche
doit être trouvé et traité. Le membre de droite suivant n'a pas de
non-terminaux: la grammaire s'arrête donc là et remonte. La valeur
récupérée lors du passage sur le jeton 'NUMBER' est alors
remontée. 'RESULT' prend alors 'n', qui se réfère à 'NUMBER', comme
action de cette production. La même action est engagée pour 'ID' mis à
part le fait que le 'i' se réfère à 'ID'. 'ID' est également le seul
élément du membre droit de la production. Compte tenu du fait que 'ID'
est un terminal, la grammaire s'arrête là et remonte l'arbre. */
primary ::= LPAREN expr:e RPAREN
{: RESULT = e; :}
|
NUMBER:n
{: RESULT = n; :}
|
ID:i
{: RESULT = i; :}
;
C'est la spécification lexicale utilisée par notre calculatrice. Vous y
trouverez de nombreux commentaires expliquant ce qui se passe. Il peut être
copié, de même que les fichiers Main et CUP fournis afin de faire
tourner cet exemple de projet. Les instructions pour savoir comment préparer
les fichiers et faire tourner la calculatrice sont fournies. Le JDK,
JFlex et CUP sont nécessaires pour le faire et peuvent être
gratuitement téléchargés sur les sites web mentionnés dans cet article.
Pour plus d'informations sur CUP, veuillez consulter le manuel CUP disponible sur le site mentionné dans cet article.
Il existe plus d'une manière d'écrire le programme principal pour notre
projet. Une première façon de faire attend de l'utilisateur qu'il entre des
données pendant l'exécution du programme. Une autre manière de procéder est de
donner un nom de fichier d'entrée à l'exécution du programme. Le programme
principal présenté ici implante la seconde méthode. La première chose que nous
faisons est d'importer trois classes que nous allons utiliser. La première
classe est notre parseur, la deuxième est java_cup.runtime.Symbol et la
troisième est l'ensemble de classes java.io.*.
On déclare alors la classe Main. Nous allons y appeler le parseur afin de
commencer l'analyse syntaxique du fichier d'entrée. Le parseur va alors appeler
le scanneur qui va analyser lexicalement l'entrée quand le parseur demandera le
jeton suivant du fichier d'entrée. La classe Main contient deux
étapes. Elle met d'abord la variable do_debug_parse à false puis
définit une méthode appelée main.
On passe à main un tableau de chaîne de caractères qui contient les
paramètres passés sur la ligne de commande au démarrage du programme. Dans
notre cas, le premier élément de la chaîne contient le nom du fichier texte à
traiter. La méthode entre alors dans un bloc try dans lequel se fait
l'appel effectif du parseur. Le bloc try permet que tout ce qui se trouve
à l'intérieur soit essayé. Si des problèmes surviennent, le programme sortira
de ce bloc. La première ligne dans le bloc try crée un nouvel objet
parseur. Le parseur invoque un nouvel objet Lexer. Celui-ci utilise la
chaîne passée à main comme entrée. La seconde ligne démarre alors le
parseur. Le code correspondant à ceci suit:
try {
parser p = new parser(new Lexer(new FileReader(argv[0])));
Object result = p.parse().value;
}
À la suite du bloc try, on trouve un bloc catch. Le but de
ce dernier est de réparer les erreurs qui ont pu intervenir à
l'intérieur du bloc try. Le bloc catch va récupérer
l'exception, à savoir la raison pour laquelle on est sorti en urgence
du bloc try, et faire ce qu'il faut pour arranger les choses
avant la fin du programme. Dans notre exemple, rien n'est fait à
l'intérieur du bloc catch. Après le bloc catch, on trouve la
méthode finally. Nous ne faisons rien non plus dans cette
méthode. Voici le code du bloc catch et de la méthode finally.
catch (Exception e) {
/* do cleanup here -- possibly rethrow e */
} finally {
/* do close out here */
}
}
Voilà qui clôture le contenu de la méthode main et de la classe
Main. Nous avons créé uen calculatrice simple avec JFlex comme analyseur
lexical et CUP comme analyseur syntaxique.
Voici le fichier Java:
/*
Commenté Par: Christopher Lopes
Nom du fichier: Main.java
Pour l'utiliser: après que le scanneur, lcalc.flex, et le parseur, ycalc.cup,
aient été créés, javac Main.java
Pour le lancer: java Main test.txt
où test.txt est le fichier de test de notre calculatrice.
*/
/* Import des classes nécessaires. La classe que nous avons créé pour le
parseur, la classe de runtime standard de java et une classe d'e/s.
*/
import parser;
import java_cup.runtime.Symbol;
import java.io.*;
class Main {
static boolean do_debug_parse = false;
static public void main(String argv[]) {
/* lancer le parseur */
try {
parser p = new parser(new Lexer(new
FileReader(argv[0])));
Object result = p.parse().value;
} catch (Exception e) {
/* nettoyer à cet endroit -- éventuellement relancer e */
} finally {
/* terminer proprement ici */
}
}
}
C'est le programme principal utilisé par notre calculatrice. Vous y
trouverez de nombreux commentaires expliquant ce qui se passe. Il peut être
copié, de même que les fichiers Main et CUP fournis afin de faire
tourner ce projet exemple. Les instructions pour savoir comment préparer les
fichiers et faire tourner la calculatrice sont fournies. Le JDK,
JFlex et CUP sont nécessaires pour le faire et peuvent être
gratuitement téléchargés sur les sites web mentionnés dans cet article.
Pour mettre en place les fichiers nécessaire à l'exécution de la calculatrice,
vous devez d'abord utiliser JFlex sur le fichier de spécification
lcalc.flex. Cela va produire le fichier Lexer.java. L'étape suivante
est de mettre en place le fichier CUP ycalc.cup. Après, vous devez
compiler le fichier Lexer.java créé par JFlex. Vous finissez alors le
processus en compilant le fichier Main.java. Pour faire ce qui est décrit
ici, vous devez donc faire les commandes suivantes:
jflex lcalc.flex
java java_cup.Main < ycalc.cup
javac Lexer.java
javac Main.java
Pour lancer alors la calculatrice, vous devez taper ce qui suit sur la
ligne de commande. Le fichier test.txt est le fichier d'entrée de
la calculatrice destiné à être analysé.
java Main test.txt
Voici un exemple de fichier d'entrée.
2+4;
5*(6-3)+1;
6/3*5+20;
4*76/31;
La sortie correspondant à ce fichier devrait être:
2 + 4 = 6
5 * ( 6 - 3 ) + 1 = 16
6 / 3 * 5 + 20 = 30
4 * 76 / 31 = 9
Outils de Construction de Compilateurs, partie I, avril 1999.
Outils de Construction de Compilateurs, partie II, mai 1999.
Copyright © 1999, Christopher Lopes, Paru dans le numéro 41 de la Linux Gazette en mai 1999
Adaptation française de Pierre Tane tanep@bigfoot.com