Guide pratique et introduction à Lex et Yacc

Adaptation française du guide pratique Lex and YACC primer/HOWTO

Bert Hubert

Silvio Morandi

Adaptation française 

Jean-Philippe Guérard

Préparation de la publication de la v.f. 

Version : 0.8.fr.1.0

2 mai 2008

Historique des versions
Version 0.8.fr.1.02008-05-02SM, JPG
Première traduction française.
Version 0.82004-09-20BH
Version originale.

Résumé

Ce document tente de vous aider à commencer à utiliser Lex et YACC.


1. Introduction

Bienvenue, cher lecteur.

Quelle que soit la durée durant laquelle vous avez programmé sous un environnement Unix, vous avez rencontré les programmes mystiques Lex et YACC, ou tels qu'ils sont connus des utilisateurs de GNU/Linux à travers le monde, Flex et Bison; où Flex est une implémentation de Lex par Vern Paxson et Bison la version GNU de YACC. Nous allons appeler ces programmes Lex et YACC dans ce document - les nouvelles versions sont compatibles "vers le haut", vous pouvez donc utiliser Flex et Bison pour essayer nos exemples.

Ces programmes sont très utiles, mais comme pour votre compilateur C, leur page de manuel n'explique pas le langage qu'ils comprennent, ni comment les utiliser. YACC utilisé en combinaison avec Lex est vraiment surprenant, cependant, la page de manuel ne décrit pas comment intégrer du code généré par Lex dans votre programme en Bison.

1.1. Ce que ce document n'est PAS

Il existe de nombreux livres qui traitent de Lex et YACC. Lisez ces ouvrages de toute manière si vous souhaitez en savoir plus. Ils apportent beaucoup plus d'information que ce nous sommes en mesure de voir ici. Vous pouvez consulter la section « lectures pour approfondir » à la fin. Ce document a pour but de vous aider à vous en sortir lors de la création de vos premiers programmes avec Lex & YACC.

La documentation fournie avec Lex & YACC est elle aussi excellente, mais peu pédagogique. Elle est cependant complémentaires avec ce guide pratique, et est aussi référencée à la fin.

Je ne suis absolument pas un expert de Lex & Yacc. lorsque j'ai commencé à écrire ce document, j'avais exactement deux jours de pratique. Tout ce que j'ai cherché à faire, c'est rendre ces deux jours les plus simple possibles pour vous.

N'attendez pas de ce guide pratique qu'il vous montre comment coder proprement en Lex et YACC. Les exemples ont été laissé volontairement très simples et il y a sûrement de meilleures manières de les écrire. Si vous savez comment, s'il vous plaît, contactez moi.

1.2. Téléchargement

Notez que vous pouvez télécharger tous les exemples montrés sous forme de code source. Visitez la Homepage pour plus de détails.

1.3. Licence

Copyright (c) 2001 by bert hubert. This material may be distributed only subject to the terms and conditions set forth in the Open Publication License, vX.Y or later (the latest version is presently available at http://www.opencontent.org/openpub/).

Traduction à titre informative et sans valeur juridique :

Copyright (c) 2001, bert hubert. Ce programme ne peut être distribué que selon les conditions générales établies dans l'« Open Publication License », vX.Y ou ultérieure (la dernière version est disponible à http://www.opencontent.org/openpub/).

2. Ce que Lex & YACC peuvent faire pour vous

Utilisés proprement, ces langages vous permettent d'analyser facilement des langages complexes. C'est un sacré coup de pouce lorsque vous souhaitez lire un fichier de configuration, ou que vous souhaitez écrire un compilateur pour un langage que vous (ou n'importe qui d'autre) avez inventé.

Avec un peu d'aide, ce que j'espère que ce document vous apportera, vous découvrirez finalement que vous n'écrirez plus jamais d'analyseur syntaxique à la main: Lex & YACC sont les outils pour le faire.

2.1. Ce que fait chaque programme

Même si ces programmes fonctionnent de manière optimale ensemble, ils servent chacun à un but différent. Les prochains chapitres expliqueront exactement l'action de chacun d'entre eux.

3. Lex

Ce programme génère ce que l'ont appelle un analyseur lexical. Il s'agit d'une fonction qui prend comme argument un flux de caractères, et dès qu'il aperçoit un groupe qui correspond à un mot clef, effectue une certaine action. Un exemple très simple :

%{
#include <stdio.h>
%}

%%
stop	printf("Stop command received\n");
start	printf("Start command received\n");
%%

La première partie, entre les paires %{ et %}, est inclue directement dans la sortie. Nous avons besoin de cela, car nous utiliserons printf, qui est définit dans stdio.h, plus tard.

Les parties sont séparées par %%, donc la première ligne de la seconde section commence par le mot-clef « stop ». A chaque fois que le mot-clef « stop » est rencontré dans l'entrée, le reste de la ligne ( ici un appel à printf() ) est exécuté.

En plus de « stop » nous avons aussi définit « start », qui par ailleurs effectue sensiblement la même chose.

Nous terminons la seconde partie avec %% encore.

Pour compiler l'exemple 1, faire ceci:

lex example1.l
cc lex.yy.c -o example1 -ll
[Note]Note

si vous utilisez Flex, au lieu de Lex, vous pouvez avoir à changer -|| en -lfl ans le script de compilation. RedHat 6.x et SuSE en ont besoin aussi, même en utilisant Flex au lieu de Lex !

Ceci générera un fichier « exemple1 ». Si vous le lancez, il attendra que de vous tapiez une entrée. Même si vous tapez une entrée qui n'est pas « matchée » par un mot-clef (ici stop et start) it's output again. Si vous entrez 'stop', il affichera la sortie suivante « stop command received »;

Terminate with a EOF (^D).

Vous pouvez vous demander comment fonctionnent ces programmes, car nous n'avons pas définit de fonction main(). Cette fonction est définit pour vous dans libl (liblex) que nous avons compilé avec le programme grâce à la commande -ll.

3.1. Analyser les expressions régulières

Cet exemple n'était pas très utile en soit, et notre suivant ne sera pas mieux. Il va cependant nous montrer comment utiliser les expressions régulières en Lex, qui seront très utiles plus tard.

Example 2:

%{
#include <stdio.h>
%}

%%
[0123456789]+		printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]*	printf("WORD\n");
%%

