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

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 :
,

643392

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 :

643393

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 revient au début de la boucle servant à tester les diagrammes de transition.
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.
Un diagramme de transition est implémenté avec la structure switch. Par exemple pour le diagramme reconnaisant deux-points et deux_point egal, l'implémentation sera le suivant:

bool lexical::obtenir2ptsega(terminal &ulex){
bool continuer=true;
bool reussi;
int etat=0;
debutlex=enavant;
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;
continuer=false;
reussi=true;
break;
case 3:
ulex=deuxpoints;
enavant-=taille; //reculer d'un caractère dans le texte d'entrée
reussi=true;
continuer=false;
break;
}
return reussi;
}
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 :
646561
643393
643395

Voici le programme :
terminal.hpp
#ifndef TERMINAL_HPP
#define TERMINAL_HPP

enum terminal {identificateur,nombre,deuxpointsegal,deuxpoints,FDF};

#endif

main.cpp
#include
#include
#include

#include "lexical.hpp"
#include "terminal.hpp"

int main(int argc,char *argv[]){
std::vectorargs;
for(unsigned i=0;i(argc);++i)
args.push_back(argv);
if(argc!=2)
std::cerr<<"manque le fichier"< else{
lexical L(args);
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 "< break;
case deuxpoints:
std::cout<<"ligne "< break;
case deuxpointsegal:
std::cout<<"ligne "< break;
case nombre:
std::cout<<"ligne "< break;
}
}
}

lexical.hpp:
#ifndef LEXICAL_HPP
#define LEXICAL_HPP

#include
#include

#include "terminal.hpp"

class lexical{
public:
lexical(std::string fichierentree);
void analex(terminal &ulex,std::string &lexeme,int &ligne);
private:
std::string texte;
std::string caracterelu;
std::ifstream entree;
size_t enavant,debutlex;
size_t taille;
bool utf8;
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);
void calcul_taille();
std::string carsuiv();
};
#endif


lexical.cpp:
#include
#include

#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(entree)),
std::istreambuf_iterator());
}
}

void lexical::analex(terminal &ulex,std::string &lexeme,int &ligne){
while(true){
if(obtenirblanc(ligne))
;//ignorer le blanc. enavant pointe sur le premier caractère du lexeme suivant
else if(obteniridentificateur(ulex,lexeme))
return;
else if(obtenir2ptsega(ulex))
return;
else if(obtenirnombre(ulex,lexeme))
return;
else if(obtenirFDF(ulex))
return;
else{
std::cerr<<"ligne "< enavant+=taille;//ignorer le caractère hors langage
}
}
}

bool lexical::obtenirblanc(int &ligne){
int etat=0;
bool continuer=true;
bool reussi;
debutlex=enavant;
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:
caracterelu=carsuiv();
if(caracterelu=="\n"){
ligne++;
etat=1;
}
else if(caracterelu==" "||caracterelu=="\t"||caracterelu=="\r")
etat=1;
else
etat=3;
break;
case 3:
enavant-=taille;
continuer=false;
reussi=true;
}
return reussi;
}

bool lexical::obtenirFDF(terminal &ulex){
int etat=0;
bool continuer=true;
bool reussi;
debutlex=enavant;
while(continuer)
switch(etat){
case 0:
caracterelu=carsuiv();
if(caracterelu=='\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;
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;
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;
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;
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 <= (unsigned char)127)
taille=1;
else if((unsigned char)texte >= (unsigned char)0xC2 && (unsigned char)texte <= (unsigned char)0xdf)
taille=2;
else if((unsigned char)texte >= (unsigned char)0xe0 && (unsigned char)texte <= (unsigned char)0xef)
taille=3;
else if((unsigned char)texte >= (unsigned char)0xf0 && (unsigned char)texte <= (unsigned char)0xff)
taille=4;
else{
std::cerr<<"caractère non UTF-8"< enavant++;
return carsuiv();
}
std::string c=texte.substr(enavant,taille);
enavant+=taille;
return c;
}