Introduction à Lex et Yacc
--------------------------
Guillaume Thouvenin (22/02/2001)
[Note: cet article provient de l'édition 2002-06 de LJNB, un journal qui
n'existe plus.]
0.0 Introduction
================
Un compilateur est un programme qui lit un langage (la source) et qui le
traduit par un programme équivalent dans un autre langage (la cible) en
rapportant les erreurs éventuelles. Nous allons nous intéresser dans cette
introduction à trois étapes qui sont l'analyse lexicale, l'analyse syntaxique
et l'analyse sémantique.
0.1 Analyse lexicale
--------------------
Le rôle de l'analyse lexicale est de fournir une suite de "tokens" (les
éléments terminaux du langage) à partir d'une suite de caractères fournis en
entrée. Par exemple, dans la déclaration suivante, x := 2*y + 3, l'analyseur
lexical va identifier les caractères par :
- Un identificateur x
- Un symbole d'assignation :=
- Un nombre 2
- Le signe *
- Un identificateur y
- Le signe +
- Un nombre 3
0.2 Analyse syntaxique
----------------------
L'analyse syntaxique est une analyse hiérarchique. L'objectif de cette analyse
est de regrouper les "tokens" fournis par l'analyse lexicale en phrases
grammaticales. En reprenant l'exemple précédent, nous pouvons construire l'arbre
syntaxique abstrait suivant :
assignation
/ | \
/ | \
/ := \
ident expression
| / | \
| / | \
x expression + expression
/ | \ |
/ | \ |
expression * expression nombre
| | |
| | |
nombre ident 3
| |
| |
2 y
Dans cet exemple, les règles grammaticales associées à "expression" sont (":="
peut se traduire par "se dérive en"):
expression := expression1 + expression2
expression := expression1 * expression2
expression := nombre
expression := ident
0.3 Analyse sémantique
---------------------
Enfin, l'analyse sémantique doit permettre de détecter les erreurs
éventuelles.
Il existe des outils permettant de générer automatiquement des analyseurs
lexicaux et syntaxiques, nous allons vous présenter dans ce texte Lex (un
analyseur lexical) et Yacc (un analyseur syntaxique).
1.0 Lex
=======
1.1 Théorie
-----------
Comme nous l'avons indiqué dans l'introduction, Lex va lire des données afin
de convertir les caractères en "tokens" compréhensibles par l'analyseur
syntaxique. Pour permettre à Lex d'identifier des patrons de caractères, nous
allons utiliser les expressions régulières. À chaque patron est associé une
action (en général, il s'agit de retourner le "token" correspondant au patron).
Par exemple, supposons qu'un identificateur soit de la forme
"lettre(lettre|chiffre)*" c'est à dire une lettre suivit d'une lettre ou d'un
chiffre zéro ou plusieurs fois (x, x1, xx, etc...). Il est alors possible de
représenter ce patron par un automate à état fini (FSA : finite state
automaton):
lettre autre
Début ----------> Etat0 ----------> Etat1 ----------> Fin
| ^
| |
| |
\---/
lettre ou chiffre
L'état "Fin" représente un état validant notre identificateur. De façon plus
algorithmique, nous pourrions écrire :
Début : aller à Etat0
Etat0 : lire c
si c = lettre aller à Etat1
aller à Etat0
Etat1 : lire c
si c = lettre aller à Etat1
si c = chiffre aller à Etat1
aller à Etat2
Fin : accepter l'identificateur
C'est la technique utilisée par Lex. Les expressions régulières sont
représentées sous forme d'un automate.
1.2 Reconnaissance des chaînes de caractères
--------------------------------------------
Voici un tableau des "méta-caractères" utilisés par Lex :
. n'importe quel caractère sauf le retour à la ligne
\n retour à la ligne
* zéro fois ou plus l'expression précédent ce signe
+ une fois ou plus l'expression précédent ce signe
? zéro ou une fois l'expression précédent ce signe
^ début de la ligne
$ fin de la ligne
a|b a ou b
(ab)+ une fois ou plus le mot ab
"a+b" la chaîne a+b
[] une classe de caractères
Quelques exemples :
abc* ab, abc, abcc, abccc, ...
[abc] a ou b ou c
[a-z] une lettre entre a et z
[a\-z] a, -, z
[A-Za-z0-9]+ un caractère alphanumérique ou plus
[^ab] n'importe quoi sauf a,b
Nous pouvons remarquer que dans une classe de caractères, les
"méta-caractères" perdent leur signification à l'exception de "^" et "-". Entre
deux caractères, "-" signifie un intervalle et, lorsque "^" est utilisé en début
d'une classe, il entraîne la négation de la classe. Si deux chaînes de
caractères sont reconnues, Lex prendra la plus longue et si les deux chaînes ont
la même longueur, Lex prendra celle se trouvant dans la règle la plus haute (la
première déclarée).
1.3 La syntaxe de Lex
---------------------
Lex peut être découpé en trois parties :
... les définitions ...
%%
... les règles ...
%%
... les sous-routines ...
Le programme le plus simple que nous pouvons écrire est :
%%
Ce programme est tout à fait valable. Il va copier sur la sortie ce qui arrive
en entrée un caractère après l'autre. Par défaut, l'entrée est "stdin" la sortie
est "stdout". Lex possède des variables prédéfinies comme par exemple "yyleng"
qui indique la longueur de la chaîne reconnue ou encore "yylval" qui est la
valeur associée au "token". Une autre variable importante est "char *yytext" qui
pointe sur le "patron" reconnu. Il existe aussi des fonctions prédéfinies comme
"int yylex(void)" qui permet d'invoquer l'analyseur lexicale et qui retourne un
"token".
Regardons maintenant un exemple plus intéressant qui permet de numéroter un
texte:
exemple1.l
- - - - -
%{
int yylineno;
%}
%%
^(.*)\n printf("%4d\t%s", ++yylineno, yytext);
%%
int main(int argc, char *argv[]) {
yyin = fopen(argv[1], "r");
yylex();
fclose(yyin);
}
Le code de la partie définition va être copié tel quel dans le fichier C
généré par Lex et ce code doit être délimité par %{ et %}. La partie définition
peut aussi contenir des substitutions permettant d'améliorer la lisibilité de
notre programme. Par exemple, il est possible d'avoir une partie définition tel
que :
exemple2.l
- - - - -
chiffre [0-9]
lettre [A-Za-z]
%{
int count;
%}
%%
{lettre}({lettre}|{chiffre})* count++;
%%
int main(void) {
yylex();
printf("nombre d'identificateurs = %d\n", count);
return 0;
}
Remarquons dans l'exemple1.l que l'entrée utilisée par Lex n'est plus celle
par défaut (stdin) mais, argv[1]. Il est bien sûr possible de faire la même
chose pour la sortie en utilisant la variable yyout. Dans la pratique, voici
la façon permettant d'obtenir un exécutable à partir de l'exemple1.l :
guill:~/parserTest/simple $ flex exemple1.l
guill:~/parserTest/simple $ ls -l
total 164
drwxr-xr-x 3 guill users 4096 Feb 22 15:09 .
drwxr-xr-x 4 guill users 4096 Feb 19 20:06 ..
-rwxr-xr-x 1 guill users 24226 Feb 21 16:28 calc
-rw-r--r-- 1 guill users 211 Feb 21 16:01 calc.l
-rw-r--r-- 1 guill users 330 Feb 21 16:28 calc.y
-rw-r--r-- 1 guill users 181 Feb 22 15:07 exemple1.l
drwxr-xr-x 2 guill users 4096 Feb 18 14:16 julesCesar
-rw-r--r-- 1 guill users 36044 Feb 22 15:09 lex.yy.c
-rwxr-xr-x 1 guill users 19974 Feb 18 14:04 simple
-rw-r--r-- 1 guill users 162 Feb 18 14:04 simple.l
-rwxr-xr-x 1 guill users 20479 Feb 15 18:36 simple2
-rw-r--r-- 1 guill users 179 Feb 15 18:36 simple2.l
-rw-r--r-- 1 guill users 2131 Feb 21 16:28 y.output
-rw-r--r-- 1 guill users 23243 Feb 21 16:28 y.tab.c
-rw-r--r-- 1 guill users 88 Feb 21 16:28 y.tab.h
guill:~/parserTest/simple $ gcc -o exemple1 lex.yy.c -lfl
guill:~/parserTest/simple $ exemple1 < exemple1.l
1 %{
2 int yylineno;
3 %}
4
5 %%
6
7 ^(.*)\n printf("%4d\t%s", ++yylineno, yytext);
8
9 %%
10
11 int main(int argc, char *argv[]) {
12 yyin = fopen(argv[1], "r");
13 yylex();
14 fclose(yyin);
15 }
guill:~/parserTest/simple $
Nous avons utilisé Flex à la place de Lex. Si vous utilisez Lex, il faut alors
utiliser la librairie Lex (-ll) au lieu de la librarie Flex (-lfl).
2.0 YACC
========
2.1 Théorie
-----------
Un langage de programmation peut être défini par sa syntaxe et, par sa
sémantique. Pour spécifier la syntaxe d'un langage, il est possible d'utiliser
ce que l'on appelle les grammaires libres de contexte (context-free) ou BNF
(forme de Backus-Norm). Une grammaire libre de contexte possède quatre
composantes qui sont :
- Un ensemble de "tokens" ou terminaux du langage
- Un ensemble de non-terminaux
- Un ensemble de règles de productions ou chacune des règles consistent
en un non-terminal à gauche de la production (left-side), une flèche
et une séquence de tokens et/ou de non-terminaux à droite de la
production (right-side)
- Un non-terminal de départ.
Les grammaires pour Yacc sont décrites en utilisant cette forme. La plupart
des langages modernes peuvent être décris sous cette forme.
Prenons par exemple la grammaire suivante :
(r1) E -> E + E
(r2) E -> E * E
(r3) E -> id
Nous venons de spécifier trois règles de production. Cette grammaire indique
qu'une expression peut être la somme de deux expressions, le produit de deux
expressions ou un identificateur. Nous pouvons utiliser cette grammaire pour
générer l'expression suivante :
E -> E * E (r2)
-> E * z (r3)
-> E + E * z (r1)
-> E + y * z (r3)
-> x + y * z (r3)
A chaque étape, nous avons remplacé le membre droit d'une production avec le
membre gauche de cette même production (les productions sont notées r1, r2 et
r3). Pour "parser" une expression, Yacc a besoin de faire l'opération inverse.
Plutôt que de partir d'un non-terminal et générer une expression à partir de
la grammaire, il faut partir d'une expression et la réduire à un non-terminal.
Cette technique s'appelle un "parsage bottom-up" ou "shift-reduce" et, elle
utilise des piles pour stocker les termes. Voici la même dérivation que
précédemment mais en bottom-up :
1 .x + y * z (shift)
2 x .+ y * z (reduce [r3])
3 E .+ y * z (shift)
4 E + .y * z (shift)
5 E + y .* z (reduce [r3])
6 E + E .* z (shift)
7 E + E * .z (shift)
8 E + E * z. (reduce [r3])
9 E + E * E. (reduce [r2])
10 E + E. (reduce [r1])
11 E. (accept)
Le "." symbolise le "lookhead" qui est le symbole courant. Le terme à gauche
du "." est sur la pile. Lorsque le sommet de la pile correspond à un terme se
trouvant à droite d'une production, on remplace le token correspondant avec la
partie gauche de la règle de production. A l'étape 1, on place x sur la pile.
L'étape 2 applique la règle r3 et, x est donc remplacé par la partie gauche de
la règle 3 (c'est à dire E). Nous continuons le processus jusqu'à ce qu'il n'y
ait plus qu'un seul non-terminal sur la pile.
Dans la grammaire que nous avons utilisé, nous pouvons remarquer des conflits.
Par exemple, à l'étape 6, nous avons choisi de décaler le lookhead après
l'opérateur '*' alors que nous aurions pu faire une réduction de "E + E" en
utilisant la règle r1. Nous avons donc un conflit "shift-reduce". Ceci arrive
car notre grammaire est ambiguë (il existe plusieurs dérivations possibles).
Nous aurions pu avoir aussi un conflit "reduce-reduce" comme par exemple dans la
grammaire suivante :
E -> T
E -> id
T -> id
Yacc résout ces problèmes en adoptant une action par défaut. Dans le cas d'un
conflit "shift-reduce", Yacc va choisir le "shift". Dans le cas d'un conflit
"reduce-reduce", Yacc va choisir la première règle dans la grammaire. En cas de
conflits, Yacc génère des "warnings" sur les règles problématiques. Il est aussi
possible de lui spécifier un comportement.
2.2 La syntaxe de Yacc
----------------------
Les entrées dans Yacc sont diviseés en trois parties.
... définitions ...
%%
... règles ...
%%
... sous-routines ...
La section définitions contient la déclaration des "tokens" et peut aussi
contenir du code C qui doit alors être placé entre "%{" et "%}". Les règles de
grammaire se retrouvent dans la partie "règles" et enfin, les fonctions
utilisées par l'usager vont se placer dans la partie réservée aux sous-routines.
Pour commencer, nous allons prendre comme exemple un simple calculateur qui
permet d'ajouter et de soustraire des nombres afin de mettre en évidence le lien
entre Lex et Yacc. Dans la partie définition de Yacc, nous pouvons placer :
% token INTEGER
Cette définition déclare INTEGER comme étant un "token" de notre langage.
Lorsque l'on exécute Yacc, il génère un parser dans le fichier y.tab.c et, en
utilisant l'option -d, il crée un fichier d'en-tête y.tab.h qui ressemble à :
#ifndef YYSTYPE
#define YYSTYPE int
#endif
#define INTEGER 258
extern YYSTYPE yylval;
Le fichier y.tab.h va être inclus dans la partie définition de notre fichier
lex et Lex va pouvoir utiliser la définition de INTEGER. Pour obtenir le
"token", Yacc fait un appel à la fonction yylex(). Cette fonction retourne un
entier qui est le token. Les valeurs associées aux "tokens" sont retournées par
l'intermédiaire de la variable yylval. Par exemple, dans notre fichier lex nous
pourrions avoir :
[0-9]+ {
yylval = atoi(yytext);
return INTEGER;
}
La valeur associée au "token" INTEGER est placée dans yyval et Lex retourne le
"token" INTEGER. Les valeurs de "tokens" 0-255 sont réservées pour les
caractères. En générale, Yacc commence la numérotation des tokens à 258. Voyons
maintenant un exemple plus complet de notre calculateur :
%{
#include "y.tab.h"
%}
%%
[0-9]+ {
yylval = atoi(yytext);
return INTEGER;
}
[-+\n] return *yytext;
[ \t] ; /* On ignore les espaces */
. yyerror("Caractère inconnu.");
%%
int yywrap(void) {
return 1;
}
Dans le cas de "+" et "-", c'est la valeur du caractère qui est retournée. La
fonction yywrap() est appelée lorsque tous les caractères en entrée sont lus.
Intéressons nous maintenant à la partie Yacc.
De façon interne, Yacc utilise deux piles en mémoire, la pile de "parsage" et
la pile de valeur. La pile de "parsage" contient les terminaux et non-terminaux
et représente l'état courant d'analyse. La pile de valeur est un tableau
d'éléments de type YYSTYPE et, elle permet d'associer une valeur à chaque
élément de la pile de "parsage". Par exemple, lorsque Lex retourne le token
"INTEGER", Yacc empile ce "token" sur la pile de "parsage". De façon synchrone,
la valeur associée à ce "token" est placée sur la pile de valeur. Il faut bien
comprendre que les deux piles sont synchronisées et donc, trouver la valeur
associée à un token est très facile. Par exemple, supposons que Lex soit en
train de lire la valeur 69, les piles auront donc à leurs sommets 69 pour la
pile de valeur et 258 (INTEGER) pour la pile de "parsage". Continuons notre
exemple du calculateur avec le fichier Yacc correspondant :
%token INTEGER
%%
programme :
programme expr '\n' { printf("Result : %d\n", $2);}
|
;
expr :
INTEGER { $$ = $1;}
| expr '+' expr { $$ = $1 + $3;}
| expr '-' expr { $$ = $1 - $3;}
;
%%
int yyerror (char *s) {
fprintf(stderr, "%s\n", s);
return 0;
}
int main(void) {
yyparse();
return 0;
}
Pour compiler cet exemple, nous avons utilisé Flex et Bison (les successeurs
de Lex et Yacc). Voyons le résultat :
guill:~/parserTest/simple $ bison -d -o y.tab.c calc.y
calc.y contains 4 shift/reduce conflicts.
guill:~/parserTest/simple $ flex calc.l
guill:~/parserTest/simple $ gcc -o calc lex.yy.c y.tab.c -lfl
guill:~/parserTest/simple $ ./calc
1+2
Result : 3
12*4
Caractère inconnu.
parse error
Tout d'abord, l'option -d permet la génération du fichier y.yab.h. Ensuite,
contrairement à Yacc, Bison produit par défaut un fichier C nommé calc.tab.c et
un fichier H nommé calc.tab.h (Yacc produit un fichier y.tab.c et un fichier
y.tab.h). Or, comme nous avions déclaré un fichier y.tab.h dans notre fichier
lex, nous avons choisi de définir le fichier de sortie comme étant y.tab.c afin
d'obtenir un fichier y.tab.h (À part ça, tout ce que nous avons dit pour Lex et
Yacc est valable pour Flex et Bison). Bison nous indique que notre grammaire
contient quatre conflits "shift/reduce" qui sont réglés comme nous l'avons
expliqué dans la partie 2.1. Pour produire notre exécutable "calc", nous
indiquons à gcc d'utiliser la librairie de Flex (-lfl). Dans notre exemple, nous
avons essayé d'évaluer l'expression 12*4. '*' est retourné comme étant inconnu
par Lex ce qui conduit à une erreur de parsage. Il est aussi possible de voir la
table de parsage générée par Yacc en ajoutant l'option -v lors de la compilation
(qui entraîne la création d'un fichier y.output). Voici un exemple de ce que
contient ce fichier :
State 7 contains 2 shift/reduce conflicts.
State 8 contains 2 shift/reduce conflicts.
Grammar
rule 1 programme -> programme expr '\n'
rule 2 programme -> /* empty */
rule 3 expr -> INTEGER
rule 4 expr -> expr '+' expr
rule 5 expr -> expr '-' expr
Terminals, with rules where they appear
$ (-1)
'\n' (10) 1
'+' (43) 4
'-' (45) 5
error (256)
INTEGER (257) 3
Nonterminals, with rules where they appear
programme (7)
on left: 1 2, on right: 1
expr (8)
on left: 3 4 5, on right: 1 4 5
...
Revenons sur notre fichier Yacc. La section "règles" correspond à une
grammaire BNF. La partie droite d'une production apparaît justifiée à gauche et
est suivie de ":". Ensuite, nous plaçons la partie droite de notre production.
Les actions apparaissent entre des accolades. Lorsque nous appliquons la règle :
expr : expr '+' expr { $$ = $1 + $3; }
nous remplaçons la partie droite de la production par la partie gauche de cette
même production. Dans notre cas, nous enlevons expr '+' expr de la pile puis
nous plaçons expr sur la pile. Nous avons donc réduit la pile en enlevant trois
éléments et en en replaçant un. Nous indiquons la position, dans la pile de
valeur, du premier élément de la partie droite de la production par $1, le
second par $2, etc... $$ représente le sommet de la pile après la réduction.
Pour savoir comment faire les réductions ou les décalages, Yacc construit une
table de parsage dite LALR (Lookahead-LR). Voici la table de parsage générée par
Yacc pour notre calculateur :
--------------------------------------------------------------------------
| | ACTIONS | GOTO |
| STATE |-----------------------------------------------|------------------|
| | \n | + | - | error | INTEGER | $ | $Défaut | programme | expr |
|--------------------------------------------------------------------------
| 0 | | | | | | | r2 | 1 | |
| 1 | | | | | s2 | 9 | | | 3 |
| 2 | | | | | | | r3 | | |
| 3 | s4 | s5 | s6 | | | | | | |
| 4 | | | | | | | r1 | | |
| 5 | | | | | s2 | | | | 7 |
| 6 | | | | | s2 | | | | 8 |
| 7 | | s5 | s6 | | | | r4 | | |
| 8 | | s5 | s6 | | | | | | |
| 9 | | | | | | 10 | | | |
| 10 | | | | | | | accept | | |
--------------------------------------------------------------------------
1. "si" indique un décalage (shift) et un passage de la pile à l'état i
2. "rj" indique une réduction (reduce) par la production numéro j
3. "accept" indique un succès
4. un "blanc" indique une erreur de parsage
Yacc ajoute aux terminaux une action par défaut qui est exécutée si aucuns
"tokens" ne correspond à la valeur attendue. Par exemple, si nous sommes dans
l'état 7, si nous rencontrons un "token" différent de '+' ou '-', nous
effectuerons alors une réduction en utilisant la règle 4 (cf. l'exemple du
fichier y.output). Prenons par exemple la chaîne "12+3+4\n$" (ce qui est
équivalent à saisir 12+3+4 'entrée' dans notre programme calc).
Lorsque Yacc commence l'analyse, nous sommes dans l'état 0, et avant même de
saisir un texte, il exécute l'action par défaut qui est une réduction en
utilisant la règle 1 (programme -> /*empty*/). Nous sommes donc dans l'état 0
avec le non-terminal "programme". Comme nous venons de faire une réduction, Yacc
va aller dans un nouvel état en regardant la partie GOTO de la table de parsage.
La table indique d'aller à l'état 1. Ceci peut-être considéré comme une
initialisation. À ce moment, Yacc est prêt à commencer l'analyse. Il va faire
appel à Lex pour récupérer un "token". Lex va donc retourner le "token" INTEGER
en mettant la variable yylval à 12. Yacc récupère donc le "token" 257 (qui
correspond à INTEGER). Il regarde dans sa table de parsage (l'état courant est
l'état 1). Nous voyons que l'action à effectuer est un déplacement vers la
droite (shift) et un passage dans l'état 2. Nous avons donc nos piles dans les
états suivants :
État : 0 - 1 - 2
Parse Stack : INTEGER |
Value Stack : 12 |
Nous venons de faire un "shift", nous allons donc déplacer le "lookhead" (qui
va devenir '+') et l'état va passer à 2. Dans l'état 2, nous voyons que peut
importe le "token", la seule action possible est une réduction en utilisant la
règle 3 (expr -> INTEGER). Les piles vont donc être modifiées de la façon
suivante :
État : 0 - 1
Parse Stack : expr |
Value Stack : 12 |
La valeur 12 reste dans la pile car nous avons dans notre grammaire indiqué
la règle {$$ = $1;} ce qui a pour effet d'enlever 12 de la pile pour le
remettre. Nous venons d'effectuer une réduction, il faut donc regarder dans la
table l'état dans lequel nous allons aller. L'état courant est 1 (2 a été enlevé
lors de la réduction), la pile de "parsage" contient expr au sommet, la partie
goto indique que nous allons aller à l'état 3. Au niveau de l'état 3, nous
voyons que le symbole ('+') implique un décalage et un passage à l'état 5. Le
token courant est donc INTEGER (3) et les piles sont donc maintenant :
État : 0 - 1 - 3 - 5
Parse Stack : expr | token + |
Value Stack : 12 | '+' |
Remarquons que dans l'état 5, un autre token que INTEGER provoque une erreur
de parsage. La lecture du token INTEGER à l'état 5 entraîne un déplacement du
lookhead et un passage à l'état 2. Comme précédemment, dans l'état, nous avons
une action par défaut nous imposant une réduction avec la règle 3. Après cette
réduction, nous allons avoir le non-terminal "expr" en haut de la pile et,
l'état courant positionné à 5 et donc, la partie GOTO nous indique d'aller dans
l'état 7 :
État : 0 - 1 - 3 - 5 - 7
Parse Stack : expr | token + | expr
Value Stack : 12 | '+' | 3
En continuant ainsi, nous allons pouvoir analyser toute la chaîne "12+3+4".
Vous pouvez voir ce processus en utilisant l'option de deboggage de Yacc.
Starting parse
Entering state 0
Reducing via rule 2 (line 11), -> programme
state stack now 0
Entering state 1
Reading a token: 12+3+4
Next token is 257 (INTEGER)
Shifting token 257 (INTEGER), Entering state 2
Reducing via rule 3 (line 14), INTEGER -> expr
state stack now 0 1
Entering state 3
Reading a token: Next token is 43 ('+')
Shifting token 43 ('+'), Entering state 5
Reading a token: Next token is 257 (INTEGER)
Shifting token 257 (INTEGER), Entering state 2
Reducing via rule 3 (line 14), INTEGER -> expr
state stack now 0 1 3 5
Entering state 7
Reading a token: Next token is 43 ('+')
Shifting token 43 ('+'), Entering state 5
Reading a token: Next token is 257 (INTEGER)
Shifting token 257 (INTEGER), Entering state 2
Reducing via rule 3 (line 14), INTEGER -> expr
state stack now 0 1 3 5 7 5
Entering state 7
Reading a token: Next token is 10 ('\n')
Reducing via rule 4 (line 16), expr '+' expr -> expr
state stack now 0 1 3 5
Entering state 7
Next token is 10 ('\n')
Reducing via rule 4 (line 16), expr '+' expr -> expr
state stack now 0 1
Entering state 3
Next token is 10 ('\n')
Shifting token 10 ('\n'), Entering state 4
Reducing via rule 1 (line 9), programme expr '\n' -> programme
Result : 19
state stack now 0
Entering state 1
2.3 Un exemple plus complet
---------------------------
Pour terminer, nous allons rapidement commenté un exemple plus complet dont
les sources sont disponibles à la fin de ce texte. Il s'agit d'un calculateur
acceptant certaines structures du type boucle et, il accepte aussi des variables
(les variables n'ayant qu'un seul caractère). Nous avons utilisé Flex et Bison
pour produire les fichiers C. Si vous utilisez Lex et Yacc, il faudra modifier
le nom du fichier d'en-tête en "y.tab.h".
Le principe est simple. Nous allons construire une liste au fur et à mesure du
parcours de notre grammaire. Cette liste sera évaluée lorsque nous aurons réussi
à réduire notre programme jusqu'à la racine. Nous voyons donc que nous allons
travailler avec trois types possible dans la pile de valeur. En effet, nous
pouvons avoir un entier, un caractère ou un noeud. Pour prévenir Yacc qu'il va y
avoir trois types possibles, nous allons déclarer ces différents type dans une
union dans la partie définition de Yacc :
%union {
int iValue; /* Notre type entier */
char sIndex; /* Notre type caractère */
nodeType *nPtr; /* Notre type noeud */
}
Ceci va avoir pour effet de déclarer YYSTYPE de la façon suivante :
typedef union {
int iValue;
char sIndex;
nodeType *nPtr;
} YYSTYPE;
Et, Yacc va ensuite déclarer une variable yyvalue comme étant de type YYSTYPE.
Nous pouvons donc maintenant empiler un entier, un caractère ou un noeud dans la
pile de valeur. Nous remarquons aussi dans notre code les déclarations :
%token <iValue> INTEGER
%token <sIndex> VARIABLE
Ceci nous permet de lier le token INTEGER au type entier et, le token VARIABLE
au type caractère. Ceci permet à Yacc de savoir le type à utiliser dans une
production comme :
expr : INTEGER {$$ = con($1);}
qui va produire le code C :
yylval.nPtr = con(yyvsp[0].iValue);
L'opérateur '-' unaire a une priorité supérieure aux opérateurs binaires grâce
à l'utilisation de %nonassoc UMINUS. Cette règle indique que l'opérateur UMINUS
n'est pas associatif. De plus, cette règle utilisée avec :
%prec (expr : '-' expr %prec UMINUS ...)
implique que UMINUS a une priorité supérieur aux autres. C'est la même technique
qui est utilisée pour lever l'ambiguïté sur le IF-ELSE. L'ambiguïté sur le
IF-ELSE arrive dans le cas suivant :
Soit la règle
stmt :
IF expr stmt
| IF expr stmt ELSE stmt
...
et nous devons analyser la déclaration suivante :
IF expr stmt IF expr stmt . ELSE stmt
Le "." est le symbole qui est en train d'être lu. Dans ce cas, doit-on réduire
ou bien avancer. Si nous réduisons nous obtenons IF expr stmt ELSE stmt. Si nous
avançons, nous obtenons IF expr stmt stmt. Dans les langages modernes, le ELSE
est lié au plus récent IF. Il faut donc avancer et non pas réduire. Par défaut
Yacc a le bon comportement mais, pour enlever le "warning", nous avons donné au
IF-ELSE une plus haute "précedence" que le simple IF.
Enfin, l'arbre syntaxique est construit "bottom-up", allouant des feuilles
lorsqu'un entier ou un caractère est réduit. Lorsqu'un opérateur est rencontré,
un noeud est alloué et des pointeurs sur les noeuds précédemment créés sont
placés comme opérateurs. Lorsque nous avons remonté l'arbre, la fonction ex()
est appelée et effectue un parcours en profondeur "depth-first" de l'arbre.
3.0 Conclusion
==============
Si vous souhaitez voir ce que l'on peut faire sur un vrai langage comme le C,
nous vous conseillons d'aller voir le code source de LCLint qui utilise Flex et
Bison et analyse du code C. Le code de LCLint est bien écrit et est donc
compréhensible.
Fichier test
============
x = 0;
while ( x < 3 ) {
printf x;
x = x + 1;
}
Fichier calc3.h
===============
typedef enum { typeCon, typeId, typeOpr } nodeEnum;
/* Constants */
typedef struct {
nodeEnum type; /* type of node */
int value; /* value of constant */
} conNodeType;
/* Identifiers */
typedef struct {
nodeEnum type; /* type of node */
int i; /* subscript to ident array */
} idNodeType;
/* Operators */
typedef struct {
nodeEnum type; /* type of node */
int oper; /* operator */
int nops; /* number of operands */
union nodeTypeTag *op[1]; /* operands (expandable) */
} oprNodeType;
typedef union nodeTypeTag {
nodeEnum type; /* type of node */
conNodeType con; /* constants */
idNodeType id; /* identifiers */
oprNodeType opr; /* operators */
} nodeType;
extern int sym[26];
Fichier calculator.l
====================
%{
#include <stdio.h>
#include "calc3.h"
#include "calculator.tab.h"
%}
%%
[a-z] {
yylval.sIndex = *yytext - 'a';
return VARIABLE;
}
[0-9]+ {
yylval.iValue = atoi(yytext);
return INTEGER;
}
[-()<>=+*/;{}] { return *yytext; }
">=" { return GE; }
"<=" { return LE;}
"==" { return EQ;}
"!=" { return NE;}
"while" { return WHILE;}
"if" { return IF;}
"else" { return ELSE;}
"printf" { return PRINTF;}
[ \t\n]+ ;
. yyerror("Invalid character\n");
%%
int yywrap(void) {
return 1;
}
Fichier calculator.y
====================
%{
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "calc3.h"
/* prototypes */
nodeType* opr(int oper, int nops, ...);
nodeType* id(int i);
nodeType* con(int value);
int ex(nodeType *p);
void freeNode(nodeType *p);
void yyerror(char *s);
int sym[26]; /* table des symboles */
%}
%union {
int iValue;
char sIndex;
nodeType *nPtr;
};
%token <iValue> INTEGER
%token <sIndex> VARIABLE
%token WHILE IF PRINTF
%nonassoc IFX
%nonassoc ELSE
%left GE LE EQ NE '>' '<'
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS
%type <nPtr> stmt expr stmt_list
%%
program :
function { fprintf(stderr, "regle 1 \n");
exit(0); }
;
function :
function stmt { fprintf(stderr, "regle 2 \n");
fprintf(stdout, " RES = %d\n", ex($2));
freeNode($2);}
| /* NULL */
;
stmt :
';' { fprintf(stderr, "regle 3 \n");
$$ = opr(';', 2, NULL, NULL);}
| expr ';' { fprintf(stderr, "regle 4 \n");
$$ = $1;}
| PRINTF expr ';' { fprintf(stderr, "regle 5 \n");
$$ = opr(PRINTF, 1, $2);}
| VARIABLE '=' expr ';' { fprintf(stderr, "regle 6 \n");
$$ = opr('=', 2, id($1), $3);}
| WHILE '(' expr ')' stmt { fprintf(stderr, "regle 7 \n");
$$ = opr(WHILE, 2, $3, $5);}
| IF '(' expr ')' stmt %prec IFX { fprintf(stderr, "regle 8 \n");
$$ = opr(IF, 2, $3, $5);}
| IF '(' expr ')' stmt ELSE stmt { fprintf(stderr, "regle 9 \n");
$$ = opr(IF, 2, $3, $5, $7);}
| '{' stmt_list '}' { fprintf(stderr, "regle 10 \n");
$$ = $2;}
;
stmt_list :
stmt { fprintf(stderr, "regle 11 \n");
$$ = $1;}
| stmt_list stmt { fprintf(stderr, "regle 12 \n");
$$ = opr(';', 2, $1, $2);}
;
expr :
INTEGER { fprintf(stderr, "regle 13 \n");
$$ = con($1);}
| VARIABLE { fprintf(stderr, "regle 14 \n");
$$ = id($1);}
| '-' expr %prec UMINUS { fprintf(stderr, "regle 15 \n");
$$ = opr(UMINUS, 1, $2);}
| expr '+' expr { fprintf(stderr, "regle 16 \n");
$$ = opr('+', 2, $1, $3);}
| expr '-' expr { fprintf(stderr, "regle 17 \n");
$$ = opr('-', 2, $1, $3);}
| expr '*' expr { fprintf(stderr, "regle 18 \n");
$$ = opr('*', 2, $1, $3);}
| expr '/' expr { fprintf(stderr, "regle 19 \n");
$$ = opr('/', 2, $1, $3);}
| expr '<' expr { fprintf(stderr, "regle 20 \n");
$$ = opr('<', 2, $1, $3);}
| expr '>' expr { fprintf(stderr, "regle 21 \n");
$$ = opr('>', 2, $1, $3);}
| expr GE expr { fprintf(stderr, "regle 22 \n");
$$ = opr(GE, 2, $1, $3);}
| expr LE expr { fprintf(stderr, "regle 23 \n");
$$ = opr(LE, 2, $1, $3);}
| expr NE expr { fprintf(stderr, "regle 24 \n");
$$ = opr(NE, 2, $1, $3);}
| expr EQ expr { fprintf(stderr, "regle 25 \n");
$$ = opr(EQ, 2, $1, $3);}
| '(' expr ')' { fprintf(stderr, "regle 26 \n");
$$ = $2;}
;
%%
nodeType *con(int value) {
nodeType *p;
/* allocate node */
if ((p = malloc(sizeof(conNodeType))) == NULL)
yyerror("out of memory");
/* copy information */
p->type = typeCon;
p->con.value = value;
return p;
}
nodeType *id(int i) {
nodeType *p;
/* allocate node */
if ((p = malloc(sizeof(idNodeType))) == NULL)
yyerror("out of memory");
/* copy information */
p->type = typeId;
p->id.i = i;
return p;
}
nodeType *opr(int oper, int nops, ...) {
va_list ap;
nodeType *p;
size_t size;
int i;
/* allocate node */
size = sizeof(oprNodeType) + (nops - 1) * sizeof(nodeType *);
if ((p = malloc(size)) == NULL)
yyerror("out of memory");
/* copy information */
p->type = typeOpr;
p->opr.oper = oper;
p->opr.nops = nops;
va_start(ap, nops);
for (i = 0; i < nops; i++)
p->opr.op[i] = va_arg(ap, nodeType*);
va_end(ap);
return p;
}
void freeNode(nodeType *p) {
int i;
if (!p) return;
if (p->type == typeOpr) {
for (i=0; i < p->opr.nops; i++)
freeNode(p->opr.op[i]);
}
free(p);
}
int ex(nodeType *p) {
if (!p) return 0;
switch(p->type) {
case typeCon : return p->con.value;
case typeId : return sym[p->id.i];
case typeOpr :
switch(p->opr.oper) {
case WHILE : while (ex(p->opr.op[0]))
ex(p->opr.op[1]);
return 0;
case IF : if (ex(p->opr.op[0]))
ex(p->opr.op[1]);
else if (p->opr.nops > 2)
ex(p->opr.op[2]);
return 0;
case PRINTF : printf("%d\n", ex(p->opr.op[0]));
return 0;
case ';' : ex(p->opr.op[0]);
return ex(p->opr.op[1]);
case '=' : return sym[p->opr.op[0]->id.i] =
ex(p->opr.op[1]);
case UMINUS : return -ex(p->opr.op[0]);
case '+' : return ex(p->opr.op[0]) +
ex(p->opr.op[1]);
case '-' : return ex(p->opr.op[0]) -
ex(p->opr.op[1]);
case '*' : return ex(p->opr.op[0]) *
ex(p->opr.op[1]);
case '/' : return ex(p->opr.op[0]) /
ex(p->opr.op[1]);
case '<' : return ex(p->opr.op[0]) <
ex(p->opr.op[1]);
case '>' : return ex(p->opr.op[0]) >
ex(p->opr.op[1]);
case GE : return ex(p->opr.op[0]) >=
ex(p->opr.op[1]);
case LE : return ex(p->opr.op[0]) <=
ex(p->opr.op[1]);
case NE : return ex(p->opr.op[0]) !=
ex(p->opr.op[1]);
case EQ : return ex(p->opr.op[0]) ==
ex(p->opr.op[1]);
}
}
}
void yyerror(char *s) {
fprintf(stderr, "%s\n", s);
}
int main (void) {
yyparse();
return 0;
}