Ce fichier Lex explique deux types de mots clés (symboles): WORD et NUMBER. Les expressions régulières peuvent être un peu intimidantes, mais avec un peu de travail, elles sont très simples à comprendre. Examinons le mot clé NUMBER:

[0123456789]+

Cela signifie: une séquence de un ou plus de caractères du groupe {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. On aurait aussi pu faire plus court :

[0-9]+

Maintenant, le mot clé WORD est un peu plus complexe:

[a-zA-Z][a-zA-Z0-9]*

a première partie ne repère qu'un et un seul caractère entre 'a' et 'z', ou entre 'A' et 'Z'.En d'autres termes, une lettre. Cette lettre initiale doit ensuite être suivie par zéro ou plus de caractères qui sont soit une lettre, soit un chiffre. Pourquoi avoir utilisé un astérisque ici ? Le '+' signifie 1 ou plus de repérages, mais un mot peut très bien n'être qu'un seul caractère, que nous avons alors déjà matché. La seconde partie peut donc n'avoir rien à matcher, nous écrivons donc un '*'.

De cette manière , nous avons singé le comportement de nombreux langages de programmation qui requièrent qu'un nom de variable « doive » commencer par une lettre, mais puisse contenir des chiffres ensuite. En d'autres mots 'temperature1' est un nom valide, mais '1temperature ' ne l'est pas.

Essayez de compiler Example2, tout comme Exemple1, et nourrissez le d'un peu de texte. Voici une session d'échantillons:

$ ./example2
foo
WORD

bar
WORD

123
NUMBER

bar123
WORD

123bar
NUMBER
WORD

Vous pourriez aussi vous demander pourquoi il y a un retour à la ligne dans la sortie. La raison est simple : il était dans l'entrée, n'a été matché nul part, il apparaît donc dans la sortie.

La page de man de Flex documente les expressions régulières en détail. Beaucoup de gens trouvent que cellle des expressions régulières de perl est aussi très utile, même si Flex n'implémente pas tout ce que perl fait.

Vérifiez que vous n'avez pas crée de match de taille nulle comme '[0-9]*', votre lexer pourrait être perdu et pourrait commencer à matcher des chaînes vides en boucle

3.2. Un exemple plus compliqué pour une syntaxe proche du C

Imaginons que nous voulions analyser un fichier qui ressemble à ceci:

logging {
	category lame-servers { null; };
	category cname { null; };
};

zone "." {
        type hint;
        file "/etc/bind/db.root";
};

On voit clairement un certain nombre de catégories (symboles) dans ce fichier:

  • WORD, (mot) comme 'zone' et 'type'

  • FILENAME, (nom de fichier) comme '/etc/bind/db.root'

  • QUOTE, (guillemets)comme celles entourant le nom du fichier

  • OOBRACE, (crochet ouvrant) {

  • EBRACE, (crochet fermant) }

  • SEMICOLON, (point virgule) ;

Le fichier correspondant en Lex est Exemple 3:

%{
#include <stdio.h>
%}

%%
[a-zA-Z][a-zA-Z0-9]*    printf("WORD ");
[a-zA-Z0-9\/.-]+        printf("FILENAME ");
\"                      printf("QUOTE ");
\{                      printf("OBRACE ");
\}                      printf("EBRACE ");
;                       printf("SEMICOLON ");
\n                      printf("\n");
[ \t]+                  /* ignore whitespace */;
%%

Quand nous donnons notre ficher à notre lexer généré par ce fichier Lex (en utilisant example3.compile), nous obtenons:

WORD OBRACE 
WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON 
WORD WORD OBRACE WORD SEMICOLON EBRACE SEMICOLON 
EBRACE SEMICOLON 

WORD QUOTE FILENAME QUOTE OBRACE 
WORD WORD SEMICOLON 
WORD QUOTE FILENAME QUOTE SEMICOLON 
EBRACE SEMICOLON 

Lorsque nous comparons ceci avec le fichier cité plus haut, il est clair que nous l'avons 'symbolisée'. Chaque partie du fichier de configuration à été analysée, et convertie en symbole.

Et c'est exactement ce donc nous avons besoin pour utiliser YACC Correctement.

3.3. Ce que nous avons vu

Nous avons vu que Lex est capable de lire une entrée arbitraire, et d'analyser ce qu'est chaque partie. C'est ce qu'on appelle l'analyse lexicale.

4. YACC

YACC peut analyser syntaxiquement un flux composé de symboles avec certaines valeurs. Cela décrit parfaitement la relation entre YACC et Lex. Yacc n'a aucune idée de ce que sont les 'flux en entrée ', il a besoin de symboles au préalablement traités. Alors que vous pourriez écrire vous même votre propre analyseur lexical, nous allons laisser Lex s'en charger.

Une note sur les grammaires et les analyseurs syntaxiques. Lorsque YACC à vu le jour, cet outil était utilisé pour analyser les fichier d'entrée des compilateurs. Les programmes écrits pour un langage de programmation ne sont pas ambigus (cad qu'ils n'ont qu'un seul sens). En tant que tel, YACC ne peut pas surmonter une ambiguïté ou un conflit décalage/réduction. Vous pourrez en apprendre plus sur YACC et les problèmes d'ambiguïté ou les conflits décalage/réduction dans le chapitre 'Conflits '.

