Analyseur lexicale en langage C

Dans cet article on va réaliser un analyseur lexicale étape par étape.
Vous trouvez le code source complet dans ce repository sur gihub : Analyseur lexicale

Important : n'oubliez pas d'éditer le lien vers le code source dans const char* fileName (analyseur.cpp)

Définition d'un analyseur lexicale:

Un analyseur lexicale est un programme qui prend un code source en entrée et retourne une séquence de jetons (tokens) en sortie.

Exemple:
Considérons le code source suivant:

CODE:

int x, y, z;
x = -2;
y = 8;
z = 3.1415;
String msg = "hello world";
if(x >= 0){
	print("a message...");
}else{
	print(msg);
}

La sortie de l'analyseur lexicale sera :

CODE:

INT_TOKEN IDF_TOKEN COMMA_TOKEN IDF_TOKEN COMMA_TOKEN IDF_TOKEN SEMICOLON_TOKEN
IDF_TOKEN ASSIGNMENT_TOKEN NUMBER_TOKEN SEMICOLON_TOKEN
IDF_TOKEN ASSIGNMENT_TOKEN NUMBER_TOKEN SEMICOLON_TOKEN
IDF_TOKEN ASSIGNMENT_TOKEN NUMBER_TOKEN SEMICOLON_TOKEN
STRING_TOKEN IDF_TOKEN ASSIGNMENT_TOKEN VARCHAR_TOKEN SEMICOLON_TOKEN
IF_TOKEN OPEN_PARENS_TOKEN IDF_TOKEN OP_GE_TOKEN NUMBER_TOKEN CLOSE_PARENS_TOKEN OPEN_BRACE_TOKEN
IDF_TOKEN OPEN_PARENS_TOKEN VARCHAR_TOKEN CLOSE_PARENS_TOKEN SEMICOLON_TOKEN
CLOSE_BRACE_TOKEN ELSE_TOKEN OPEN_BRACE_TOKEN
IDF_TOKEN OPEN_PARENS_TOKEN IDF_TOKEN CLOSE_PARENS_TOKEN SEMICOLON_TOKEN
CLOSE_BRACE_TOKEN

L'analyseur lexicale a changé int par INT_TOKEN, x par IDF_TOKEN (identificateur), ...
L'analyseur lexicale tout simplement transforme un code source en une version lisible par l'analyseur syntaxique.
Pour faire cette transformation, on distingue les différents types de jetons (tokens) :

Les mots-clés: ce sont les mots réservés par le langage, exemple les mots clés du langage C : if, else, while, typedef, ...
Les identificateurs: toute chaine de caractères de la forme : Alphabétique (Alphabétique | numérique)*
Ou avec les expressions régulières: [a-zA-Z_][a-zA-Z0-9_]*
Les nombres: on distingue les nombres entiers : (+|-|ε) Numérique+, ou les nombres flottants : (+|-|ε) Numérique+.Numérique+
Expression régulière d'un nombre entier: (\+|\-)?[0-9]+
Expression régulière d'un nombre flottant: (\+|\-)?[0-9]+\.[0-9]+
Les opérateurs: les symboles : >, <, +, -, =, >=, <=, ...
Les textes: ce sont les textes compris entre " ou '

Les tokens de type identificateurs, nombres et textes nécessitent qu'on sauvegarde leurs valeurs.

Les outils du travail:
On va utiliser le langage C pour écrire notre analyseur lexicale, une connaissance moyenne de ce langage est requise.

Pour éditer notre code, on va utiliser Le logiciel Dev-C++.

Réalisation de l'analyseur lexicale:
Pour commencer notre analyseur, on crée un dossier analyseur, dans ce dossier on met les fichiers :

analyseur.cpp : c'est le fichier qui contient la fonction principale int main().
header.h : Contient la définition du programme qui va être analyser.
functions.c : contient les fonctions nécessaires pour pour faire l'analyse lexicale.
functions.h : contient le header du fichier functions.c.
myfile.lag : contient le code source du programme à analyser.

Dans le fichier analyseur.cpp on met Le code suivant:

CODE:

#include<stdio.h>
#include<stdlib.h>

// Lire le fichier source
const char *fileName = "C:\\Users\\LAGRIDA\\Desktop\\analyseur\\myfile.lag";
FILE *fileSrc = fopen(fileName, "r");

