Mini Projet de Théorie des Langages et Compilation
II1- 2012-2013
L’objectif est d’étendre les connaissances en théorie des langages et des automates afin de pouvoir
décrire des langages de programmation et leur analyse syntaxique en vue de leur compilation. Un
mini compilateur est enfin mis en oeuvre. Ce mini projet est divisé en trois parties :
Partie 1. Développement d’un analyseur lexical
Il est demandé ici de
1) Construire un automate fini qui accepte l’ensemble suivant
des mots (unités lexicales ou jetons, terminaux d’une grammaire) { :, id, =, ==, >=, <=, >,
< , != ;, nb, ,, nbr, +, *, integer, real, bool, start, stop, (, )}
Où id représente les identificateurs alphanumériques qui commencent par un caractère
l(l+c)*), nb représente les nombres entiers c+ et nbr est nombre réel c+.c+
alphabétique (l(l+c
l(l+c
l(l+c
2) Etendre l’automate pour pouvoir retourner à l’état final deux valeurs. La première est
l’unité trouvée selon l’état final atteint et la deuxième est un attribut supplémentaire.
Si l’unité trouvée est un id qui n’est pas un mot clé alors la première valeur retournée est
id et la deuxième est une entrée dans une table contenant les identificateurs.
Si l’unité trouvée est un mot clé (sachant que les mots clés sont : début, fin, program,
var, entier, réel (Il faut sauvegarder quelque part cette liste de mots), alors, les valeurs
Publicité
retournées sont le mot clé et 0.
Si l’unité est nb alors la deuxième valeur est la valeur de ce nombre. L’automate doit
pouvoir sauter les espaces, les retours à la ligne et les tabulations.
3) Implémenter le parcours de cet automate par une fonction (Anal_lex) qui retourne à
chaque fois un enregistrement à deux champs contenant l’unité et un attribut.
Voici un exemple d’automate :
Voici un exemple de résultat retourné par l’analyseur lexical
Voici un exemple de résultat retourné par l’analyseur lexical
NB. Il manque un chemin dans l’automate pour := (l’unité est opaff) devinez
NB. Il manque un chemin dans l’automate pour
:= (l’unité est opaff) devinez !
Partie 2. Développement d’un analyseur syntaxique
Partie 2. Développement d’un analyseur syntaxique
Soit la grammaire G suivante
Soit la grammaire G suivante
G = (V, T, P, R)/
V = {P, S_DCL, DCL, S_INST, INST, Exp, OP}
V = {P, S_DCL, DCL, S_INST, INST, Exp
T = {Program, Start, Var,
:, id, =, ==, <, <=, >, >=, !=, ;, nb, ,, nbr, +, *, integer, real, bool,
integer, real, bool, (, )}
Publicité
R = {
Program id S_DCL
id S_DCL Début S_INST Fin
P fi
S_DCL fi
DCL fi
TYPE fi
S_INST fi
INST fi
Exp fi
OP fi
DCL | DCL S_DCL
DCL | DCL S_DCL
L_id : TYPE;
Var L_id : TYPE;
integer | real |bool
integer
INST | INST S_INST
INST | INST S_INST
id = Exp;
= Exp;
Publicité
id | nb |nbr | Exp + Exp | Exp * Exp | (Exp) |Exp OP Exp
id | nb |nbr | Exp + Exp | Exp * Exp | (Exp)
== | > | < | <= | > | >= |!= }
== | > | < | <= | > | >= |!=
Eliminer la récursivité à gauche et l’ambiguité si elle existe
1) Eliminer la récursivité à
analyseur syntaxique prédictif récursif qui fait appel à la fonction Anal_lex
2) Développer un analyseur syntaxique prédictif récursif qui fait appel à la fonction Anal_lex
analyseur syntaxique prédictif récursif qui fait appel à la fonction Anal_lex
pour analyser un programme existant dans un fichier texte.
pour analyser un programme existant dans un fichier texte.
Exemple de comportement d’un analyseur lexical
Exemple de comportement d’un analyseur lexical
Partie 3. Développement d’un analyseur sémantique
Développement d’un analyseur sémantique
1) Donner une définition dirigée par la syntaxe pour enregistrer le type d’un identificateur
Donner une définition dirigée par la syntaxe pour enregistrer le type d’un identificateur
Donner une définition dirigée par la syntaxe pour enregistrer le type d’un identificateur
dans la table d’identificateurs et de synthétiser le type d’une expression et d’une
dans la table d’identificateurs et de synthétiser le type d’une expression et d’une
dans la table d’identificateurs et de synthétiser le type d’une expression et d’une
Publicité
instruction tout en affichant le cas d’
instruction tout en affichant le cas d’erreurs.
Introduire dans le programme précédent des instructions de contrôle de type.
Introduire dans le programme précédent des instructions de contrôle de type.
2) Introduire dans le programme précédent des instructions de contrôle de type.
Illustrer le programme à travers le programme suivant :
3) Illustrer le programme à travers le programme suivant
Program test
Var a : integer ;
Var b : real;
Var c : bool;
Start
a = 12;
b = 2.34 ;
c = 0;
a = c >b ;
Stop
Sachant que les opérateurs relationnels >, ==, …. Doivent avoir comme arguments deux
entiers ou deux réels.