4.1. 4.Un contrôleur simple de thermostat

Imaginons que nous ayons un thermostat que nous voulons contrôler avec un langage simple. Un dialogue avec le thermostat pourrait ressembler à ceci :

heat on
	Heater on!
heat off
	Heater off!
target temperature 22
	New temperature set!

Les symboles que nous avons besoin de reconnaître sont : heat, on/off (STATE), target, température, NUMBER.

L'analyseur lexical Lex (Exemple 4) est :

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  return NUMBER;
heat                    return TOKHEAT;
on|off                  return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

Nous pouvons remarquer deux changements importants. Premièrement, nous 'incluons' le fichier 'y.tab.h', et ensuite nous n'affichons plus rien, nous retournons les noms des ymboles. Ce changement est causé par le fait que nous fournissons désormais le tout à YACC, ce qui n'a plus aucun rapport avec ce que nous obtenons à l'écran. Y.tab.h has definitions for these tokens.

Mais d'où viens y.tab.h ? Il est généré par YACC à partir du fichier grammaire que nous sommes allons créer. Comme notre langage est très basique, voilà notre grammaire:

commands: /* empty */
        | commands command
        ;

command:
        heat_switch
        |
        target_set
        ;

heat_switch:
        TOKHEAT STATE
        {
         	printf("\tHeat turned on or off\n");
        }
        ;

target_set:
        TOKTARGET TOKTEMPERATURE NUMBER
        {
         	printf("\tTemperature set\n");
        }
        ;

La première partie est ce que j'appelle la 'racine'. Elle nous explique que nous avons des commandes, et que ces commandes consistent en individual 'command' parts. Comme vous pouvez le voir, cette règle es très récursive car elle contient encore le mot « command ». Ce qui signifie que le programme est désormais capable de réduire une série de commandes une par une. Lisez le chapitre 'Comment fonctionnent Lex et YACC en détail ' pour des détails importants sur la récursivité.

la seconde règle définit ce qu'est une commande. Nous ne supportons que deux types de commande, la commande 'heat_switch' et la commande 'target_set'. C'est ce que le symbole |- signifie: une commande peut être ou un 'heat-switch' ou un 'target-set'.

Un heat-switch consiste en un symbole HEAT qui est simplement le mot 'heat' suivit d'un état (que nous définirons dans le Fichier Lex comme 'on' ou 'off').

Plus compliqué: le 'target_set' qui consiste en un symbole TARGET (le mot target), le symbole TEMPERATURE (le mot temperature) et un nombre.

4.1.1. Un fichier YACC complet

La section précédente n'a montrée que la partie grammaticale du fichier YACC, mais il y a plus. Voici l'en tête que nous avons omis:

%{
#include <stdio.h>
#include <string.h>
 
void yyerror(const char *str)
{
 	fprintf(stderr,"error: %s\n",str);
}
 
int yywrap()
{
 	return 1;
} 
  
main()
{
  	yyparse();
} 

%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

La fonction yyerror() est appelée par YACC si il trouve une erreur. Nous renvoyons simplement le message reçu, mais il y a des choses plus intelligente à faire avec. Lisez la section « lectures pour approfondir » pour en savoir plus.

La fonction yywarp() peut être utilisée pour continuer la lecture depuis un autre fichier. C'est appelée à EOF et vous pouvez ensuite ouvrir un autre fichier et renvoyer 0; ou renvoyer 1 qui indique qu'il s'agit de la fin. Pour en savoir plus, lisez le chapitre : 'Comment fonctionnent Lex et YACC en détail '.

Ensuite, il y a la fonction main(), qui ne fait rien de particulier, mais lance le processus

La dernière ligne définit simplement les symboles qui seront utilisés. Ce sont les sorties qui utilisent y.tab.h si YACC est appelé avec l'option -d <-- ici je ne suis pas sur d'avoir compris le sens de la phrase en anglais.

4.1.2. Compiler et utiliser le contrôleur de thermostat

lex example4.l
yacc -d example4.y
cc lex.yy.c y.tab.c -o example4 

Certaines choses ont changées. Nous appelons aussi YACC pour compiler notre grammaire, ce qui crée y.tab.c et y.tab.h. Nous appelons appelons ensuite Lex comme d'habitude. Lorsque nous compilons, nous retirons le drapeau -ll: nous avons désormais notre propre fonction main() et nous n'avons pas besoin de celle fournis par libl.

[Note]Note

Si vous obtenez une erreur indiquant que votre compilateur n'est pas capable de trouver 'yylval ', ajoutez ceci à l'éxemple4.1, juste sous #include <y.tab.h>:

extern YYSTYPE yylval;

Ceci est expliqué dans le chapitre 'comment Lex et YACC fonctionnent en détail.

Une session d'exemple :

$ ./example4 
heat on
	Heat turned on or off
heat off
	Heat turned on or off
target temperature 10
	Temperature set
target humidity 20
error: parse error
$

Ce n'est pas vraiment ce que l'ont avait prévu d'obtenir, mais pour garder une courbe d'apprentissage praticable nous ne pouvons pas montrer toutes les possibilités en une fois.

4.2. Étendre le thermostat afin de supporter les paramètres

Comme nous l'avons vu, nous analysons désormais syntaxiquement les commandes du thermostat correctement, et marquons mêmes les erreurs correctement. Mais comme vous pouvez l'avoir deviné d'après le titre le programme n'a aucune idée de ce qu'il doit faire, it does not get passed any of the values you enter.

Commençons par ajouter la possibilité de lire la nouvelle température cible. Pour faire cela, nous avons besoin de lire le NUMBER matché dans l'analyseur lexical pour le convertir en valeur entière, qui pourra ensuite être lue avec le YACC.

A chaques fois que le Lex matche une cible, il place le texte matché dans la suite de caractères 'yytext'. YACC, lui, espère trouver une valeur dans la variable 'yylval'. Dans l'exemple 5, nous voyons la solution triviale:

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval=atoi(yytext); return NUMBER;
heat                    return TOKHEAT;
on|off                  yylval=!strcmp(yytext,"on"); return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

Comme vous pouvez le constater, nous appelons atoi() sur yytext, et plaçons le résultat dans yyval, où YACC peut le lire. Nous faisons à peu près la même chose pour le match STATE, nous le comparons à 'on', et initialisons yylval à 1 si c'est égal. Notez qu'avoir deux match separés pour 'on' et 'off' dans lex produirai un code plus rapide, mais j'ai voulu montrer une action plus complexe pour changer.

Maintenant, nous devont apprendre YACC à le supporter. Ce qui est appellé yylval avec Lex est appelé différemment avec YACC. Examinons la règle réglant la nouvelle temperature cible:

target_set: 
	TOKTARGET TOKTEMPERATURE NUMBER
	{
         	printf("\tTemperature set to %d\n",$3);
	}
        ;

Pour accéder à la valeur de la troisième partie de la règle (cad, NUMBER), nous avons besoin d'utiliser $3. Quelque soit le moment du retour de yylex(), les contenus de yylval sont attaché au terminal, qui peuvent être atteint par le $-constructeur. <- je ne suis pas sur du sens

Pour aller plus loin, observons la nouvelle règle du 'heat switch':

heat_switch:
        TOKHEAT STATE
        {
         	if($2)
         	        printf("\tHeat turned on\n");
	 	else
                        printf("\tHeat turned off\n");
        }
        ;

Si vous lancez maintenant l'exemple5, il prend en compte correctement ce que vous avez entré.

4.3. Analyser un fichier de configuration

Rappelons une partie du fichier de configuration que nous avons vu plus haut:

zone "." {
        type hint;
        file "/etc/bind/db.root";
};

Souvenez vous que nous avons déjà écrit un Lexer pour ce fichier. Tout ce dont nous avons besoin maintenant c'est d'écrire la grammaire de YACC et modifier l'analyseur lexical (aussi appelé Lexer) pour qu'il renvoi les données dans un format compréhensible pour YACC.

Dans l'analyseur lexicalde l'exemple6, nous avons :

%{
#include <stdio.h>
#include "y.tab.h"
%}

%%

zone			return ZONETOK;
file			return FILETOK;
[a-zA-Z][a-zA-Z0-9]*    yylval=strdup(yytext); return WORD;
[a-zA-Z0-9\/.-]+        yylval=strdup(yytext); return FILENAME;
\"                      return QUOTE;
\{                      return OBRACE;
\}                      return EBRACE;
;                       return SEMICOLON;
\n                      /* ignore EOL */;
[ \t]+                  /* ignore whitespace */;
%%

Si vous observez attentivement, vous pouvez voir que yylval est différent ! Nous n'attendons plus de lui d'être un entier, mais nous acceptons le fait que ce soit un char *. Dans un but de simplicité, nous utilisons strdup et gaspillons beaucoup de ressource mémoires. Veuillez noter que cela peut ne pas être un problème dans beaucoup de cas, lorsque par exemple vous n'avez besoin d'analyser qu'un fichier, puis de quitter.

Nous souhaitons stocker des chaînes de caractère, car nous ne travaillons presque qu'avec des noms : nom de fichiers et noms de zone?. Plus tard, dans un autre chapitre, nous expliquerons comment traiter différents types de données.

Pour indiquer à YACC le nouveau type de yylval, nous ajoutons cette ligne à l'en-tête de notre grammaire YACC:

#define YYSTYPE char *

La grammaire elle-même est encore une fois plus compliquée. Nous la découpons en parts pour la rendre plus digeste:

commands:
	|	 
	commands command SEMICOLON
	;


command:
	zone_set 
	;

zone_set:
	ZONETOK quotedname zonecontent
	{
		printf("Complete zone for '%s' found\n",$2);
	}
	;

Ceci est l'introduction, comprenant la racine récursive précédemment citée. Veuillez noter que nous précisons que chaque commande se termine par un ;. (et les commandes sont donc séparées par des ;). Nous définissons un type de commande : 'zone_set'. Elle consiste en un symbole ZONE (le mot 'zone'), suivit par un 'quotedname' et le 'zone content'. Ce 'zonecontent ' débute simplement :

zonecontent:
	OBRACE zonestatements EBRACE 

Il a besoin de commencer avec un OBRACE, un crochet ouvert {. Puis suit les 'zonestatement's, suivits par un EBRACE, crochet fermé }.

quotedname:
        QUOTE FILENAME QUOTE
        {
         	$$=$2;
        }

Cette section définit ce qu'est un quotedname : un FILENAME (nom de fichier) entre QUOTEs (guillemets). Puis il indique quelque chose de spécial: la valeur d'un symbole 'quotedname' est la valeur du FILENAME. Cela signifie que la valeur du quoted name est le nom du fichier sans les quotes

C'est ce que fait la commande magique '$$=$2;' . Elle dit : ma valeur est la valeur de ma seconde partie. Alors que le quoted name est désormais referencé par d'autres règles, et que vous accédez à sa valeur grâce au $-constructeur, vous voyez la valeur que nous avons fixé ici avec $$=$2.

[Note]Note

Cette grammaire bute sur les noms de fichiers ne comportant pas de '.' ou de '/'

zonestatements:
	|
	zonestatements zonestatement SEMICOLON
	;

zonestatement:
	statements
	|
	FILETOK quotedname 
	{
		printf("A zonefile name '%s' was encountered\n", $2);
	}
	;

Il s'agit d'une instruction générale qui détecte tous les types d'instructions à l'intérieur des blocs 'zone'. Nous apercevons ici encore de la récursivité.

block: 
	OBRACE zonestatements EBRACE SEMICOLON
	;

statements:
	| statements statement
	;

statement: WORD | block | quotedname

Ceci définit un bloc et les instructions qui peuvent être trouvée à l'intérieur.

Lorsque l'on exécute le tout, la sortie ressemble à cela :

$ ./example6
zone "." {
        type hint;
        file "/etc/bind/db.root";
        type hint;
};
A zonefile name '/etc/bind/db.root' was encountered
Complete zone for '.' found

5. Faire un Parseur en C++

Bien que Lex & YACC soient antérieurs à C++, il est possible de générer un parseur C++. Flex comprends une option pour générer un Lexer C++, mais nous ne l'utiliserons pas, car YAXX ne sait pas comment l'utiliser directement.

Ma méthode préférée pour créer un parseur C++ est de faire générer à Lex un fichier C clair, et de laisser YACC générer le code C++. Lorsque liez ensuite votre application, vous pouvez avoir quelques problèmes car le code C++ fournit par défaut ne sera pas capable de trouver les fonctions C, sauf si vous avez indiqué que ces fonction sont du C externe.

Pour faire cela, faites un en-tête C dans YACC, comme cela:

extern "C"
{
 	int yyparse(void);
 	int yylex(void);  
 	int yywrap()
 	{
 	 	return 1;
        }

}

Si vous voulez déclarer ou changer yydebug, vous devez maintenant le faire comme ceci:

extern int yydebug;

main()
{
	yydebug=1;
	yyparse();
}

Cela est du à la définition d'une règle en C++, qui ne permet pas plusieurs définitions de yydebug.

Vous pouvez aussi avoir besoin de répéter le #define de YYSTYPE dans votre ficher Lex à cause du vérificateur de type strict de C++.

Pour compiler, faites quelque chose comme ceci :

lex bindconfig2.l
yacc --verbose --debug -d bindconfig2.y -o bindconfig2.cc
cc -c lex.yy.c -o lex.yy.o
c++ lex.yy.o bindconfig2.cc -o bindconfig2 

A cause de l'option -o, y.tab.h est désormais appelé bindconfig2.cc.h, donc prenez le en compte.

Pour résumer: ne vous embêtez pas à compiler votre lexer en C++, laissez le en C. Faites votre parseur en C++ et expliquez à votre compilateur que certaines fonctions sont des fonctions C avec des instructions externes.

6. Comment fonctionnent Lex et YACC en détail

Dans le fichier YACC, vous écrivez votre propre fonction main(), qui appelle yyparse() à un certain moment. La fonction yyparse()est créée pour vous par YACC, et finit dans y.tab.c.

yyparse() lit un flux de symboles/paires de valeurs depuis yylex() , qui doit être alimenté. Vous pouvez coder cette fonction vous même, ou laisser Lex le faire pour vous. Dans nos exemples, nous avons choisit de laisser ce travail à Lex.

Ce yylex() écrit par Lex lit les caractères depuis un FILE* file pointer appellé yyin. Si vous ne définissez pas yyin, il est définit par défaut sur l'entrée standard. It outputs to yyout, which if unset defaults to stdout. Vous pouvez aussi modifier yin dans la fonction yywrap() qui est appelée à la fin d'un fichier. Elle vous permet d'ouvrir un autre fichier et de continuer le parsing.

Si c'est le cas, faites lui retourner 0. Si vous voulez finir le parsing par ce fichier, faites lui retourner 1.

Chaque appel à yylex() retourne une valeur entière qui représente un type de jeton. Cela indique à YACC quel type de jeton est lu. Le jeton peut éventuellement avoir une valeur, qui devra être placée dans la variable yyval.

Par défaut yylval est du type int, mais vous pouvez le surcharger depuis le fichier YACC en redéfinissant #define YYSTYPE.

Le lexer doit être capable d'accéder à yylval. Pour faire cela, il doit être déclaré dans le champ du lexer comme une variable externe. Le YACC original omet de le faire, donc vous devrez ajoutez la ligne suivante à votre lexer: extern YYSTYPE yyval; , juste après le #include <y.tab.h>.

extern YYSTYPE yylval;

Bison, que la plupart des gens utilise, le fait pour vous automatiquement.

6.1. Valeurs des symboles

Comme dit précédemment, yylex() a besoin de renvoyer le type de jeton rencontré, et de placer sa valeur dan yylval. Lorsque ces jetons sont définits avec la commande %token, il leur est assigné un identifiant numérique commençant à 256.

A cause de cela, il est possible d'avoir tous els caractères ascii comme jeton. Imaginons que vous écriviez une calculatrice, jusqu'à maintenant, nous aurions écrit le lexer comme ceci:

[0-9]+          yylval=atoi(yytext); return NUMBER;
[ \n]+          /* eat whitespace */;
-               return MINUS;
\*              return MULT; 
\+              return PLUS;
...

Notre grammaire YACC aurait donc contenu suivant:

	exp: 	NUMBER 
		|
		exp PLUS exp
		|
		exp MINUS exp
		|
		exp MULT exp

Tout ceci est compliqué pour pas grand chose. En utilisant les caractères comme abréviations d'identifiants numériques de jetons, nous pouvons réécrire notre lexer comme ceci :

[0-9]+          yylval=atoi(yytext); return NUMBER;
[ \n]+          /* eat whitespace */;
.               return (int) yytext[0];

This last dot matches all single otherwise unmatched characters. <- Cette version ne matche pas les caractères seuls ou non matchés. Je n'arrive pas à reformuler mais en gros y'a pas de match par default ?

Notre grammaire YACC sera donc:

	exp: 	NUMBER 
		|
		exp '+' exp
		|
		exp '-' exp
		|
		exp '*' exp

Cette version est beaucoup plus courte et beaucoup plus évidente. Vous n'avez pas besoin de déclarer ces symboles ascii avec %token dans l'en-tête, ils sont prêts à l'emploi.

Un autre avantage avec cette construction est que Lex Lex va désormais matcher tout ce que nous lui envoyons – en évitant le comportement par défaut qui est de répéter les entrée non matchées vers la sortie standard. Si un utilisateur de la calculatrice utilise ^, par exemple, il va désormais générer une erreur de parsing, au lieu d'être renvoyé vers la sortie standard.

6.2. Récursivité: 'Droit est maladroit '

La récursivité est un aspect vital de YACC. Sans elle, vous ne pouvez pas spécifier que ce fichier consiste en une séquence de commandes ou d'instructions indépendantes.YACC ne s'intéresse qu'a la première règle, ou celle désignée comme règle de départ, par le symbole '%start'.

La récursivité dans YACC existe en deux tendances : gauche ou droite. La récursivité à gauche qui est celle que vous devriez utiliser la plupart du temps, ressemble à ça:

commands: /* empty */
	|
	commands command

Cela signifie: une commande est soit vide, soit plusieurs commandes, suivies par une commande. La manière dont YACC travaille signifie qu'il peut désormais séparer facilement des groupes de commandes et les réduire.

Comparons cela à la récursivité à droite, qui de manière plutôt confuse paraît meilleure aux yeux de beaucoup:

commands: /* empty */
	|
	command commands

Mais c'est très coûteux. Si on l'utilise comme règle %start, elle nécessite que YACC conserve toutes les commandes dans la file sur le tas, ce qui peut prendre beaucoup de ressources mémoires. Utilisez donc quoi qu'il arrive la récursivité à gauche lorsque vous analysez de longues instructions, comme des fichiers entiers. Il est parfois difficile d'éviter la récursivité à droite, mais si vos instructions ne sont pas trop longues, il est naturel d'utiliser la récursivité à gauche.

Si vous quelque chose qui termine (et donc qui sépare) vos commandes, la Récursion à droite paraît très naturelle, mais reste très coûteuse:

commands: /* empty */
	|
	command SEMICOLON commands

La manière adroite de programmer ceci est d'utiliser la récursivité à gauche (je n'ai trouvé cela tout seul non plus):