#include "functions.c"

int main(){
	if(fileSrc == NULL){
		printf("Erreur d'ouverture du fichier source..\n\n");
		exit(0);
	}
	system("pause");
	return 0;
}

Remarque : N'oubliez pas d'éditer const char* fileName suivant le lien vers le code source.

Dans le fichier functions.h on met Le code suivant:

CODE:

#include "header.h"

Dans le fichier functions.c on met Le code suivant:

CODE:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define IDFSIZE 50 // taille maximal d'un identificateur
#define NUMBERSIZE 32 // taille maximal d'un nombre
#define VARCHARSIZE 225 // taille maximal d'une variable texte

#include "functions.h"

Définition du langage à analyser:
Maintenant, on va définir notre langage qui va être analyser par notre analyseur lexicale.

Dans header.h ajoutez le code suivant :

CODE:

// Type booléen
typedef enum{FALSE, TRUE} boolean;
// Les mots clés de notre langage
const char* keyword_token[] = {"if", "else", "for", "while", "int", "float", "string"};
// Les symboles de notre langage
// "+", "-", "/", "*", ",", ";", "{", "}", "(", ")", "=", ">", "==", ">=", "<="
const char symbole_token[] = {'*', ',', ';', '{', '}', '(', ')'};
// Le monde des tokens
typedef enum{
	// keywrods tokens
	IF_TOKEN, ELSE_TOKEN, FOR_TOKEN, WHILE_TOKEN, INT_TOKEN, FLOAT_TOKEN, STRING_TOKEN,
	// Symbole tokens
	PLUS_TOKEN, MINUS_TOKEN, DIV_TOKEN, STAR_TOKEN, COMMA_TOKEN, SEMICOLON_TOKEN,
	OPEN_BRACE_TOKEN, CLOSE_BRACE_TOKEN, OPEN_PARENS_TOKEN, CLOSE_PARENS_TOKEN,
	ASSIGNMENT_TOKEN, GT_TOKEN, LT_TOKEN, OP_EQ_TOKEN, OP_GE_TOKEN, OP_LE_TOKEN,
	// Other tokens
	IDF_TOKEN,
	VARCHAR_TOKEN,
	NUMBER_TOKEN,
	EOF_TOKEN,
	ERROR_TOKEN
} nameToken;

Remarque: Il faut garder le même ordre des mots clés dans *keyword_token[] avec les éléments de l’énumération nameToken (aussi pour la table des symboles simples symbole_token[]).

CODE:

"if" ----------> IF_TOKEN
"else" --------> ELSE_TOKEN
...
"string" ------> STRING_TOKEN

'*' -----------> STAR_TOKEN
',' -----------> COMMA_TOKEN
...
')' -----------> CLOSE_PARENS_TOKEN

Remarque: Les constantes char* keyword_token[] et char symbole_token[] contiennent les mots clés et les symboles du langage à analyser, il faut les modifier suivant le langage désiré.
On distingue les symboles simples qui demandent seulement une simple reconnaissances, exemple: Les symboles dans la constante char symbole_token[], et les symboles qui peuvent être liés avec d'autres tokens, Exemple: '+' et '-' sont liés avec les nombres, '/' est lié avec les commentaires. Ou les symboles qui contiennent plus de deux caractère (symboles complexes), exemple: '=' avec '==', '>' avec '>=', '<' avec '<='.

Maintenant on va définir les structures que nous utiliserons pour définir les tokens.

Dans header.h ajoutez le code suivant :

CODE:

// structure d'un identificateur
typedef struct{
	char* name;
}idfToken;

// structure d'une variable texte
typedef struct{
	char c; // " ou '
	char* value;
}varcharToken;

// structure d'un nombre
typedef struct{
	boolean isInt; // entier ou flottant
	union{
		int n;
		float x;
	}value;
}numberToken;

// La structure d'un token
typedef struct{
	nameToken name; // Le nom du token
	union{
		idfToken idf; // les informations de l'identificateur (si le token est IDF_TOKEN)
		numberToken number; // les informations du nombre (si le token est NUMBER_TOKEN)
		varcharToken varchar; // les informations du texte (si le token est VARCHAR_TOKEN)
	}properties;
} token;

