IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

matser

un analyseur lexical

Noter ce billet
par , 11/08/2022 à 15h28 (258 Affichages)
Un analyseur lexical

Scanneur et analyseur
Un analyseur lexical agit dans un compilateur. Il lit les caractère du code source pour en faire des lexèmes, une suite de caractères ayant un sens lexical, et retourne une unité lexicale correspondant à ce lexème à l'analyseur syntaxique, à chaque fois que ce dernier le demande.
L'analyseur lexical est accompagné d'un scanneur, qui lit les caractères du fichier source et peut aussi reculer de un ou plusieurs caractère si demandé.
scanneur.hpp:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifndef SCANNEUR_HPP
#define SCANNEUR_HPP

#include <fstream>
#include <string>

constexpr int taille=3000;

class scanneur{
public:
  scanneur(std::string const& nomFichier);
  char carsuiv();
  void reculer(int const &n);
  int getTailleFichier();
private:
  std::ifstream fichier;
  char tampon[taille+1];// +1 car sentinelle EOF
  int Ntampon;
  int enAvant;
  int derniers;
  int tailleFichier;
};

#endif
scanneur.cpp:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <fstream>
#include <iostream>
#include "scanneur.hpp"

scanneur::scanneur(std::string const& nomFichier):Ntampon(1),enAvant(0),
						  derniers(0){
  fichier.open(nomFichier.c_str(),std::ios::binary|std::ios::in);
  fichier.seekg(0,std::ios_base::end);
  tailleFichier=fichier.tellg();
  fichier.seekg(0,std::ios_base::beg);
  if(taille<=tailleFichier){
    fichier.read(tampon,taille);
    tampon[taille]=EOF;
  }
  else{
    derniers=tailleFichier;
    fichier.read(tampon,derniers);
    Ntampon=1;
    tampon[derniers]=EOF;
    enAvant=0;
  }
}

char scanneur::carsuiv(){
  if(tampon[enAvant]==EOF)
    if(enAvant!=taille)
      return tampon[enAvant++];//enAvant++ car on pourrait devoir reculer
    else if((Ntampon+1)*taille<=tailleFichier){//++ car tampon suivant
      fichier.read(tampon,taille);
      Ntampon++;
      enAvant=0;
      derniers=0;
      return tampon[enAvant++];
    }
    else{
      derniers=tailleFichier%(Ntampon*taille);
      fichier.read(tampon,derniers);
      Ntampon++;
      tampon[derniers]=EOF;
      enAvant=0;
      return tampon[enAvant++];
    }
  else
    return tampon[enAvant++];
}

void scanneur::reculer(int const &n){
  for(int i=0;i<n;i++){
    if(enAvant==0){
      if(Ntampon>1){
	fichier.seekg((Ntampon-2)*taille,std::ios_base::beg);
   	fichier.read(tampon,taille);
	enAvant=taille-1;
      }
      else if(derniers!=0)
	enAvant=derniers-1;
      else
	enAvant=taille-1;
      Ntampon--;
    }
    else
      enAvant--;
  }
}

