Théorie des langages : Cours lex analyseur lexical
Télécharger PDFAnalyse lexicale
Compilation, 3LMD 2011 -2012
Université de Biskra
Mr. Meadi M.Nadjib 10
L'outil Lex (générateur d’analyseur Lexical) Introduction Lex est un utilitaire d'Unix. Son grand frère fLex est un produit GNU. Lex accepte en entrée des spécifications d'unités Lexicales sous forme de définitions régulières et produit un programme écrit dans le langage C qui, une fois compilé, reconnaît ces unités Lexicales. Ce programme est donc un analyseur Lexical).
> Lex fichier.l donne le fichier Lex.yy.c qu'il faut compiler avec Lex :
> gcc Lex.yy.c –l l Le fichier de spécifications Lex contient des expressions régulières suivies d'actions (règles de traduction). L'analyseur Lexical obtenu lit le texte d'entrée caractère par caractère jusqu'à ce qu'il trouve le plus long préfixe du texte d'entrée qui corresponde à l'une des expressions régulières. Dans le cas où plusieurs règles sont possibles, c'est la première règle rencontrée (de haut en bas) qui l'emporte. Il exécute alors l'action correspondante. Dans le cas où aucune règle ne peut être sélectionnée, l'action par défaut consiste à copier le caractère du fichier d'entrée en sortie. Les expressions réguliers Lex Une expression régulière Lex se compose de caractères normaux et de méta-caractères, qui ont une signification spéciale: $, \, ^, [,], {,}, <, >, +, -, *, /,|,?. Le tableau suivant donne les expressions régulières reconnues par Lex. Attention, Lex fait la différence entre les minuscules et les majuscules. Expression
SignificationExemple ctout caractère
c qui n’est pas opérateur ou métacaractère a \c caractère littéral c (lorsque c est un métacaractère) \+
\. "s " chaîne de caractères "bonjour " . n’importe quel caractère, sauf retour à la ligne (\n) a.b ^
l’expression qui suit ce symbole débute une ligne^abc$ l’expression qui précède ce symbole termine une ligneabc$ [s] n’importe quel caractère de s [abc] [^s] n’importe quel caractère qui n’est pas dans s [^xyz] r* 0 ou plusieurs occurrences de r b* r+ 1 ou plusieurs occurrences de r a+ r?
0 ou 1 occurrence de r
d? Compilateur Lex Compilateur C Analyseur Lexical résultant
Programme Lex Lex.yy.c Texte d'éntée
Lex.l Lex.yy.c Exécutable Flot des unités Lexicales Analyse lexicale
Compilation, 3LMD 2011 -2012
Université de Biskra
Mr. Meadi M.Nadjib 11
r{m} m occurrences de r e{3} r{m,n} entre m et n occurrences de r f{2,4} r1 r
2 r
1 suivie de r2 abr 1|r 2r 1 ou r2 c|d r1 /r
2 r1 si elle est suivie de r2 ab/cd (r)r (a|b)?c
<x>r r si Lex se trouve dans l’état x
<x>abc Structure d'un fichier Lex Un fichier de description pour Lex est formé de trois parties, selon le schéma suivant : %{ Déclaration en C des variables, des constants,...etc. %} Déclaration des définitions régulières. %% Expression régulières et actions correspondantes %% Déclaration des procédures auxiliaires Dans lequel aucune partie n'est obligatoire. Cependant, le séparateur "%%" est utilisé pour
séparer entre les déclarations et expression régulières et actions correspondantes (le productions). A. Partie des déclarations La section Déclarations peut elle même se composer de : a.Bloc littéral Cette partie d'un fichier Lex peut contenir : Commence par %{ et se termine par %}. Où %{ et %} doivent être placés en début de ligne. Contient des déclarations et définitions en C. Est copié tel quel dans le fichier Lex.yy.c produit par la commande Lex Les définitions et déclarations qu’il contient sont globales au programme produit par Lex. b.Définitions Associations d’identificateurs à des expressions régulières. . Ces définitions sont de la forme : notion
expression régulière Exemple : separ
[ \t\n] espace {separ}+ lettre
[A-Za-z] chiffre [0-9] ident
{lettre}({lettre}|{chiffre})* nbre
{chiffre}+ (\.{chiffre}+ )?(E[+\-]?{chiffre}+ )? Remarque Lorsqu’on se réfère à une expression régulière en utilisant un identificateur, celui-ci est mis entre accolades. Analyse lexicale
Compilation, 3LMD 2011 -2012
Université de Biskra
Mr. Meadi M.Nadjib 12
c. Conditions de départ Les conditions de départ permettent de définir plusieurs états de Lex Exemple %start etat1 etat2 .... Où etat1, état2 ... sont les états possibles de Lex B. Partie des productions Contient deux parties Partie gauche : - spécification des expressions régulières reconnues - pour une chaîne de lettres et de chiffres, les guillemets peuvent être omis - identificateurs d’expressions mis entre accolades Partie droite : - actions exécutées lorsque unités Lexicales reconnues - actions définies avec syntaxe C - si scanner appelé par parser YACC, alors : - les attributs de l’unité Lexicale reconnue doivent être déposés dans yylval - l’unité Lexicale reconnue doit être retournée Exemple { \t\n}{ /* pas d ’action */ } ``<=``{return(PPE);} ``<>``{return(DIF);} ``<`` {return(PPQ);} ``=`` {return(EGA);} ``>=``{return(PGE);} ``>`` {return(PGQ);} ``:=`` {return(AFF);} if
{return(si);} then {return(alors);} else
{return(sinon);} {ident}{yylval = yytext; return(id);} {nbre}{yylval = yytext; return(nb);} Remarques En cas de conflit, Lex choisit toujours la règle qui produit le plus long lexème. prog action1 program action2 La deuxième règle sera choisie. Si plusieurs règles donnent des lexèmes de mêmes longueurs, Lex choisit la première. prog action1 [a-z]
+ action2 La première règle sera choisie. Si aucune règle ne correspond au flot d'entrée, Lex choisit sa règle par défaut implicite : .|\n {ECHO} recopie le flot d'entrée sur le flot de sortie Analyse lexicale
Compilation, 3LMD 2011 -2012
Université de Biskra
Mr. Meadi M.Nadjib 13
C. Section Procédures auxiliaires Section optionnelle qui permet de : - définir toutes les fonctions utilisées dans les actions associées aux expressions reconnues - définir (si nécessaire) le programme principal (main()). Exemples
Ce premier exemple compte le nombre de voyelles, consonnes et caractères de ponctuations d'un texte entré au clavier. %{
int nbVoyelles, nbConsonnes, nbPonct; %} consonne
[b-df-hj-np-tv-xz] ponctuation [,;:?!\.] %% [aeiouy]
nbVoyelles++; {consonne}
nbConsonnes++; {ponctuation} nbPonct++; .|\n
// ne rien faire %% main() {nbVoyelles = nbConsonnes = nbPonct = 0; yylex(); printf("Il y a %d voyelles, %d consonnes et %d ponctuations.\n",nbVoyelles, nbConsonnes, nbPonct); } Variables et fonctions prédéfinies char yytext[ ] : tableau de caractères qui contient la chaîne d'entrée qui a été acceptée. int yyleng : longueur de cette chaîne. int yylex() : fonction qui lance l'analyseur (et appelle yywrap()). yylval: retourne la valeur associé à l'unité lexicale reconnue. ECHO afficher l'unité lexicale reconnue (équivalente à printf("%s",yytext); ) FILE *yyout: fichier de sortie. FILE *yyin: fichier d'entrée int yywrap(): fonction toujours appelée en fin de flot d'entrée. Elle ne fait rien par défaut, mais l'utilisateur peut la redéfinir dans la section des fonctions auxiliaires. yywrap() retourne 0 si l'analyse doit se poursuivre (sur un autre fichier d'entrée) et 1 sinon. unput(char c) : remet le caractère dans le flot d'entrée. int yylineno : numéro de la ligne courante. yymore(): fonction qui concatène la chaîne actuelle yytext avec celle qui a été reconnue avant yyless(): fonction admettant un entier comme argument, yyless(k>0) : supprime les (yyleng-k) derniers caractères de yytext, dont la longueur devient alors k - recule le pointeur de lecture sur le fichier d’entrée de (yyleng-k) positions, les caractères supprimés de yytext seront donc considérés pour la reconnaissance des prochaines unités yyterminate() : fonction qui stoppe l'analyseur . Analyse lexicale
Compilation, 3LMD 2011 -2012
Université de Biskra
Mr. Meadi M.Nadjib 14
Exemple L'exemple suivant insert le numéro de ligne à chaque ligne dans un fichier. %{ int yylineno; %} %% ^(.*)\n printf("%4d\t%s", ++yylineno, yytext); %% int main(int argc, char *argv[]) { yyin = fopen(argv[1], "r"); yylex(); fclose(yyin); } Etude de cas...