La reconnaissance des tokens :
Aprés la définition de notre langage et la structuration des tokens, on passe à la construction de notre analyseur lexicale, notre but est de construire la Fonction token getToken(); qui, à chaque appelle, donne le token suivant, exemple:
Si on reprend le code source du premier exemple, l'appelle de la fonction getToken() donne :

CODE:

getToken().name; // résultat : INT_TOKEN
getToken().name; // résultat : IDF_TOKEN
getToken().name; // résultat : COMMA_TOKEN
.....

Pour construire la fonction getToken(), nous avons besoin de plusieurs fonctions qui nous aide à savoir la nature d'un caractère.
Dans functions.c Ajoutez le code suivant:

CODE:

// le nombre de cases de la table keyword_token
int keyword_token_size = sizeof(keyword_token)/sizeof(keyword_token[0]);

// le nombre de cases de la table symbole_token
int symbole_token_size = sizeof(symbole_token)/sizeof(symbole_token[0]);

//----- Les prototypes des fonctions :
boolean isAlphabetic(char c);
boolean isNumeric(char c);
int caractereSpecial(char c);

//----- Les fonctions -------------- :

// savoir si un caractère est une alphabet
boolean isAlphabetic(char c){
	if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_'){
		return TRUE;
	}
	return FALSE;
}
// savoir si un caractère est un chiffre
boolean isNumeric(char c){
	if(c >= '0' && c <= '9'){
		return TRUE;
	}
	return FALSE;
}
// savoir si un caractère est un symbole simple
// retourner son numéro dans nameToken si caractère est un symbole simple, -1 sinon
int caractereSpecial(char c){
	int i = 0;
	int symbole = (int) STAR_TOKEN; // STAR_TOKEN est le premier symbole simple dans nameToken
	while(i < symbole_token_size){
		if(c == symbole_token[i]){
			symbole = symbole + i;
			return symbole;
		}
		i++;
	}
	return -1;
}

Dans la fonction getToken() on va lire le code source d'après le fichier myfile.lag caractère par caractère. Et le type de caractère obtenue nous donne le traitement nécessaire pour la reconnaissance des tokens.
Dans functions.c Ajoutez le corps de la fonction getToken() :

CODE:

token getToken(){
	// Lire le caractère suivant
	char character = fgetc(fileSrc);
	token A;
	int i = 0;
	// Eliminer les blancs
	if(character == ' ' || character == '\t' || character == '\n'){
		return getToken();
	}
	// Reconnaissance des mots-clé et des identificateurs
	else if(isAlphabetic(character) == TRUE){
		// code ici
	}
	// Reconnaissance des nombres
	else if(isNumeric(character) == TRUE){
		// code ici
	}
	// Reconnaissance des variables textes
	else if(character == '"' || character == '\''){
		// code ici
	}
	// Elimination des commentaires
	else if(character == '/'){
		// code ici
	}
	// Reconaissance des symboles simples
	else if((i = caractereSpecial(character)) > -1){
		// code ici
	}
	/*
	Reconnaissance des symboles complexes
	*/
	// La fin de la lecture
	else if(character == EOF){
		A.name = EOF_TOKEN;
		return A;
	}
	// Si on rencontre d'autre caractères non analysés
	else{
		A.name = ERROR_TOKEN;
		return A;
	}
}

Reconnaissance des mots-clé et des identificateurs :
Dans cette étape on va récupérer tout mot de la forme [a-zA-Z_][a-zA-Z0-9_]* puis vérifier si c'est un mot-clé ou un identificateur.

Si le curseur de lecture pointe sur une alphabet ('a', 'b' ,..., 'z', 'A', 'B',...'Z', '_') on va lire tout le mot pour obtenir le mot-clé ou l'identificateur.