int scanneur::getTailleFichier(){
  return tailleFichier;
}
Analyseur lexical
Pour obtenir un lexème, l'analyseur lexical se base sur des diagrammes de transition. Il s'agit là d'un graphe orienté dont les états sont numérotés et le coût des arcs représente un caractère. Il y a un état initial et un ou des états d'acceptations. Par exemple, le diagramme de transition des opérateurs de relation (<, <=, =, <>,>= et >) est le suivant:
Nom : oprel.png
Affichages : 37
Taille : 63,4 Ko
On utilise la variable "etat" qui indique dans quel état on se trouve. Le scanneur donne alors un caractère. Si il y a un arc sortant de l'état courant dont le coût est ce caractère, l'analyseur lexical se met dans l'état atteint par cet arc. Si cet état est l'un des états d'acceptation, l'analyseur lexical se termine en retournant l'unité lexicale indiquée. Si il n'y a pas de tel arc, la fonction d'échec est appelé. Celle-ci réinitialise la variable etat à 0,recule du nombre de caractères lu et recommence avec le diagramme suivant. Le nombre de caractères lus est dans la variable debutlex. À chaque fois que un caractère est lu, cette variable est incrémenté. Dans la fonction d'échec, cette variable est remis à 0 après avoir reculé du nombre de caractère indiqué par cette dernière.
Un diagramme de transition est implémenté par une fonction. Dans celle-ci, il y a une boucle while dont la condition est une variable booléenne appelé "continuer". Cette boucle contient une instruction switch(etat), Les cas sont les états du diagramme de transition.
Remarquons que dans le diagramme de transition des opérateurs de relation la mention "autre" des arcs qui aboutissent aux états 4 et 7. À l'état 4, "autre" est un caractère différend de '=' et '>'. ce caractère n'appartient à aucun des trois lexèmes "<=", "<" et "<>". Il appartient donc au lexème suivant. Quand le lexème "<" est trouvé, le scanneur doit reculer d'un caractère afin que celui-ci puisse être reconnu dans le lexème suivant. Ceci s'indique par l'étoile à côté de l'état d'acceptation.
L'analyseur lexical est censé ignorer les séparateur (espace, tabulation et nouvelle ligne). Il y a bien des diagrammes pour ces symboles, mais au lieu de retourner une unité lexicale, il continue d'analyser, sans reculer car ce n'est pas un échec.
Les unités lexicales sont représentée par la classe unilex, constituée d'un terminal et d'un lexème et, si besoin, un attribut pour l'opérateur de relation, qui est un type énumération. Le terminal est un type énumération, le lexème est la chaine de caractères lu dans le code source et est associé à ce terminal.
par exemple, le diagramme de transition sur les opérateurs de relation sera codé comme ceci:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
void lexical::obteniroprel(){
  std::string lexeme;
  while(continuer)
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c=='<')
	etat=1;
      else if(c=='>')
	etat=5;
      else if(c=='=')
	etat=8;
      else{
	continuer=false;
	reussi=false;
      }
      break;
    case 1:
      c=scan.carsuiv();
      debutlex++;
      if(c=='=')
	etat=2;
      else if(c=='>')
	etat=3;
      else
	etat=4;
      break;
    case 2:
      ulex.setlex(oprel);
      ulex.setrel(PPE);
      reussi=true;
      continuer=false;
      break;
    case 3:
      ulex.setlex(oprel);
      ulex.setrel(DIFF);
      reussi=true;
      continuer=false;
      break;
    case 4:
      scan.reculer(1);
      ulex.setlex(oprel);
      ulex.setrel(PPQ);
      reussi=true;
      continuer=false;
      break;
    case 5:
      c=scan.carsuiv();
      debutlex++;
      if(c=='=')
	etat=6;
      else
	etat=7;
      break;     
    case 6:
      ulex.setlex(oprel);
      ulex.setrel(PGE);
      reussi=true;
      continuer=false;
      break;
    case 7:
      scan.reculer(1);
      ulex.setlex(oprel);
      ulex.setrel(PGQ);
      reussi=true;
      continuer=false;
      break;
    case 8:
      ulex.setlex(oprel);
      ulex.setrel(EGAL);
      reussi=true;
      continuer=false;
      break;
    }
}
Un exemple
Nous allons faire ici un exemple d'analyseur lexical. Ce dernier devra reconnaître les identificateurs, les entiers, les décimaux et les symboles '+', '-', '*','/'.

On utilise le scanneur vu plus haut.

Le fichier symboles.hpp contient le type énumération des terminaux. unilex.hpp et unilex.cpp implémentent les unités lexicales. Le terminal dolar est utilisé pour nommer la fin du fichier.
Le fichier symboles.hpp
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
#ifndef SYMBOLES_HPP
#define SYMBOLES_HPP

enum terminal{identificateur,decimal,entier,plus,moins,etoile,slash,dolar};
#endif
fichier unilex.hpp
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef UNILEX_HPP
#define UNILEX_HPP

