Algorithme - L'analyse lexicale, première phase de la compilation qui consiste à lire le code source pour en extraire les unités lexicales,
Un billet blog de matser
Le 06/09/2023, par emmesse, Membre confirmé
L'analyse lexicale est une phase, la première, de la compilation. Elle consiste à lire le code source pour en extraire les unités lexicales.
Une unité lexicale est une entité qui correspond à un élément du langage traduit par le compilateur. Cette unité lexicale peut être accompagnée d'un attribut, un lexème, qui spécifie l'unité lexicale. Par exemple, sur la ligne de code suivante :
Vitesse := 35
L'analyseur lexical retournera, un par un à chaque fois que l'analyseur syntaxique le lui demande, les unités lexicales suivantes :
<identificateur,Vitesse> , <deux-points-egal, > <nb,35>
Pour reconnaître un lexème, l'analyseur lexical utilise des diagrammes de transition. Ce sont des graphes orientés dont les nœuds sont des états en forme de cercle et comportant un numéro. Les arcs sont associés à un caractère. L'analyseur lexical change d'état à chaque caractère lu. Ce diagramme de transition comporte un ou plusieurs états d'acceptations indiqués par un double cercle. Lorsque l'un de ces états est atteint, l'analyseur lexical retourne l'unité lexicale indiquée près de cet état d'acceptation. Parfois, quand un arc indique "autre", l'analyseur lexical doit dépasser le dernier caractère du lexème. Dans ce cas, il doit donc reculer d'un caractère avant de retourner l'unité lexicale. Ce cas est indiqué par une étoile qui précède le nom de l'unité lexicale.
Un diagramme de transition qui représente un identificateur (une lettre éventuellement précédée d'un ou plusieurs underscores et éventuellement suivie par une ou plusieurs lettre ou chiffres ou underscores) pourra être le suivant :
L'analyseur lexical utilise les diagrammes de transition les uns après les autres. Si le diagramme ne correspond pas, les variables sont actualisées afin d'utiliser le diagramme suivant. Si tous les diagrammes ont été parcourus, une erreur est spécifiée.
Le code source est chargé dans un tampon. Il est parcouru par la variable "enavant". La variable "debutlex" indique le premier caractère du lexème courant. Il sert, en cas d'échec d'un diagramme, à remettre la variable enavant au début du lexème.
Afin d'être compatible avec l'UTF-8, on utilise une variable taille qui indique de combien d'octets est le caractère lu. Si le premier octet est compris entre 0 et 127, le caractère est encodé sur un octet. La valeur de la variable taille est égal à 1. Si il est compris entre 224 et 239, taille sera égal à 2. Si il est compris entre 224 et 239, taille sera egal à 3, et à 4 pour une valeur comprise entre 240 et 255. Sinon le programme signale un caractère non utf-8, incrémente enavant et la fonction carsuiv est appelée récursivement.
Le diagramme de transition est implémenté avec l'instruction switch dont chaque cas indique un état. Le caractère est lu par la fonction carsuiv et l'analyseur lexical choisi l'état suivant en fonction de ce caractère.
On utilisera un type énumération pour que l'analyseur désigne une unité lexicale.
Nous allons implémenter un analyseur lexical qui reconnaîtra trois types de lexeme : identificateur, nombre, deux-points et deux-points-egal.
Voici les diagrammes de transitions :
Voici le programme :
terminal.hpp
main.cpp
lexical.hpp:
lexical.cpp:
Une unité lexicale est une entité qui correspond à un élément du langage traduit par le compilateur. Cette unité lexicale peut être accompagnée d'un attribut, un lexème, qui spécifie l'unité lexicale. Par exemple, sur la ligne de code suivante :
Vitesse := 35
L'analyseur lexical retournera, un par un à chaque fois que l'analyseur syntaxique le lui demande, les unités lexicales suivantes :
<identificateur,Vitesse> , <deux-points-egal, > <nb,35>
Pour reconnaître un lexème, l'analyseur lexical utilise des diagrammes de transition. Ce sont des graphes orientés dont les nœuds sont des états en forme de cercle et comportant un numéro. Les arcs sont associés à un caractère. L'analyseur lexical change d'état à chaque caractère lu. Ce diagramme de transition comporte un ou plusieurs états d'acceptations indiqués par un double cercle. Lorsque l'un de ces états est atteint, l'analyseur lexical retourne l'unité lexicale indiquée près de cet état d'acceptation. Parfois, quand un arc indique "autre", l'analyseur lexical doit dépasser le dernier caractère du lexème. Dans ce cas, il doit donc reculer d'un caractère avant de retourner l'unité lexicale. Ce cas est indiqué par une étoile qui précède le nom de l'unité lexicale.
Un diagramme de transition qui représente un identificateur (une lettre éventuellement précédée d'un ou plusieurs underscores et éventuellement suivie par une ou plusieurs lettre ou chiffres ou underscores) pourra être le suivant :
L'analyseur lexical utilise les diagrammes de transition les uns après les autres. Si le diagramme ne correspond pas, les variables sont actualisées afin d'utiliser le diagramme suivant. Si tous les diagrammes ont été parcourus, une erreur est spécifiée.
Le code source est chargé dans un tampon. Il est parcouru par la variable "enavant". La variable "debutlex" indique le premier caractère du lexème courant. Il sert, en cas d'échec d'un diagramme, à remettre la variable enavant au début du lexème.
Afin d'être compatible avec l'UTF-8, on utilise une variable taille qui indique de combien d'octets est le caractère lu. Si le premier octet est compris entre 0 et 127, le caractère est encodé sur un octet. La valeur de la variable taille est égal à 1. Si il est compris entre 224 et 239, taille sera égal à 2. Si il est compris entre 224 et 239, taille sera egal à 3, et à 4 pour une valeur comprise entre 240 et 255. Sinon le programme signale un caractère non utf-8, incrémente enavant et la fonction carsuiv est appelée récursivement.
Le diagramme de transition est implémenté avec l'instruction switch dont chaque cas indique un état. Le caractère est lu par la fonction carsuiv et l'analyseur lexical choisi l'état suivant en fonction de ce caractère.
On utilisera un type énumération pour que l'analyseur désigne une unité lexicale.
Nous allons implémenter un analyseur lexical qui reconnaîtra trois types de lexeme : identificateur, nombre, deux-points et deux-points-egal.
Voici les diagrammes de transitions :
Voici le programme :
terminal.hpp
Code cpp : |
1 2 3 4 5 6 | #ifndef TERMINAL_HPP #define TERMINAL_HPP enum terminal {identificateur,nombre,deuxpointsegal,deuxpoints,FDF}; #endif |
Code cpp : |
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 | #include <iostream> #include <string> #include <vector> #include "lexical.hpp" #include "terminal.hpp" int main(int argc,char *argv[]){ std::vector<std::string>args; for(unsigned i=0;i<static_cast<unsigned>(argc);++i) args.push_back(argv[i]); if(argc!=2) std::cerr<<"manque le fichier"<<std::endl; else{ lexical L(args[1]); std::string lexeme; terminal ulex; int ligne=1; for(L.analex(ulex,lexeme,ligne);ulex!=FDF;L.analex(ulex,lexeme,ligne)) switch(ulex){ case identificateur: std::cout<<"ligne "<<ligne<<": identificateur "<<lexeme<<std::endl; break; case deuxpoints: std::cout<<"ligne "<<ligne<<": deuxpoints "<<std::endl; break; case deuxpointsegal: std::cout<<"ligne "<<ligne<<": deux-points-egal "<<std::endl; break; case nombre: std::cout<<"ligne "<<ligne<<": nombre "<<lexeme<<std::endl; break; } } } |
Code cpp : |
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 | #ifndef LEXICAL_HPP #define LEXICAL_HPP #include <string> #include <fstream> #include "terminal.hpp" class lexical{ public: lexical(std::string fichierentree); void analex(terminal &ulex,std::string &lexeme,int &ligne); private: std::string texte; std::ifstream entree; size_t enavant,debutlex; int taille; std::string readFileIntoString(const std::string path); bool obtenirFDF(terminal &ulex); bool obtenirblanc(int &ligne); bool obteniridentificateur(terminal &ulex,std::string &lexeme); bool obtenirnombre(terminal &ulex,std::string &lexeme); bool obtenir2ptsega(terminal &ulex); std::string carsuiv(); }; #endif |
Code cpp : |
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 | #include <string> #include <iostream> #include "lexical.hpp" #include "terminal.hpp" lexical::lexical(std::string fichierentree):enavant(0),debutlex(0){ entree.open(fichierentree.c_str()); texte = readFileIntoString(fichierentree); } std::string lexical::readFileIntoString(const std::string path) { if (!entree.is_open()){ std::cerr << "Could not open the file - '" << path << "'" << std::endl; exit(1); } else{ return std::string((std::istreambuf_iterator<char>(entree)), std::istreambuf_iterator<char>()); } } void lexical::analex(terminal &ulex,std::string &lexeme,int &ligne){ if(obtenirblanc(ligne)){ analex(ulex,lexeme,ligne);//ignorer le blanc. enavant pointe sur le premier caractère du lexeme suivant } else if(obtenirFDF(ulex)){ return; } else if(obteniridentificateur(ulex,lexeme)){ return; } else if(obtenir2ptsega(ulex)){ return; } else if(obtenirnombre(ulex,lexeme)){ return; } else{ std::cerr<<"caratère hors langage"<<std::endl; enavant+=taille;//ignorer le caractère hors langage analex(ulex,lexeme,ligne); } } bool lexical::obtenirblanc(int &ligne){ int etat=0; bool continuer=true; bool reussi; debutlex=enavant; std::string caracterelu; while(continuer) switch(etat){ case 0: caracterelu=carsuiv(); if(caracterelu=="\n"){ ligne++; etat=1; } else if(caracterelu==" "||caracterelu=="\t"||caracterelu=="\r") etat=1; else{ continuer=false; reussi=false; enavant=debutlex; } break; case 1: continuer=false; reussi=true; } return reussi; } bool lexical::obtenirFDF(terminal &ulex){ int etat=0; bool continuer=true; bool reussi; debutlex=enavant; std::string caracterelu; while(continuer) switch(etat){ case 0: caracterelu=carsuiv(); if(caracterelu[0]=='\0') etat=1; else{ continuer=false; reussi=false; enavant=debutlex; } break; case 1: continuer=false; reussi=true; ulex=FDF; break; } return reussi; } bool lexical::obteniridentificateur(terminal &ulex,std::string &lexeme){ int etat=0; bool continuer=true; bool reussi; lexeme=""; debutlex=enavant; std::string caracterelu; while(continuer) switch(etat){ case 0: caracterelu=carsuiv(); if(caracterelu=="_"){ lexeme+=caracterelu; etat=0; } else if(caracterelu >="A" && caracterelu<="Z" || caracterelu >= "a" && caracterelu <= "z"){ lexeme+=caracterelu; etat=1; } else{//echec enavant=debutlex; continuer=false; reussi=false; } break; case 1: caracterelu=carsuiv(); if(caracterelu >="A" && caracterelu<="Z" || caracterelu >= "a" && caracterelu <= "z" || caracterelu >="0" && caracterelu <= "9" || caracterelu=="_"){ lexeme+=caracterelu; etat=1; } else //autre caractère etat=2; break; case 2: continuer=false; reussi=true; enavant-=taille;//reculer pour le dépassement de caractère (autre caractère) ulex=identificateur; } return reussi; } bool lexical::obtenir2ptsega(terminal &ulex){ bool continuer=true; bool reussi; int etat=0; debutlex=enavant; std::string caracterelu; while(continuer) switch(etat){ case 0: caracterelu=carsuiv(); if(caracterelu==":") etat=1; else{ continuer=false; reussi=false; enavant=debutlex; } break; case 1: caracterelu=carsuiv(); if(caracterelu=="=") etat=2; else etat=3; break; case 2: ulex=deuxpointsegal;//ulex est un attribut de la classe lexical continuer=false; reussi=true; break; case 3: ulex=deuxpoints; enavant-=taille; reussi=true; continuer=false; break; } return reussi; } bool lexical::obtenirnombre(terminal &ulex,std::string &lexeme){ int etat=0; bool continuer=true; bool reussi; lexeme=""; debutlex=enavant; std::string caracterelu; while(continuer) switch(etat){ case 0: caracterelu=carsuiv(); if(caracterelu==","){ lexeme+=caracterelu; etat=2; } else if(caracterelu>="0" && caracterelu<="9"){ lexeme+=caracterelu; etat=1; } else{ continuer=false; reussi=false; enavant=debutlex; } break; case 1: caracterelu=carsuiv(); if(caracterelu==","){ lexeme+=caracterelu; etat=2; } else if(caracterelu>="0" && caracterelu<="9"){ lexeme+=caracterelu; etat=1; } else etat=4;//autre break; case 2: caracterelu=carsuiv(); if(caracterelu>="0" && caracterelu<="9"){ lexeme+=caracterelu; etat=3; } else{ enavant=debutlex; continuer=false; reussi=false; } break; case 3: caracterelu=carsuiv(); if(caracterelu>="0" && caracterelu<="9"){ lexeme+=caracterelu; etat=3; } else{ etat=4; } break; case 4: continuer=false; reussi=true; ulex=nombre; enavant-=taille;//reculer pour le dépassement de caractère (autre caractère) } return reussi; } std::string lexical::carsuiv(){ if((unsigned char)texte[enavant] >= (unsigned char)0 && texte[enavant] <= (unsigned char)127) taille=1; else if((unsigned char)texte[enavant] >= (unsigned char)0xC2 && (unsigned char)texte[enavant] <= (unsigned char)0xdf) taille=2; else if((unsigned char)texte[enavant] >= (unsigned char)0xe0 && (unsigned char)texte[enavant] <= (unsigned char)0xef) taille=3; else if((unsigned char)texte[enavant] >= (unsigned char)0xf0 && (unsigned char)texte[enavant] <= (unsigned char)0xff) taille=4; else{ std::cerr<<"caractère non UTF-8"<<std::endl; enavant++; return carsuiv(); } std::string c=texte.substr(enavant,taille); enavant+=taille; return c; } |