CODE:

	// Reconnaissance des mots-clé et des identificateurs
	else if(isAlphabetic(character) == TRUE){
		// Allocation de la mémoire pour sauvegarder le mot
		A.properties.idf.name = (char *)malloc(IDFSIZE*sizeof(char));
		// Lire tout le mot
		do{
			A.properties.idf.name[i] = character;
			// Lire le caractère suivant
			character = fgetc(fileSrc);
			i++;
		}while(isAlphabetic(character) == TRUE || isNumeric(character) == TRUE);
		A.properties.idf.name[i] = '\0'; // il faut poser \0 à la fin du mot
		/*
		La fonction do..while sort Lorsqu'elle lit un non alpha-numérique caractère
		il faut retourner le curseur en arrière par la fonction ungetc()
		pour que ce caractère ne soit perdu, et il va être analyser
		dans le prochain appelle de la fonction getToken()
		*/
		ungetc(character, fileSrc);
		i = 0;
		// vérifier si lo mot obtenue est un mot-clé :
		while(i < keyword_token_size){
			if(strcmp(A.properties.idf.name, keyword_token[i]) == 0){ // Le mot est un mot-clé
				// Le nom token c'est (nameToken) i
				A.name = (nameToken) i;
				// Libérer la case mémoire A.properties.idf.name
				// On a besoin du nom de token seulement dans ce cas (et pas sa valeur)
				free(A.properties.idf.name);
				return A; // retourner le token
			}
			i++;
		}
		// Si on arrive à cette étape, le mot n'est pas mot-clé
		// Donc c'est un identificateur, et son nom est stocké dans A.properties.idf.name
		A.name = IDF_TOKEN;
		return A; // retourner le token
	}

Reconnaissance des nombres:
Dans cette étape on va récupérer les nombres (entiers : (\+|\-)?[0-9]+ ou flottants : (\+|\-)?[0-9]+\.[0-9]+).
Si le curseur de lecture pointe sur un chiffre ('0', '1' ,..., '9') on va lire tout le nombre.

un nombre peut commencer par un '+' ou un '-', donc une situation dans le code source comme : "- 3.14" doit être traduit par NUMBER_TOKEN.
Une autre situation peut être ambigu : "5 - 3.14", ce code doit être traduit par : NUMBER_TOKEN MINUS_TOKEN NUMBER_TOKEN.

Pour enlever cette ambiguïté, on va créer une variable globale boolean isNumber = FALSE; cette variable sera modifier par TRUE si on arrive à un NUMBER_TOKEN, comme ça on se situe bien si le token suivant sera '+' ou un '-'.

Premièrement on doit ajouter la fonction numberToken getNumber(char digit, boolean isNegative); qui récupère tout le nombre.

Dans functions.c Ajoutons cette fonction:

CODE:

numberToken getNumber(char digit, boolean isNegative){
	int i=0;
	// variable qui indique s'il s'agit d'un entier ou un flottant
	boolean isInt = TRUE;
	// Allocation de la mémoire
	char* memory = (char *)malloc(NUMBERSIZE*sizeof(char));
	numberToken A;
	// Lire tout le chiffre
	do{
		memory[i] = digit;
		digit = fgetc(fileSrc); // caractère suivant
		i++;
		if(digit == '.'){ // si on arrive à une virgule (un nombre flottant)
			isInt = FALSE;
			memory[i] = '.';
			digit = fgetc(fileSrc);
			i++;
		}
	}while(isNumeric(digit) == TRUE);
	memory[i] = '\0';
	/*
		on sort de do..while Lorsqu'on lit un caractère non numérique
		il faut retourner le curseur pour que cette caractère ne soit perdu
	*/
	ungetc(digit, fileSrc);
	A.isInt = isInt;
	if(isInt == TRUE){ // un nombre entier
		// transformer le nombre dans la chaine de caractère memory en int et le stoker dans A.value.n
		A.value.n = atoi(memory);
		if(isNegative == TRUE){
			A.value.n = - A.value.n;
		}
	}else{ // un nombre flottant
		// transformer le nombre dans la chaine de caractère memory en float et le stoker dans A.value.x
		A.value.x = atof(memory);
		if(isNegative == TRUE){
			A.value.x = - A.value.x;
		}
	}
	return A;
}

Dans functions.c Ajoutez en haut du fichier la variable global isNumber :

CODE:

boolean isNumber = FALSE;

Dans la fonctions getToken() ajoutez en haut le code suivant :

CODE:

boolean previousIsNumer = isNumber;
isNumber = FALSE;

Maintenant on peut faire la reconaissance des nombres :

