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

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

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

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

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, (, )}

R = {

Program id S_DCL

id S_DCL Début S_INST Fin

P ﬁ

S_DCL ﬁ

DCL ﬁ

TYPE ﬁ

S_INST ﬁ

INST ﬁ

Exp ﬁ

OP ﬁ

DCL | DCL S_DCL

L_id : TYPE;

Var L_id : TYPE;

integer | real |bool

integer

INST | INST S_INST

id = Exp;

= Exp;

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.

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

dans la table d’identificateurs et de synthétiser le type d’une expression et d’une

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.

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.