commands: /* empty */
	|
	commands command SEMICOLON

Les versions plus anciennes de ce guide pratique utilisaient par erreur la Récursion à droite. Markus Triska nous a gentiment informé à ce sujet.

6.3. Plus loin avec yylval : %union

Actuellement, nous avons besoin de définir LE type yylval. Ce n'est cependant pas toujours approprié. dans de nombreux cas nous avons besoin de pouvoir utiliser plusieurs types de données. Retournons sur notre thermostat fictif, nous souhaitons peut être être capable de choisir un heater pour le contrôler, comme ceci.

heater mainbuiling
	Selected 'mainbuilding' heater
target temperature 23
	'mainbuilding' heater target temperature now 23

Cela demande à yylval d'être une union, qui peut supporter les strings et les entiers – mais pas simultanément.

Souvenez vous que nous avons précédemment dit à YACC de quel type yylval est supposé être en définissant YYSTYPE. Il serai concevable de définir YYSTYPE ainsi comme une union, mais YACC a une meilleur méthode pour faire cela: les instructions %union.

A partir de l'exemple 4, nous écrivons maintenant la grammaire YACC de l'exemple 7. Tout d'abord l'introduction:

%token TOKHEATER TOKHEAT TOKTARGET TOKTEMPERATURE

%union 
{
        int number;
        char *string;
}