CODE:

	// Reconnaissance des nombres
	else if(isNumeric(character) == TRUE){
		// le token est un nombre ==> isNumber = TRUE;
		isNumber = TRUE;
		A.name = NUMBER_TOKEN;
		// récupérer le nombre et le stocker dans A.properties.number
		A.properties.number = getNumber(character, FALSE);
		return A;
	}
	else if(character == '+' || character == '-'){
		nameToken symboleToken = (character == '+' ? PLUS_TOKEN : MINUS_TOKEN);
		boolean isNegative = (character == '-' ? TRUE : FALSE);
		// Eliminer les espaces
		do{
			character = fgetc(fileSrc);
		}while(character == ' ');
		// Si le caractère suivant de +/- est un chiffre
		if(isNumeric(character) == TRUE){
			if(previousIsNumer == TRUE){
				// le token précédant est un nombre, exemple de cette situation : "5 - 3"
				ungetc(character, fileSrc); // retourner le curseur en arrière
				A.name = symboleToken; // token : PLUS_TOKEN ou MINUS_TOKEN
				return A;
			}else{
				// le token précédant n'est pas un nombre, exemple cette situation : "= - 3"
				isNumber = TRUE; // token actuel est un nombre
				A.name = NUMBER_TOKEN;
				A.properties.number = getNumber(character, isNegative);
				return A;
			}
		}else{ // Le caractère suivant de +/- n'est pas un chiffre
			ungetc(character, fileSrc); // retourner le curseur en arrière
			A.name = symboleToken;
			return A;
		}
	}

Reconnaissance des variables textes :
Les variables textes sont les textes comprisent entre " ou ' On peut avoir dans une variable texte \" ou \'
exemple : "hello world \" exemple" il faut prendre cela en considèration dans notre code.

CODE:

	// Reconnaissance des variables textes
	else if(character == '"' || character == '\''){
		i = 0;
		// type de délimiteure de texte : ' ou "
		char d = character;
		// caractère precédant de character
		// valeur initiale : tout caractère différent de '\'
		char previousC = ' ';
		// Lire le caractère suivant
		character = fgetc(fileSrc);
		// Allocation mémoire pour sauvegarder le texte
		A.properties.varchar.value = (char *)malloc(VARCHARSIZE*sizeof(char));
		// Lire le texte
		while((character != d || (character == d && previousC == '\\')) && character != EOF){
			A.properties.varchar.value[i] = character;
			character = fgetc(fileSrc); // Lire le caractère suivant
			i++;
			previousC = A.properties.varchar.value[i-1];
		}
		A.properties.varchar.value[i] = '\0';
		A.name = VARCHAR_TOKEN;
		A.properties.varchar.c = d;
		return A;
	}

Elimination des commentaires :
Les commentaires sont des lignes ignorées par le compilateur, déstinées à la clarifications des instructions, on distingue :

Les commentaires lignes : ils commencent par // et terminent par retour à la ligne \n
Les commentaires bloques : ils commencent par /* et terminent par */

CODE:

	// Elimination des commentaires
	else if(character == '/'){
		// Lire le caractère suivant
		character = fgetc(fileSrc);
		if(character == '/'){ // un commentaire ligne
			// dépasser tous les caractères jusqu'on arrive à \n
			do{
				character = fgetc(fileSrc);
			}while(character != '\n' && character != EOF);
			return getToken(); // rappeler la fonction
		}
		else if(character == '*'){ // un commentaire bloque
			// dépasser tous les caractères jusqu'on arrive à */
			do{
				character = fgetc(fileSrc);
			}while(character != '*');
			// Lire le caractère suivant
			character = fgetc(fileSrc);
			if(character == '/'){ // Fin du commentaire bloque
				return getToken(); // rappeler la fonction
			}
		}
		else{ // Le caractère suivant de / n'est ni / ni *
			// symbole division
			A.name = DIV_TOKEN;
			ungetc(character, fileSrc);
			return A;
		}
	}

Reconnaissance des symboles simples :
Les symboles simples sont les caractères spéciales qui demandent une simple reconnaissance, ils sont présentés dans la table const char symbole_token[] dans le fichier header.h.

CODE:

	// Reconaissance des symoboles simples
	else if((i = caractereSpecial(character)) > -1){
		A.name = (nameToken) i;
		return A;
	}

Reconaissance des symboles composés :
Les symboles composés sont les symboles qui se composent plus de deux caractères, ils nécessitent une reconnaissance caractère par caractère, exemple : '==' ou '=<' ...