#include <string>
#include <vector>
#include "symboles.hpp"

class unilex{
public:
  terminal getlex();
  void setlex(terminal const &x);
  std::string getlexeme();
  void setlexeme(std::string const &s);
protected:
  terminal unitlex; //unitlex, pas unilex
  std::string lexeme;
};
#endif
unilex.cpp:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <string>
#include "unilex.hpp"
#include "symboles.hpp"

terminal unilex::getlex(){
  return unitlex;//unitlex, pas unilex
}

void unilex::setlex(terminal const &x){
  unitlex=x;
}
std::string unilex::getlexeme(){
  return lexeme;
}
void unilex::setlexeme(std::string const &s){
  lexeme=s;
}
voici les diagrammes de transition proposés:
Nom : decimal.png
Affichages : 13
Taille : 44,1 Ko
Nom : entier.png
Affichages : 32
Taille : 11,6 Ko
Nom : etoile.png
Affichages : 32
Taille : 7,2 Ko
Nom : identificateur.png
Affichages : 32
Taille : 13,6 Ko
Nom : moins.png
Affichages : 33
Taille : 7,3 Ko
Nom : plus.png
Affichages : 33
Taille : 7,1 Ko
Nom : slash.png
Affichages : 32
Taille : 7,2 Ko

Nous remarquerons que les lexèmes dont l'unité lexicale est "entier", et que les lexèmes dont l'unité lexicale est "décimal", peuvent débuter par les mêmes caractères (des chiffres uniquement). Si l'analyseur lexical tente de tester un entier alors qu'un décimal doit être lu dans le texte d'entrée, il lira un entier jusque la virgule, et retournera l'unité lexical "entier". Puis, pour le lexème suivant, il tombera sur le caractère virgule et indiquera un décimal séparément de l'entier précédent. C'est pourquoi, on doit d'abord chercher le plus long avant le plus court. En l’occurrence, il faut chercher un décimal avant de chercher un entier, sur le même lexème.
En tentant de détecter un décimal alors que le texte d'entrée présente un entier, lors que l'analyseur lexical arrive à la fin de l'entier, il trouvera un caractère différent de la virgule et appellera la fonction d'échec. Le scanneur reculera jusque au premier chiffre (on recule du nombre de caractères indiqué par la variable debutlex, qui contiendra le nombre de chiffres lus), puis cherchera un entier, et le détectera.

Ces diagrammes de transitions sont implémentés dans la classe lexical:
lexical.hpp:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#ifndef LEXICAL_HPP
#define LEXICAL_HPP

#include <vector>
#include <string>
#include "unilex.hpp"
#include "scanneur.hpp"

class lexical{
public:
  lexical(std::string const &nomfichier);
  int getligne();
  unilex analex();
private:
  void obtenirseparateur();
  void obtenirentier();
  void obtenirdecimal();
  void obteniridentificateur();
  void obtenirplus();
  void obtenirmoins();
  void obteniretoile();
  void obtenirslash();
  void obtenirdolar();
  void echec();
  int debutlex,etat,ligne;
  char c;
  bool continuer,reussi;
  unilex ulex;
  scanneur scan;
};
#endif
lexical.cpp:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
#include <iostream>
#include <string>
#include <vector>
#include <map>

#include "unilex.hpp"
#include "symboles.hpp"
#include "lexical.hpp"
#include "scanneur.hpp"

lexical::lexical(std::string const &nomfichier):debutlex(0),
						etat(0),scan(nomfichier),
						ligne(1),continuer(true) {
  /*corps vide*/
}

void lexical::echec(){
  scan.reculer(debutlex);
  continuer=true;
  debutlex=etat=0;
}

