Mini Projet de Théorie des Langages et Compilation

Ce mini projet de Théorie des Langages et Compilation s'adresse aux étudiants souhaitant approfondir leurs connaissances sur la description, l'analyse et la compilation des langages de programmation. Il couvre la construction d'un analyseur lexical, d'un analyseur syntaxique, puis d'un analyseur sémantique, avec la mise en œuvre progressive d'un mini compilateur.

Développement d’un analyseur lexical

L'objectif de cette première partie est de construire un automate fini capable de reconnaître un ensemble donné d'unités lexicales (jetons) correspondant aux éléments syntaxiques d'un langage simple. Ces jetons incluent notamment :

• Les symboles : :, =, ==, >=, <=, >, <, !=, ;, ,, +, *, (, )
• Les mots clés : integer, real, bool, start, stop
• Les identificateurs (id) : chaînes alphanumériques commençant par une lettre (l(l+c)*)
• Les nombres entiers (nb) : séquences de chiffres (c+)
• Les nombres réels (nbr) : séquences de chiffres avec un point décimal (c+.c+)

L'automate doit également gérer les espaces, retours à la ligne et tabulations en les ignorant.

Extension de l’automate

L'automate doit être étendu pour retourner, à chaque état final, deux valeurs :

• La première valeur est l'unité lexicale reconnue (par exemple, id, mot clé, nb, etc.).
• La deuxième valeur est un attribut supplémentaire :

• Si l'unité est un identificateur (id) qui n'est pas un mot clé, la deuxième valeur est une entrée dans une table des identificateurs.
• Si l'unité est un mot clé (parmi la liste sauvegardée : début, fin, program, var, entier, réel), la deuxième valeur est 0.
• Si l'unité est un nombre entier (nb), la deuxième valeur est la valeur numérique correspondante.

Implémentation de la fonction Anal_lex

La fonction Anal_lex parcourt l'automate et retourne à chaque appel un enregistrement à deux champs : l'unité lexicale et son attribut.

Remarque : L'automate présenté dans le projet ne comporte pas encore de chemin pour reconnaître l'opérateur d'affectation composé := (unité opaff), ce qui doit être corrigé.

Développement d’un analyseur syntaxique

La deuxième partie consiste à construire un analyseur syntaxique basé sur la grammaire G suivante :

G = (V, T, P, R)
V = {P, S_DCL, DCL, S_INST, INST, Exp, OP}
T = {Program, Start, Var, :, id, =, ==, <, <=, >, >=, !=, ;, nb, ,, nbr, +, *, integer, real, bool, (, )}

Les règles de production R sont :

Program → id S_DCL
S_DCL → DCL | DCL S_DCL
DCL → Var L_id : TYPE ;
L_id → id | id , L_id
TYPE → integer | real | bool
S_INST → INST | INST S_INST
INST → id = Exp ;
Exp → id | nb | nbr | Exp + Exp | Exp * Exp | ( Exp ) | Exp OP Exp
OP → == | > | < | <= | >= | !=

Élimination de la récursivité à gauche et ambiguïtés

Avant d'implémenter l'analyseur syntaxique, il faut éliminer la récursivité à gauche dans la grammaire et résoudre toute ambiguïté éventuelle afin de pouvoir construire un analyseur syntaxique prédictif récursif.

Implémentation de l’analyseur syntaxique prédictif récursif

L'analyseur syntaxique doit être développé sous forme de fonctions récursives qui appellent la fonction Anal_lex pour obtenir les unités lexicales successives. Il doit analyser un programme donné dans un fichier texte selon la grammaire corrigée.

Développement d’un analyseur sémantique

La troisième partie porte sur l'analyse sémantique, qui consiste à vérifier les types et la cohérence des expressions et instructions.

Définition dirigée par la syntaxe

Il faut définir des règles dirigées par la syntaxe pour :

• Enregistrer le type d'un identificateur dans la table des symboles.
• Synthétiser le type d'une expression et d'une instruction.
• Afficher les erreurs de type éventuelles.

Contrôle de type

Des instructions de contrôle de type doivent être introduites dans le programme précédent afin de vérifier la validité des opérations.

Exemple de programme à analyser

Program test

Var a : integer ;
Var b : real;
Var c : bool;

Start

a = 12;
b = 2.34 ;
c = 0;
a = c > b ;

Stop

Note : Les opérateurs relationnels tels que >, ==, etc., doivent avoir comme arguments deux entiers ou deux réels. L'exemple illustre une erreur de type dans l'affectation a = c > b car c est booléen et b est réel.

Glossaire des termes clés

• Analyseur lexical (lexer) : composant qui transforme une chaîne de caractères en une suite d'unités lexicales ou jetons.
• Automate fini : modèle mathématique utilisé pour reconnaître des langages réguliers, ici pour identifier les jetons.
• Jeton (unité lexicale) : élément atomique reconnu par l'analyseur lexical, comme un mot clé, un identificateur ou un opérateur.
• Identificateur (id) : chaîne alphanumérique commençant par une lettre, représentant une variable ou un nom.
• Nombre entier (nb) : séquence de chiffres représentant un entier.
• Nombre réel (nbr) : nombre avec partie décimale, représenté par c+.c+.
• Analyseur syntaxique (parser) : composant qui vérifie la structure grammaticale d'une suite de jetons selon une grammaire.
• Grammaire : ensemble de règles définissant la syntaxe d'un langage.
• Récursivité à gauche : forme de récursivité dans une grammaire qui peut poser problème pour certains analyseurs syntaxiques.
• Analyseur syntaxique prédictif récursif : analyseur qui utilise la récursivité et la prédiction pour analyser un programme.
• Analyseur sémantique : composant qui vérifie la cohérence des types et la validité des opérations dans un programme.
• Table des symboles : structure de données qui stocke les informations sur les identificateurs, notamment leurs types.

Points clés à retenir

• La construction d’un automate fini est essentielle pour reconnaître les unités lexicales d’un langage.
• L’analyseur lexical doit retourner à la fois l’unité lexicale et un attribut utile pour la suite de la compilation.
• La grammaire doit être adaptée (récursivité à gauche éliminée) pour permettre un analyseur syntaxique prédictif récursif.
• L’analyseur syntaxique s’appuie sur l’analyseur lexical pour analyser la structure du programme.
• L’analyse sémantique vérifie la cohérence des types et signale les erreurs liées aux opérations incompatibles.
• La table des symboles est indispensable pour gérer les identificateurs et leurs types.
• Les opérateurs relationnels doivent être appliqués à des opérandes de types compatibles (entier ou réel).