CODE:

	// Reconnaissance de =, ==
	else if(character == '='){
		// Lire le caractère suivant
		character = fgetc(fileSrc);
		if(character == '='){ // On a le symbole ==
			A.name = OP_EQ_TOKEN;
			return A;
		}else{ // On a le symbole =
			A.name = ASSIGNMENT_TOKEN;
			ungetc(character, fileSrc);
			return A;
		}
	}
	// Reconnaissance de >, >=
	else if(character == '>'){
		// Lire le caractère suivant
		character = fgetc(fileSrc);
		if(character == '='){ // On a le symbole >=
			A.name = OP_GE_TOKEN;
			return A;
		}else{ // On a le symbole >
			A.name = GT_TOKEN;
			ungetc(character, fileSrc);
			return A;
		}
	}
	// Reconnaissance de <, <=
	else if(character == '<'){
		// Lire le caractère suivant
		character = fgetc(fileSrc);
		if(character == '='){ // On a le symbole <=
			A.name = OP_LE_TOKEN;
			return A;
		}else{ // On a le symbole <
			A.name = LT_TOKEN;
			ungetc(character, fileSrc);
			return A;
		}
	}

Analyseur lexicale :
On a arrivé à la fin de notre analyseur, tu peux télécharger l'analyseur complet sur le lien : Analyseur_lexicale.
Pour voir le fonctionnement de notre analyseur, mettez le code suivant dans le fichier myfile.lag :

CODE:

if else +32 "hello world"

Et dans la fonction main() du fichier analyseur.ccp :

CODE:

token currentToken = getToken();
printf("token : %d\n", (int) currentToken.name);
currentToken = getToken();
printf("token : %d\n", (int) currentToken.name);
currentToken = getToken();
printf("token : %d\n", (int) currentToken.name);
currentToken = getToken();
printf("token : %d\n", (int) currentToken.name);

Aprés l'éxecution on aura le résultat suivant :

CODE:

token : 0
token : 1
token : 25
token : 24

Les nombres affichés sont les indices de ces tokens dans l’énumération nameToken

Pour afficher les tokens sous forme lisible, ajoutez la table suivante dans le fichier header.h :

CODE:

const char* tokens[] = {"IF_TOKEN", "ELSE_TOKEN", "FOR_TOKEN", "WHILE_TOKEN", "INT_TOKEN", "FLOAT_TOKEN", "STRING_TOKEN",
                        "PLUS_TOKEN", "MINUS_TOKEN", "DIV_TOKEN", "STAR_TOKEN", "COMMA_TOKEN", "SEMICOLON_TOKEN", "OPEN_BRACE_TOKEN",
                        "CLOSE_BRACE_TOKEN", "OPEN_PARENS_TOKEN", "CLOSE_PARENS_TOKEN", "ASSIGNMENT_TOKEN", "GT_TOKEN", "LT_TOKEN",
                        "OP_EQ_TOKEN", "OP_GE_TOKEN", "OP_LE_TOKEN",
                        "IDF_TOKEN",
                        "VARCHAR_TOKEN",
                        "NUMBER_TOKEN",
                        "EOF_TOKEN",
                        "ERROR_TOKEN"};

Dans la fonction main() du fichier analyseur.ccp on va mettre :

CODE:

    token currentToken = getToken();
    printf("token : %s\n", tokens[(int) currentToken.name]);
    currentToken = getToken();
    printf("token : %s\n", tokens[(int) currentToken.name]);
    currentToken = getToken();
    printf("token : %s\n", tokens[(int) currentToken.name]);
    currentToken = getToken();
    printf("token : %s\n", tokens[(int) currentToken.name]);

Aprés l'éxecution on aura le résultat suivant :

CODE:

token : IF_TOKEN
token : ELSE_TOKEN
token : NUMBER_TOKEN
token : VARCHAR_TOKEN

D'une façon générale pour afficher tous les tokens du fichier source myfile.lag :

CODE:

	int k;
	token currentToken = getToken();
	do{
		k = (int) currentToken.name;
		printf("%s ", tokens[k]);
		currentToken = getToken(); 
	}while(currentToken.name != EOF_TOKEN);

Après la vérification de tokens, supprimez la table const char* tokens[] et notre code est Prêt pour L'analyse syntaxique.