Lex et yacc sont des outils de génération d'analyseurs lexicaux (Lex) et syntaxiques (Yacc) en langage C. Yacc est l'acronyme de Yet Another Compiler Compiler.
Du point de vue de la classification des langages, Lex est capable de traiter des langages de type 3 (réguliers), et Yacc fournit le code nécessaire à l'analyse de langages de type 2 (non-contextuels).
La grammaire utilisée
On se propose d'écrire une mini calculatrice. Pour cela, la grammaire utilisée n'est pas compliquée. Nous évaluons des expressions, qui peuvent être soit un nombre, soit une expression entourée de parenthèses, soit une expression plus une autre expression, etc... Ainsi, tu le vois, la grammaire utilisée est récursive.
L'analyse du texte source se réalise en fait en deux étapes. La première est ce que l'on appelle l'analyse lexicale, qui fait partie du domaine de compétences de Lex, par l'intermédiaire de la fonction yylex(), qui se charge de consommer les terminaux (voir plus bas). Elle va les signaler à l'analyseur syntaxique, rôle de Yacc, grâce à la fonction yyparse().
Utilisation de Lex dans l'analyse lexicale
Le but de l'analyse lexicale est de transformer une suite de symboles en terminaux (un terminal peut être par exemple un nombre, un signe "+", un identificateur, etc...). Une fois cette transformation effectuée, la main est repassée à l'analyseur syntaxique (voir ci-dessous). Le but de l'analyseur lexical est donc de "consommer" des symboles et de les fournir à l'analyseur syntaxique.
Un fichier de description pour Lex est formé de trois parties, selon le schéma suivant ;
déclarations %% productions %% code additionnel
dans lequel aucune partie n'est obligatoire. Cependant, le premier %% l'est, afin d'indiquer la séparation entre les déclarations et les productions.
La première partie d'un fichier Lex
Cette partie d'un fichier Lex peut contenir :
- Du code écrit dans le langage cible, encadré par %{ et %}, qui se retrouvera au début du fichier synthétisé par Lex. C'est ici que l'on va spécifier les fichiers à inclure. Lex recopie tel quel tout ce qui est écrit entre ces deux signes, qui devront toujours être placés en début de ligne.
- Des expressions régulières définissant des notions non terminales, telles que lettre, chiffre et nombre. Ces spécifications sont de la forme : notion expression_régulière. Les notions ainsi définies pourront alors être utilisées dans la suite de la première partie du fichier, ainsi que dans la deuxième partie, en les parenthésant par { et }.
Exemple :
%{
#include "calc.h"
#include <stdio.h>
#include <stdlib.h>
%}
/* Expressions régulières */
/* ---------------------- */
blancs [\t
]+
lettre [A-Za-z]
chiffre10 [0-9] /* base 10 */
chiffre16 [0-9A-Fa-f] /* base 16 */
identificateur {lettre}(_|{lettre}|{chiffre10})*
entier10 {chiffre10}+
L'exemple en lui-même est clair, mais regardons d'un peu plus près comment sont formées les expressions régulières.
Les expressions régulières
Symbole Signification
x le caractère "x"
. n'importe quel caractère sauf
[xyz] soit x, soit y, soit z
[^bz] tous les caractères, sauf b et z
[a-z] n'importe quel caractère entre a et z
[^a-z] tous les caractères, sauf ceux compris entre a et z
R* zéro R ou plus, où R est n'importe quelle expression régulière
R+ un R ou plus
R? zéro ou un R (c'est-à-dire un R optionnel)
R{2,5} entre 2 et 5 R
R{2,} 2 R ou plus
R{2} exactement 2 R
"[xyz\"foo" la chaîne "[xyz"foo"
{NOTION} l'expansion de la notion NOTION définie plus haut
\X si X est un "a", "b", "f", "n", "r", "t", ou "v", représente l'interprétation ANSI-C de \X.
\0 le caractère ASCII 0
\123 le caractère dont le code ASCII est 123, en octal
\x2A le caractère dont le code ASCII est 2A, en hexadécimal
RS R suivi de S
R|S R ou S
R/S R, seulement s'il est suivi par S
^R R, mais seulement en début de ligne
R$ R, mais seulement en fin de ligne
<<EOF>> fin de fichier
Ainsi, la définition :
identificateur {lettre}(_|{lettre}|{chiffre10})*
reconnaitra comme identificateur les mots "integer", "une_variable", "a1", mais pas "_ident" ni "1variable". Facile, non ?
Enfin, comme dernier exemple, voici la définition d'un réel :
chiffre [0-9]
entier {chiffre}+
exposant [eE][+-]?{entier}
reel {entier}("."{entier})?{exposant}?
Deuxième partie d'un fichier Lex : les productions
Cette partie sert à indiquer à Lex ce qu'il devra faire lorsqu'il rencontrera telle ou telle notion. Celle-ci peut contenir :
- Des spécifications écrites dans le langage cible, encadrées par %{ et %} (toujours placés en début de ligne), qui seront placées au début de la fonction yylex(), la fonction chargée de consommer les terminaux, et qui renvoit un entier.
- Des productions de la forme : expression_régulière action. Si action est absente, Lex recopiera les caractères tels quels sur la sortie standard. Si action est présente, elle devra être écrite en langage cible. Si celle-ci comporte plus d'une seule instruction ou ne peut tenir sur une seule ligne, elle devra être parenthésée par { et }.
Il faut de plus savoir que les commentaires tels que /* ... */ ne peuvent être présents dans la deuxième partie d'un fichier Lex que s'il sont placés dans les actions parenthésées. Dans le cas contraire, ceux-ci seraient considérés par Lex comme des expressions régulières ou des actions, ce qui donnerait lieu à des messages d'erreur, ou, au mieux, à un comportement inattendu.
Enfin, la variable yytext désigne dans les actions les caractères acceptés par expression_régulière. Il s'agit d'un tableau de caractère de longueur yyleng (donc défini comme char yytext[yyleng]).
Exemple :
%%
[ \t]+$ ;
[ \t]+ printf(" ");
Ce programme supprime tous les espaces inutiles dans un fichier. Tu auras d'ailleurs noté que Lex permet de faire énormément de choses, et pas seulement des interpréteurs et des compilateurs (Il peut par exemple servir à la recherche/remplacement dans un texte, etc...).
Troisième partie d'un fichier Lex : le code additionnel
Tu peux mettre dans cette partie facultative tous le code que tu veux. Si tu ne mets rien, Lex considère que c'est juste :
main()
{
yylex();
}
Conclusion sur Lex
Comme tu as pu le voir, Lex est très simple d'emploi (en tout cas dans les cas simples tels que ceux présentés). Pourtant, nous n'avons pas fait le tour de toutes les fonctionnalités de Lex, et je t'invite donc à consulter la page de manuel pour une information plus détaillée.
L'analyse grammaticale avec Yacc
Pour les puristes : Yacc (Yet Another Compiler Compiler) est un programme destiné à compiler une grammaire du type LALR(1) et à produire le texte source d'un analyseur syntaxique du langage engendré par cette grammaire. Il est aussi possible, en plus de la vérification de la syntaxe de la grammaire, de lui faire effectuer des actions sémantiques.
De la même manière que pour un fichier Lex, un fichier Yacc se compose de trois parties, de cette façon :
déclarations %% productions %% code additionnel
seuls le premier séparateur %% et la deuxième partie étant obligatoires.
La première partie d'un fichier Yacc
La première partie d'un fichier Yacc peut contenir :
- Des spécifications écrites dans le langage cible, placées entre %{ et %}, ces deux symboles étant obligatoirement en début de ligne.
- La déclaration des terminaux pouvant être rencontrés, grâce au mot-clé %token
- Le type de donnée du terminal courant, avec le mot-clé %union
- Des informations donnant la priorité et l'associativité des opérateurs.
- L'axiome de la grammaire, avec le mot-clé %start (si celui-ci n'est pas précisé, l'axiome de la grammaire est la première production de la deuxième partie).
La variable yylval, déclarée implicitement du type de %union a une importance fondamentale dans le fichier, puisque celle-ci contient la description du dernier terminal lu.
La deuxième partie d'un fichier Yacc
Cette partie, qui ne peut pas être vide, contient :
- des déclarations et/ou définitions encadrées par %{ et %} ;
- des productions de la grammaire du langage choisi.
Ces productions s'écrivent sous la forme générale :
notion_non_terminale:
corps_1 { action_sémantique_1 }
| corps_2 { action_sémantique_2 }
| ...
| corps_n { action_sémantique_n }
;
sachant que les corps_i peuvent être des notions terminales ou non terminales du langage.
Et enfin, on trouve...
La troisième partie d'un fichier Yacc
Cette partie, qui comporte le code additionnel, devra obligatoirement comporter une déclaration du main() (qui devra appeler la fonction yyparse()), et de la fonction yyerror(char *message), appelée lorsqu'une erreur de syntaxe est trouvée.
Conclusion sur Yacc
Ici aussi, nous sommes loin d'avoir fait le tour de Yacc, et je ne t'ai d'ailleurs pas tout expliqué. Nous allons préciser certains points dans l'exemple qui va suivre.
Un exemple : un mini interprète d'expressions
Cet interprète d'expressions est capable de calculer la valeur de n'importe quelle expression mathématique exprimée à l'aide de nombres réels et des opérateurs "+", "-" (considéré en tant qu'opérateur unaire et binaire, ce qui signifie que "5-3" et "-2" seront des expressions valides), "*", "/", "^" (opérateur puissance). Cet interprète ne pourra pas faire appel à des fonctions ni à des variables.
Le source Lex du mini-interprète d'expressions
Voici tout d'abord le source complet :
%{
#include "global.h"
#include "calc.h"
#include <stdlib.h>
%}
blancs [ \t]+
chiffre [0-9]
entier {chiffre}+
exposant [eE][+-]?{entier}
reel {entier}("."{entier})?{exposant}?
%%
{blancs} { /* On ignore */ }
{reel} {
yylval=atof(yytext);
return(NOMBRE);
}
"+" return(PLUS);
"-" return(MOINS);
"*" return(FOIS);
"/" return(DIVISE);
"^" return(PUISSANCE);
"(" return(PARENTHESE_GAUCHE);
")" return(PARENTHESE_DROITE);
"
" return(FIN);
Explication de texte :
- La première partie du fichier permet d'inclure le fichier calc.h, qui sera généré plus tard par Yacc et qui contiendra la définition des identificateurs NOMBRE, PLUS, MOINS, etc... On en profite au passage pour inclure la librairie stdlib, qui contient l'en-tête de la fonction atof(), utilisée par la suite. On déclare la notion "réel" qui sera utilisée plus bas. On peut aussi signaler que les structures manipulées seront du type double, par une directive #define YYSTYPE double, faite dans le fichier global.h. D'ailleurs, yylval est du type YYSTYPE.
- La deuxième partie sert à signaler à l'analyseur syntaxique quel terminal a été rencontré. S'il s'agit d'un NOMBRE, alors il faut stocker sa valeur dans la variable yylval, afin qu'elle puisse être utilisée ultérieurement.
- Enfin, la troisième partie n'existe pas, puisqu'on ne veut pas que Lex mette un main() dans le texte source créé. Le main() sera fait dans la partie sur Yacc.
Le source Yacc du mini-interprète d'expressions
C'est le plus important, et le plus intéressant. Le voici :
%{
#include "global.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
%}
%token NOMBRE
%token PLUS MOINS FOIS DIVISE PUISSANCE
%token PARENTHESE_GAUCHE PARENTHESE_DROITE
%token FIN
%left PLUS MOINS
%left FOIS DIVISE
%left NEG
%right PUISSANCE
%start Input
%%
Input:
/* Vide */
| Input Ligne
;
Ligne:
FIN
| Expression FIN { printf("Résultat : %f
",$1); }
;
Expression:
NOMBRE { $$=$1; }
| Expression PLUS Expression { $$=$1+$3; }
| Expression MOINS Expression { $$=$1-$3; }
| Expression FOIS Expression { $$=$1*$3; }
| Expression DIVISE Expression { $$=$1/$3; }
| MOINS Expression %prec NEG { $$=-$2; }
| Expression PUISSANCE Expression { $$=pow($1,$3); }
| PARENTHESE_GAUCHE Expression PARENTHESE_DROITE { $$=$2; }
;
%%
int yyerror(char *s)
{
printf("%s
",s);
}
int main(void)
{
yyparse();
}
Bon, un peu plus compliqué n'est-ce pas ? En fait, pas tant que ça. Après avoir inclus les fichiers habituels, tu utilises la directive %token pour déclarer les terminaux pouvant être rencontrés. Il n'y a, dans ce cas, aucun ordre à respecter.
Ensuite, ça se complique avec les directives %left et %right. Celle-ci servent à donner l'associativité des opérateurs, ainsi que leur précédences. On définit donc les opérateurs par ordre croissant de priorité. Ainsi 1+2*3 est evalué comme 1+(2*3). D'autre part, le fait que l'on choisisse "left" ou "right" dépend du comportement que tu voudras donner à ton opérateur. Pour un opérateur (ici, "+") associatif à gauche, a+b+c sera évalué comme (a+b)+c. Inversement, pour l'associativité à droite, a^b^c est évalué comme a^(b^c). C'est pas si compliqué, hein ?
On signale ensuite à Yacc que l'axiome de départ sera Input, c'est-à-dire qu'il se place au départ dans un état tel que toute entrée sera considérée comme un Input. A ce sujet, note la récursion dans la définition de Input. Cela permet de traiter une entrée de taille inconnue. Pour des raisons internes à Yacc, il est préférable d'utiliser
Input: /* Vide */ | Input Ligne ;
plutôt que :
Input: /* Vide */ | Ligne Input ;
(Cela permet une réduction dès que c'est possible).
Passons à la définition de Ligne. Si la définition seule ne pose pas de problème, peut-être es-tu intrigué par le $1 ? C'est simple, $1 fait référence à la valeur renvoyée par la première notion de la production. De la même façon pour $2, $3,... Par contre, $$ est la valeur renvoyé par la production. Ainsi, dans la définition d' Expression, lorsqu'on rencontre Expression "+" Expression on fait l'action $$=$1+$3, qui ne fait qu'ajouter...
Dans un autre ordre d'idée, regarde la ligne définissant le moins unaire. Le %prec sert juste à indiquer que la priorité de ceci est celle de NEG.
Enfin, la troisième partie du fichier est banale, puisqu'elle se contente d'appeler yyparse().
Comment faire marcher cet exemple...
Si le fichier Lex s'appelle calc.lex et le fichier Yacc calc.y, il suffit de faire la procédure suivante :
bison -d calc.y mv calc.tab.h calc.h mv calc.tab.c calc.y.c flex calc.lex mv lex.yy.c calc.lex.c gcc -c calc.lex.c -o calc.lex.o gcc -c calc.y.c -o calc.y.o gcc -o calc calc.lex.o calc.y.o -ll -lm [éventuellement -lfl]
Note bien que tu devras créer le fichier global.h pour que cela compile. Ce fichier contiendra :
#define YYSTYPE double extern YYSTYPE yylval;
Je dispose uniquement de bison et de flex, au lieu de lex et de yacc, mais cela devrait fonctionner de la même façon, à part le nom des fichiers générés.
L'appel à bison (le Yacc de GNU) avec l'option "-d" crée le fichier calc.tab.h pour définir les terminaux. On appelle flex (le Lex de GNU) et on donne des noms un peu plus convenables pour le tout. Il suffit alors de compiler, sans oublier de linker avec la librairie mathématique ("-lm") et la librairie spéciale Lex ("-ll"). On obtient :
$ calc 1+2*3 Résultat : 7.000000 2.5*(3.2-4.1^2) Résultat : -34.025000
Une amélioration possible...
Afin de permettre le rattrapage d'erreurs syntaxiques, et pour ne pas voir le programme s'arrêter sur un "parse error", on peut remplacer
Ligne:
FIN
| Expression FIN { printf("Résultat : %f
",$1); }
;
par
Ligne:
FIN
| Expression FIN { printf("Résultat : %f
",$1); }
| error END { yyerrok; }
;
mais ce n'est qu'une possibilité parmi d'autres (utilisation et définition de variables et de fonctions, plusieurs types de données, ...).