%token <number> STATE
%token <number> NUMBER
%token <string> WORD

Nous définissons notre union, qui contient seulement un nombre et un string. Puis en utilisant un une syntaxe étendue de %token nous expliquons à YACC à quelle partie de l'union chaque jeton doit accéder.

Dans ce cas, nous laissons le symbole STATE utiliser un entier comme précédemment. Il en va de même pour le symbole NUMBER, que nous utilisons pour lire les températures.

Le symbole WORD est lui par contre nouveau, et est déclaré pour avoir besoin d'un string.

Le fichier Lexer change lui aussi un petit peu:

%{
#include <stdio.h>
#include <string.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval.number=atoi(yytext); return NUMBER;
heater			return TOKHEATER;
heat                    return TOKHEAT;
on|off                  yylval.number=!strcmp(yytext,"on"); return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
[a-z0-9]+		yylval.string=strdup(yytext);return WORD;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

Comme vous pouvez le voir, nous n'accédons plus directement à yyval directement, nous ajoutons un suffixe indiquant à quelle partie nous souhaitons accéder. Nous n'avons cependant pas besoin de le faire dans la grammaire YACC, car YACC effectue le travail pour nous:

heater_select:
        TOKHEATER WORD
	{
	 	printf("\tSelected heater '%s'\n",$2);
        	heater=$2;
	}
        ;

A cause de de la déclaration %token au dessus, YACC choisit automatiquement la partie 'string' dans notre union. Notez aussi que nous stockons une copie de $2 qui est plus tard utilisée pour indiquer à l'utilisateur à quel heater il envoie la commande:

target_set:
        TOKTARGET TOKTEMPERATURE NUMBER
        {
	 	printf("\tHeater '%s' temperature set to %d\n",heater,$3);
  	}
	;

Pour plus de détails, Consultez l'exemple 7.y.

7. Déboguage

Particuliermeent lorsque l'on apprends, il est nécessaire d'avoir des outils de déboguage. Heureusement, YACC peut fournir énormément d'informations. Ces informations sont fournies au prix de temps système, vous aurez donc besoin d'interrupteurs pour les activer.

Lorsque vous compilez votre grammaire, ajoutez --debug et –verbose à votre ligne de commande. Dans votre l'en-tête C de votre grammaire , ajoutez :

int yydebug=1;

Cela générera le fichier 'y.output' qui détaille l'automate qui a été crée.

Lorsque vous lancez le binaire généré, il renverra énormément d'informations sur ce qui se passe. Cela inclus dans quel état se trouve l'automate et quels symboles sont en trains d'être lus.

Peter jinks a écrit une page sur le déboguage qui contient quelques erreurs classiques et comment les résoudre.

7.1. L'automate à état finis

Sous le capot, votre analyseur syntaxique YACC fonctionne comme un automate fini. Comme le nom l'indique, cet automate (ou machine à états finis) peut se trouver dans différents états. Il y a ensuite des règles qui gouvernent ces transitions d'un état à l'autre. Tout débute avec la règle 'racine' mentionnée plus tôt.

Pour citer la sortie de l'exemple 7:

state 0

    ZONETOK     , and go to state 1

    $default    reduce using rule 1 (commands)

    commands    go to state 29
    command     go to state 2
    zone_set    go to state 3

By default, this state reduces using the 'commands' rule. This is the aforementioned recursive rule that defines 'commands' to be built up from individual command statements, followed by a semicolon, followed by possibly more commands.

This state reduces until it hits something it understands, in this case, a ZONETOK, ie, the word 'zone'. It then goes to state 1, which deals further with a zone command:

state 1

    zone_set  ->  ZONETOK . quotedname zonecontent   (rule 4)

    QUOTE       , and go to state 4

    quotedname  go to state 5

The first line has a '.' in it to indicate where we are: we've just seen a ZONETOK and are now looking for a 'quotedname'. Apparently, a quotedname starts with a QUOTE, which sends us to state 4.

To follow this further, compile Example 7 with the flags mentioned in the Debugging section.

7.2. 7.Conflits : décalage/réduction, réduction/réduction

A chaque fois que YACC vous informe de la présence de conflits, vous pouvez avoir des soucis. Résoudre ces conflits semble un art qui peut vous apprendre beaucoup sur votre langage, plus que ce que vous n'auriez voulu en savoir.

Ces problèmes sont liés à l'interprétation de la séquence des symboles. Supposons que l'on définisse un langage qui ait besoin d'accepter les deux commandes suivantes:

delete heater all
delete heater number1

Pour ce faire, définissons cette grammaire:

	delete_heaters:
		TOKDELETE TOKHEATER mode
		{
			deleteheaters($3);
		}
	
	mode:	WORD

	delete_a_heater:
		TOKDELETE TOKHEATER WORD
		{
			delete($3);
		}

Vous devez déjà sentir les ennuis arriver. L'automate commence par lire le mot 'delete' puis doit décider de la transition en se basant sur le symbole suivant. Le symbole suivant peut aussi bien être un 'mode', spécifiant comment supprimer les 'heaters', ou le nom d'un 'heater' à supprimer.

Cependant le problème est que pour les deux commandes, le symbole suivant sera un 'WORD'. YACC n'a par conséquent aucune idée de ce qu'il doit faire. Cela conduit à une alerte 'réduction/réduction' et une seconde alerte : le nœud delete_a_heater ne sera jamais atteint.

Dans ce cas, le conflit est facilement résolu en renommant la première commande 'delete heaters all' ou en faisant de ALL un autre symbole. Mais parfois c'est plus difficile. Le fichier y.output généré lorsque vous lancez YACC avec l'opion –verbose peut être d'une aide formidable.

8. Lectures pour approfondir

GNU YACC (Bison) est fournit avec un fichier info (.info) très intéressant qui documente très bien la syntaxe YACC. Il ne mentionne Lex qu'une seule fois, mais sinon il est très bon. Vous pouvez lire les fichiers .info avec Emacs ou avec l'outil très bien fait 'pinfo'. Il est aussi disponible sur le site de GNU : BISON Manual.

Flex est fournit avec une page de man qui est très utile si vous avez déjà une idée approximative de ce que Flex fait. Le Flex Manual est aussi disponible en ligne.

Après cette introduction à Lex et YACC, vous pouvez avoir besoin de plus d'informations. Je n'ai pas encore lu ces livres, mais ils semblent assez bon:

Bison-The Yacc-Compatible Parser Generator

Par Charles Donnelly et Richard Stallman. Un lecteur d'Amazon le trouve très utile.

Lex & Yacc

Par John R. Levine, Tony Mason et Doug Brown. Considéré comme une référence sur le sujet, bein qu'un peu vieux. Commentaires sur Amazon.

Compilers : Principles, Techniques, and Tools

par Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Le 'Dragon Book'. De 1985 et ils continuent de le réimprimer. Considéré comme la base sur la construction de compilateurs.. Amazon.

Thomas Niemann a écrit un document expliquant comment écrire des compilateurs et des calculatrices avec Lex et YACC. Vous pouvez le trouver ici.

La newsgroup modérée comp.compilers peu aussi être très utile, mais gardez à l'esprit que les gens là bas ne sont pas une hotline dédiée aux parsers. Avant de poster, lisez leur page et plus spécialement la FAQ.

Lex - A Lexical Analyzer Generator par M. E. Lesk and E. Schmidt est l'une des sources de référence. Il peut être trouvé ici.

YACC: Yet Another Compiler Compiler par Stephen C. Johnson est l'une des sources de référence. Il peut être trouvé ici. Il contient des astuces sur le style.

9. Remerciements

  • Pete Jinks <pjj%cs.man.ac.uk>

  • Chris Lattner <sabre%nondot.org>

  • John W. Millaway <johnmillaway%yahoo.com>

  • Martin Neitzel <neitzel%gaertner.de>

  • Sumit Pandaya <sumit%elitecore.com>

  • Esmond Pitt <esmond.pitt%bigpond.com>

  • Eric S. Raymond

  • Bob Schmertz <schmertz%wam.umd.edu>

  • Adam Sulmicki <adam%cfar.umd.edu>

  • Markus Triska <triska%gmx.at>

  • Erik Verbruggen <erik%road-warrior.cs.kun.nl>

  • Gary V. Vaughan <gary%gnu.org> (read his awesome Autobook)

  • Ivo van der Wijk (Amaze Internet)