NF11 - TP2

Analyseur Lexical

Patrick CHABLE et Raphaël MOLL

1. Introduction

L'objectif de cette seconde partie du TP de NF11 est de réaliser un analyseur lexical. Celui-ci est réduit à sa plus simple expression. En effet, bien qu'il ait au préalable été envisagé d'écrire un module relativement intelligent (avec notamment la gestion des scopes), celui présenté ici ne fait que ce que l'on peut attendre d'un analyseur de base: renvoyer des tokens...

2. Structure des données

a. les tokens

Les tokens sont les éléments renvoyés par l'analyseur lexical. C'est à travers eux et, uniquement ainsi, que les couches supérieures du compilateur ont 'une idée' du code du fichier source. Ces tokens doivent donc permettre de décrire précisément ce qui se trouve sous la tête de lecture. Un token a alors la forme suivante:

typedef struct token
{
	BYTE   type;
	double valeur;
} UnToken;

Les champs sont employés comme suit:

Le champ type permet de savoir à quelle sorte de token on a affaire. Ce champ peut prendre les valeurs:

#define C_RESERVE	0
#define C_IDENT	1
#define C_OP_REL	2
#define C_OP_ADD	3
#define C_CHAINE	4
#define C_CARACT	5
#define C_ENTIER	6
#define C_REEL	7
#define C_OP_MUL	8
#define C_METASYMB	9

Le champ valeur permet de désigner avec précision le token. Ainsi, si le token est mot clé, valeur contient le code du mot; si le token est un identificateur alors valeur est identique au numéro de cet identificateur particulier dans la table des symboles. Dans le cas d'entiers ou de réels, valeur contient bien entendu la valeur de ceux-ci convertis au bon type.

Il sera sans doute judicieux de renvoyer avec le token la position de celui-ci dans le texte, travail particulièrement aisé car déjà géré par l'analyseur lexical...

b. la table des symboles

La table des symboles est, comme son nom l'indique, une table contenant des symboles...

Il convient donc de commencer par décrire ce qu'est un symbole. En fait, il s'agit tout simplement d'un identificateur qui est donc caractérisé par une chaîne de caractères (son lexème), son adresse dans la pile de données et de son domaine de visibilité. Tous ces champs se retrouvent bien entendu dans la structure C correspondante:

typedef struct symbole
{
	char *lexeme;
	BYTE scope;
	WORD adresse;
} UnSymbole;

Il faut noter que, pour l'instant, seul le champ lexeme est initialisé. Ni l'allocation de place dans la pile de la MAP, ni la gestion de la visibilité des variables n'est actuellement réalisée: cela fait partie du travail des autres couches (analyseur syntaxique et sémantique).

c. la table des mots clés

Suite à une réflexion antérieure, il a été décidé de ne pas stocker les mots clés dans la même table que les autres identificateurs. Ce détails mis à part, la structure de la table des mots clés est totalement identique.

On remarquera que les mots clés sont actuellement lus dans un fichier texte lors de l'initialisation de l'analyseur.

d. chaînes de caractères

Les chaînes de caractères sont stockées dans un tableau TChaines. Elles forment un ensemble séparé du reste des données car sont des constantes. En fait, lors de la génération de code, elles devront être simplement recopiées au bas de la pile.

3. Programme

a. organisation

Le programme de l'analyseur lexical est entièrement contenu dans le module analex.c. Il existe par ailleurs un fichier de prototypes nommé proto.h (le même que pour la machine à pile, mais complété) ainsi qu'un tout petit module d'appel et de test destiné à être remplacé par l'analyseur lexical.

b. principe de fonctionnement

L'algorithme de recherche d'un token peut se résumer ainsi:

c. gestion des flux

Le problème souvent évoqué concernant la recherche lexicale est le problème du backtrack. Ici, le problème ne porte pas sur un groupe entier de lettres mais seulement sur le dernier caractère, le fonctionnement étant déterministe. Cependant, une routine et une macro ont la charge de la gestion du texte.

La fonction LitCaractère extrait un octet du fichier, effectue le traitement approprié s'il s'agit d'un changement de ligne et renvoie le code. Dans le cas d'une erreur, la faute sera détectée et propagée à travers l'ensemble des routines appelantes ce qui générera jusqu'à l'émission d'une erreur une erreur.
La macro REMET(x) replace le dernier caractère lu dans le tampon d'entrée et réaligne le compteur de colonne (on ne remonte jamais à la ligne du dessus). Cette macro est définie ainsi:

#define REMET(x) \ ungetc(x, FichierSource); \ if (ColonneSource > 1) ColonneSource--;

d. regroupement des caractères

Dans le cas des identificateurs (variables et mots clés), chaque caractère lu est concaténé au précédent jusqu'à rencontrer un blanc (ou un changement de ligne) ou un caractère non alphanumérique.

Le processus est sensiblement le même pour les nombres mais par contre, est effectué au coup par coup pour les autres symboles (>, >=, +, etc.).

e. messages d'erreurs

L'analyseur lexical est assez pauvre du point de vue messages. En effet, il ne peut dire que si tout s'est bien passé ou si une erreur est intervenue. Or, même cette erreur se limite aux deux cas suivants:

Fin de fichier rencontré
Caractère inattendu, rendant la suite difficilement compréhensible.

Seuls ces deux cas sont donc traités.

4. Evolution du programme

Peu de choses restent à apporter. Cependant, la version actuelle de l'analyseur est indépendante du reste du TP. Lors de l'intégration, deux ajouts pourraient se révéler utiles:

Le renvoi d'un token fin de fichier plutôt que l'affichage d'un message d'erreur
Le renvoi systématique avec un token de son emplacement dans le fichier (Ligne, Colonne) afin d'autoriser une gestion plus fine des autres erreurs.
Le renvoi d'un token d'erreur plutôt que l'arrêt du module.

Ces trois modifications sont aisées car déjà prévues, il ne reste plus qu'à le faire.

[webcounter] counts WebCounter.

Last update : 12/07/1999

NF11 - TP2, UTC