Lex et Yacc

Lex (flex sous Linux)

Il permet de générer un programme en C qui est un analyseur lexicale que l'on a décrit au préalable.

Le programme qui est généré s'appelle yylex. Il peut être utilisé dans un programme Yacc pour combiner analyse syntaxique et lexicale.

%%
[ \t]+$
" "+ printf(" ");

Il supprime les espaces et les tabulations en fin de ligne et il remplace toute séquence d'espace, par un seul espace. Le programme porte l'extension .l. La compilation se fait comme suit :

$ lex test.l

Un programme C est sortit.

Structure d'un programme Lex : 3 parties

- Définition
%%
- Règles
%%
- Procédures utilisateurs

Chaque partie est optionnelle.

Les règles

Elles ont un format en 2 parties: regexp action.

Les expressions régulières

Les méta-symboles utilisés pour décrire les expressions régulières :

Expression régulière	Chaîne de caractères
x	x
"x"	x même s'il est opérateur
\x	x même s'il est opérateur
[xy]	x ou y
[x-y]	Char entre x et y
.	N'importe quel caractère
^x	x en début de ligne
x$	x en fin de ligne
x?	x facultatif
x*	0 ou plusieurs x
x+	1 ou plusieurs x
x.y	x ou y
x/y	x si suivit de y

Les actions

Elles sont écrites en C :

Par défaut, le programme recopie l'entrée vers la sortie. Sinon :

Action	Description
;	Action vide, ignorer la chaîne.

Variables :

Variable	Description
yytext	Variable qui contient le la chaîne reconnue.
yyleng	Taille de la chaîne reconnue.

La fonction doit renvoyer un 1 pour arrêter le traitement après son exécution. Cette fonction s'exécute à la fin du fichier d'entrée.

Yacc

S'il est combiné avec Lex :

Dans la première partie du Lex, rajouter:

  #include "y.tab.h"

Il contient, entre autres, les symboles terminaux du Yacc.

Dans la troisième partie du Yacc :

  #include "lex.yy.c"

La compilation se fait comme suit :

$ yacc -d parse.y
$ lex fichier.l
$ gcc y.tab.c -ly -ll

L'option -d génère le fichier y.tab.h.

La structure d'un programme Yacc est composée également de 3 parties :

- Déclaration
%%
- Règles actions
%%
- Procédures utilisateurs

Une rèlge E -> E + T | T devient, en Yacc :

E : E + T
  | T
  ;

Variables associées :

Variable	Description	Valeur
$$	Règle courante	E
$1		E
$2		+
$3		T

Dans les actions Lex, on retrouvera en dernière position, un return de l'unité syntaxique.