unilex lexical::analex(){
  while(true){
    continuer=true;
    debutlex=etat=0;

    obtenirseparateur();
    if(reussi)
      continue;//séparateurs ignorés
    else
      echec();
 
    obteniridentificateur();
    if(reussi)
      return ulex;
    else
      echec();

    obtenirdecimal();   //obtenirdecimal() avant obtenirentier()
    if(reussi)
      return ulex;
    else
      echec();

    obtenirentier();
    if(reussi)
      return ulex;
    else
      echec();

    obtenirplus();
    if(reussi)
      return ulex;
    else
      echec();

    obtenirmoins();
    if(reussi)
      return ulex;
    else echec();

    obteniretoile();
    if(reussi)
      return ulex;
    else echec();

    obtenirslash();
    if(reussi)
      return ulex;
    else echec();

    obtenirdolar();
    if(reussi)
      return ulex;
    else
      echec();
    
    std::cerr<<std::endl<<"ligne "<<getligne()<<": symbole hors langage"
	     <<std::endl<<scan.carsuiv()<<std::endl;
  }
}


int lexical::getligne(){
  return ligne;
}

void lexical::obtenirseparateur(){
  while(continuer)
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c=='\n'){
	ligne++;
	etat=1;
      }
      else if(c=='\r' || c=='t' || c==' ')
	etat=1;
      else{
	continuer=false;
	reussi=false;
      }
      break;
    case 1:
      reussi=true;
      continuer=false;
    }
}

void lexical::obteniridentificateur(){
  std::string lexeme;
  while(continuer)
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c>='a' && c<='z' || c>='A' && c<='Z'){
	lexeme+=c;
	etat=1;
      }
      else{
	continuer=false;
	reussi=false;
      }
      break;
    case 1:
      c=scan.carsuiv();
      debutlex++;
      if(c>='a' && c<='z' || c>='A' && c<='Z' || c>='0' && c<='9'){
	lexeme+=c;
	etat=1;
      }
      else
	etat=2;
      break;
    case 2:
      scan.reculer(1);
      ulex.setlex(identificateur);
      ulex.setlexeme(lexeme);
      reussi=true;
      continuer=false;
    }
}

void lexical::obtenirentier(){
  std::string lexeme;
  while(continuer)
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c>='0' && c<='9'){
	lexeme+=c;
	etat=1;
      }
      else{
	continuer=false;
	reussi=false;
      }
      break;
    case 1:
      c=scan.carsuiv();
      debutlex++;
      if(c>='0' && c<='9'){
	lexeme+=c;
	etat=1;
      }
      else
	etat=2;
      break;
    case 2:
      scan.reculer(1);
      ulex.setlex(entier);
      ulex.setlexeme(lexeme);
      reussi=true;
      continuer=false;
    } 
}

void lexical::obtenirdecimal(){
  std::string lexeme;
  while(continuer)
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c>='0' && c<='9'){
	lexeme+=c;
	etat=0;
      }
      else if(c==','){
	lexeme+=c;
	etat=1;
      }
      else{
	continuer=false;
	reussi=false;
      }
      break;
    case 1:
      c=scan.carsuiv();
      debutlex++;
      if(c>='0' && c<='9'){
	lexeme+=c;
	etat=2;
      }
      else{
	continuer=false;
	reussi=false;
      }
      break;
    case 2:
      c=scan.carsuiv();
      debutlex++;
      if(c=='e'||c=='E'){
	lexeme+=c;
	etat=3;
      }
      else if(c>='0'&&c<='9'){
	lexeme+=c;
	etat=2;
      }
      else
	etat=6;
      break;
    case 3:
      c=scan.carsuiv();
      debutlex++;
      if(c=='+'||c=='-'){
	lexeme+=c;
	etat=4;
      }
      else if(c>='0' && c<='9'){
	lexeme+=c;
	etat=5;
      }
      else{
	reussi=false;
	continuer=false;
      }
      break;
    case 4:
      c=scan.carsuiv();
      debutlex++;
      if(c>='0' && c<='9'){
	lexeme+=c;
	etat=5;
      }
      else{
	reussi=false;
	continuer=false;
      }
      break;
    case 5:
      c=scan.carsuiv();
      debutlex++;
      if(c>='0' && c<='9'){
	lexeme+=c;
	etat=5;
      }
      else
	etat=6;
      break;     
    case 6:
      scan.reculer(1);
      ulex.setlex(decimal);
      ulex.setlexeme(lexeme);
      reussi=true;
      continuer=false;
    }
}

