Tutoriel La création de langages - L'analyse lexicale (notion d'entité lexicale)

[Docteur Lalla]

Introduction

La série d'articles concernant la création de langages de programmation commence dès maintenant par une notion simple. Il s'agit ici d'étudier le lexique du code afin de déterminer précisément la nature des constuctions lexicales du langage et permettra par la suite de décrire une grammaire non contextuelle se basant sur des définitions telles que le "mot-clé" plutôt que la chaîne de caractère "while". Dans cette leçon sera développé le concept d'entité lexicale (souvent appelé token). Nous aborderons d'abord de manière théorique la nécessité d'abstraire le code en le coupant en une liste de tokens au lieu de travailler directement sur la chaîne de caractères qui le défini.
Le but avoué de cet article est de comprendre la structure lexicale d'un code source, peu importe son langage et de savoir créer un générateur d'analyse lexicale (aussi appelé lexer). La majeure partie des exemples donnés seront écrits en langage naturel (en français pour nous) puisque l'analyse lexicale est une étape de la compilation qui fonctionne de manière identique pour les langages de programmation et pour les langues naturelles.
En dernier lieu, le lexer du HKS sera décrit et des ébauches de code seront présentées afin de permettre à chacun d'écrire son propre lexer dans de bonnes conditions.

La notion d'entité lexicale

Pour une langue naturelle telle que le français, il est très simple de décrire de manière formelle le contenu d'une phrase en rangeant méthodiquement les mots employés dans des catégories précises qu'on appelle aussi nature d'un mot. On peut donc découper la phrase suivante selon cette même idée :

Un chat noir regarde par la fenêtre.

article indéfini "un"
nom commun "chat"
adjectif qualificatif de couleur "noir"
verbe "regarder", 3ème personne du singulier, présent de l'indicatif
préposition "par"
article défini "la"
nom commun "fenêtre"
ponctuation "."

On peut noter qu'à chaque constructeur (catégorie), des attributs ont été associés. Dans la majorité des cas, ce fut le mot en lui-même. Le verbe est un parfait contre exemple. Pour la suite des opérations (analyse syntaxique, sémantique...), le temps et la personne utilisée sont des informations qui pourraient être très utiles, il convient donc de les retenir et les noter avec le verbe lui-même. Par ailleurs, la ponctuation n'est jamais oubliée. Une maxime bien connue dit : "Une phrase commence par une majuscule et se termine par un point". La syntaxe du français (exemple utilisé ici) indique donc explicitement qu'un phrase doit se terminer par un point, il faut donc pouvoir vérifier ce détail à tout moment par la suite. C'est la raison pour laquelle la ponctuation est une partie intégrante du lexique.

Pour simplifier les explications, on admettra qu'un signe de ponctuation est un mot à part entière.

Avec l'exemple précédent, on a montré qu'à chaque mot peut être associé une nature et que chaque nature dispose d'un constructeur demandant plus ou moins d'attributs. Une nature de mot est une entité lexicale, soit un token. Pour une langue naturelle, on trouvera typiquement les noms, les adjectifs, les verbes. Alors qu'un langage de programmation verra plutôt un mot-clef, une valeur numérique, une chaîne de caractères... On peut donc dire qu'en dehors des types de tokens qui varient selon le langage décrit, tout les lexiques fonctionnent de la même manière (y compris pour les langues aglutinantes telles que le japonais).

Structure détaillé d'un token

Comme nous l'avons vu précédemment, un token peut utiliser un nombre variable de données et il convient de créer un type de donnée adéquat pour utiliser ce nouvel outil. Nous pouvons tout d'abord couper la nature du token en deux parties bien distinctes : son identité (ou type) et sa valeur. Vous avez certainement remarqué qu'on pouvait appeler tel mot "un verbe", un autre "un nom" et ce, indépendamment de sa valeur. Il s'agissait de la nature du mot, sa catégorie, son type. Il nous faudra alors stocker dans un endroit bien à l'abri le type du token.

Selon le langage que vous utilisez, on utilisera une méthode différente. Typiquement, pour le C (et ses dérivés), l'énumération est de loin le meilleur moyen de stocker le type du token, sachant qu'il existe dans un lexique un nombre fini de types de token.

Ici en C++ :

enum TokenType
{
    NUM, STRING, KWD, IDENT, SYMBOL // ...
};

L'énumération présentée ci-dessus permet de gérer un lexique où on peut trouver des nombres, des chaînes de caractères (typiquement entre guillemets), des mots-clefs, des identifiants (nom de variables en règle générale, ce sont des mots-clefs secondaires qui seront définis par l'utilisateur) et des symboles (souvent la même utilisation que les mots-clefs, mais permettent utilisation propre des caractères spéciaux). Partant de cette énumération, on peut gérer à peu près tout les langages de programmation (certains malins pourraient poser problèmes, bien que je n'ai pas d'exemple concret à proposer).

Pour des langages comme OCaml, utilisera un autre format de donnée. L'idée sera d'associer les valeurs du token à un constructeur.

type Token =
| Num of float (* pas de distinction pour cet exemple, même si, pour ma part je sépare float et int.
| Kwd of string
| Ident of string
| Symbol of string
| String of string
;;

Il convient de préciser que le lexer crée des tokens ayant une sémantique très abstraite. Il ne faudrait en aucun cas créer un type de token par symbole utilisé par le langage. La structure de donnée s'en verrait terriblement alourdie. Il est possible de procéder ainsi, mais le but même du lexer d'abstraire le code en serait dévié et l'analyse syntaxique sera ensuite plus difficile à gérer. Il vaut mieux avoir un nombre de type de tokens réduit et des valeurs très détaillées que l'inverse.

Les valeurs des tokens doivent maintenant être gérées intelligemment. Pour un langage comme OCaml, la question ne se pose pas, la réponse est au-dessus. On a déjà associé des valeurs à des constructeurs. Pour un langage comme le C qui ne propose pas ce genre de types de données, il va nous falloir ruser. Une technique consiste en l'utilisation des unions. Les unions ressemble fortement à une structure à la différence près qu'on ne peut utiliser qu'un seul atribut à la fois.

Voici un exemple typique d'une union symbolisant la valeur d'un token :

union TokenValue
{
    int i;
    float f;
    char* s;

    TokenValue* p; // Si on a besoin de plusieurs attributs, on peut utiliser un tableau de sous-attributs.
};

Nous avons ici réuni 4 types de données en un seul et grâce au tableau p, nous pouvons gérer les tokens utilisant plus d'un attribut qu'importe leur type.
Pour ma part, je suis adepte du C++ et je préfère utiliser une autre version de ce type de donnée :

struct TokenValue // les unions ne prennent pas les classes, alors j'utilise une structure simple
{
    int i;
    float f;
    std::string s;

    std::vector<TokenValue*> p;
};

Une fois les valeurs et types du token définis, il ne nous reste plus alors qu'à stocker les deux informations dans un seul type de donnée : le token. En OCaml, le token est déjà créé, en C il va nous falloir utiliser une bête structure liant un type et une valeur ensemble. Un conseil que je puis donner est de rajouter une troisième information : la ligne à laquelle le token a été trouvé. Par la suite, lors de l'analyse syntaxique puis sémantique du code, dans le but de générer de bons messages d'erreur, il serait utile de connaître la ligne où se trouvait le token incriminé. Il est cent fois plus simple de gérer cette information à partir de l'analyse lexicale (qui a un accès direct au code) qu'ensuite où nous n'utiliserons plus du tout le code.

Nous aurons alors :

struct Token
{
    TokenType type;
    TokenValue value;

    unsigned int line;
};