void lexical::obtenirplus(){
  while(continuer){
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c=='+')
	etat=1;
      else{
	reussi=false;
	continuer=false;
      }
      break;
    case 1:
      ulex.setlex(plus);
      reussi=true;
      continuer=false;
    }
  }
}

void lexical::obtenirmoins(){
  while(continuer){
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c=='-')
	etat=1;
      else{
	reussi=false;
	continuer=false;
      }
      break;
    case 1:
      ulex.setlex(moins);
      reussi=true;
      continuer=false;
    }
  }
}

void lexical::obteniretoile(){
  while(continuer){
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c=='*')
	etat=1;
      else{
	reussi=false;
	continuer=false;
      }
      break;
    case 1:
      ulex.setlex(etoile);
      reussi=true;
      continuer=false;
    }
  }
}

void lexical::obtenirslash(){
  while(continuer){
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c=='/')
	etat=1;
      else{
	reussi=false;
	continuer=false;
      }
      break;
    case 1:
      ulex.setlex(slash);
      reussi=true;
      continuer=false;
    }
  }
}

void lexical::obtenirdolar(){
  while(continuer)
    switch(etat){
    case 0:
      c=scan.carsuiv();
      debutlex++;
      if(c==EOF){
	etat=1;
      }
      else{
	continuer=false;
	reussi=false;
      }
      break;
    case 1:
      ulex.setlex(dolar);
      reussi=true;
      continuer=false;
    }
}
le fichier main.cpp:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include "lexical.hpp"
#include "unilex.hpp"


int main(int argc,char *argv[]){
  lexical L(argv[1]);
  int ligne;
  unilex lex;
  for(lex=L.analex();lex.getlex()!=dolar;lex=L.analex()){
    ligne=L.getligne();
    std::cout<<"ligne "<<ligne<<":";
    if(lex.getlex()==identificateur)
      std::cout<<"identificateur "<<lex.getlexeme()<<std::endl;
    else if(lex.getlex()==entier)
      std::cout<<"entier "<<lex.getlexeme()<<std::endl;
    else if(lex.getlex()==decimal)
      std::cout<<"decimal "<<lex.getlexeme()<<std::endl;
    else if(lex.getlex()==plus)
      std::cout<<"symbole plus"<<std::endl;
    else if(lex.getlex()==moins)
      std::cout<<"symbole moins"<<std::endl;
    else if(lex.getlex()==etoile)
      std::cout<<"symbole étoile"<<std::endl;
    else if(lex.getlex()==slash)
      std::cout<<"symbole slash"<<std::endl;
  }
}
le fichier de test est un ensemble de lexèmes. On peut, par exemple, y mettre ceci:
fichier nomé test:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
54,07e8
3,0e-4
4,54e+10
2,5 ,65 8,3E10
ppf -+
*
/
1234567890
le résultat est:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
ligne 1:decimal 54,07e8
ligne 2:decimal 3,0e-4
ligne 3:decimal 4,54e+10
ligne 4:decimal 2,5
ligne 4:decimal ,65
ligne 4:decimal 8,3E10
ligne 5:identificateur ppf
ligne 5:symbole moins
ligne 5:symbole plus
ligne 6:symbole étoile
ligne 7:symbole slash
ligne 8:entier 1234567890

Envoyer le billet « un analyseur lexical » dans le blog Viadeo Envoyer le billet « un analyseur lexical » dans le blog Twitter Envoyer le billet « un analyseur lexical » dans le blog Google Envoyer le billet « un analyseur lexical » dans le blog Facebook Envoyer le billet « un analyseur lexical » dans le blog Digg Envoyer le billet « un analyseur lexical » dans le blog Delicious Envoyer le billet « un analyseur lexical » dans le blog MySpace Envoyer le billet « un analyseur lexical » dans le blog Yahoo

Mis à jour Aujourd'hui à 14h52 par matser

Catégories
Sans catégorie

Commentaires