CHENEVOTOT Olivier

DORVEAUX Quentin

GALVANE Quentin

GUILPAIN Thibaud

POTET Germain

UZEL Baptiste

4INFO

Examen de compilation4ème année - A

Questions de coursQuestion 1.1 : Que signifie le "1" dans "grammaire

LL(1)" ? Il suffit de "prélire" une seule unité lexicale pour assurer

l’unicité de la règle de dérivation à utiliser.

Question 1.2 : Supposons qu’un langage de programmation autorise les commentaires imbriqués, comme par exemple /*Ceci est /*un commentaire*/ imbriqué*/.A quelle(s) étape(s) de compilation seront-ils traités ? On justifiera en quelques phrases.

Tout comme les parenthèses, on traitera ces commentaires lors de l’analyse syntaxique, en effet on ne peut pas traiter ici les commentaires lors de l’analyse lexicale.

Questions de coursQuestion 1.3 : Donner le nom de la règle

suivante, dire à quoi elle correspond. La paraphraser exhaustivement en français.

TS E1 : T TS E2 : T … TS En : T_____________________________________________________________

TS [E1;E2;…;En] : liste(T)

Système d’inférence de type pour les Listes.Si selon les hypothèses TS, E1… En sont de type T

alors [E1;E2;…;En] est de type liste de T.

Analyse lexicale et syntaxiqueG : Grammaire d’un langage impératif simplifié

prog → "programme" bloc "fin"bloc → "var" sdec corpssdec → dec "," sdecsdec → decdec → identcorps→ "debut" sinst "fin" sinst → inst ";" sinstsinst → instinst → blocinst → ident "←" expr expr → expr "@" exprexpr → ident ident → <lettre> sident sident→ <lettre> sident sident→ <chiffre> sident sident→ ε

Analyse lexicale et syntaxiqueQuestion 2.1 : Dans la grammaire G, on peut

remarquer l’utilisation de différentes notations pour distinguer plusieurs types de mots. A quoi correspondent ces types de mots ?

Les mots entre guillemets sont des terminaux du langage Les mots entre chevrons sont des classes de caractères Les autres mots correspondent aux non-terminaux

Question 2.2 : Lors de la compilation, est-ce que les mots entre guillemets (double quotes) vont être représentés par des chaînes de caractère ? Justifiez votre réponse.

Non, ils seront représentés par des unité lexicales. En fait, tous les éléments dits terminaux seront représentés par des unités lexicales. Les mots entre guillemets sont ici des mots-clés du langage.

Analyse lexicale et syntaxiqueQuestion 2.3 : Quelles règles correspondent à

l’analyse lexicale ? A l’analyse syntaxique ?Seules les règles sur ident et sident correspondent à

l’analyse lexicale. Toutes les autres correspondent à l’analyse syntaxique.

Question 2.4 : Donner les ensembles VN et VT de la grammaire G, restreintes aux règles de l’analyse syntaxique.

VN = {prog,bloc,sdec,dec,corps,sinst,inst,expr}VT = {"programme", "fin", "var", ",", "debut", ";", "←",

"@",ident}

Analyse lexicale et syntaxiqueQuestion 2.5 : La grammaire restreinte

présentée est-elle simplement LL(1) ? Justifiez votre réponse en une phrase.

Les règles suivantes nous permettent de dire que la grammaire n’est pas LL(1).

sdec → dec "," sdecsdec → dec

En effet, premier(dec "," sdec) = premier(dec). Ainsi, la pré-lecture d’une seule unité lexicale ne

permettra pas de déterminer la règle de dérivation à utiliser.

Analyse lexicale et syntaxique

Question 2.6 : Calculez les ensembles d’items LR(0) demandés pour la grammaire G, et seulement ceux-là.

On augmente la grammaire : prog’ → prog I0 = Fermeture transitive (prog’ → prog)

= {prog’ → .prog, prog → ."programme" bloc "fin"} I2 = Trans(I0,"programme")

= {prog → "programme" .bloc "fin", bloc → ."var" sdec corps}

I4 = Trans(I2,"var")

= {bloc → "var" .sdec corps, sdec → .dec "," sdec, sdec → .dec, dec → .ident}

I6 = Trans(I4, sdec)

= {bloc → "var" sdec .corps, corps → ."debut" sinst "fin" } I10 = Trans(I6, "debut" )

= {corps → "debut" .sinst "fin", sinst → .inst ";" sinst, sinst → .inst, inst→ .bloc, inst→ .ident "←" expr, bloc→ ."var" sdec corps}

Analyse lexicale et syntaxique

I18 = Trans(I14, "←")

= {inst→ ident "←" .expr, expr→ .expr "@" expr, expr→.ident} I20 = Trans(I18, expr)

= {inst→ ident "←" expr ., expr→ expr . "@" expr} I22 = Trans(I20, "@")

= {expr→ expr "@" . expr, expr→ .expr "@" expr, expr→.ident}

I23 = Trans(I22, expr)

= {expr→ expr "@" expr ., expr→ expr . "@" expr} I22 = Trans(I23, "@") [E1;E2;…;En]

= {expr→ expr "@" . expr, expr→ .expr "@" expr, expr→.ident}

Analyse lexicale et syntaxiqueQuestion 2.7 : Donner les ensembles "suivant"

pour les non-terminaux de la grammaire. On ne demande pas de faire un calcul formel.

Suivant(prog) = ØSuivant(bloc) = {"fin", ";"}Suivant(sdec) = {"debut"}Suivant(dec) = {",", "debut"}Suivant(corps) = {"fin", ";"}Suivant(sinst) = {"fin"}Suivant(inst) = {";", "fin"}Suivant(expr) = {";", "fin","@"}Suivant(ident) = {";", "fin","@", "←"}

Analyse lexicale et syntaxiqueQuestion 2.8 : Construire la table SLR à l’aide

des ensembles précédemment calculés. On indiquera toutes les possibilités données par le calcul d’items dans les cases correspondantes.

  programme var debut <- @ ident ; fin   sdec expr

0 d2                    

2   d4                  

4                   6  

6     d10                

10           d14          

14       d18              

18                     20

20         d22   r10 r10      

22                     23

23         d22,r11 r11 r11 r11      

Analyse lexicale et syntaxiqueQuestion 2.9 : Essayer de résoudre les conflits

détectés. Il est interdit de changer la grammaire. On peut toutefois s’appuyer sur des propriétés bien connues, ou sur des propriétés sans conséquences pour le programmeur. Dans ce cas, il faudra bien expliciter ces propriétés. Pour chacun des conflits, bien dire si on peut ou non le résoudre et si oui comment. Justifiez vos réponses.

Pour le @, il y a associativité à droite ; on favorise donc le décalage sur la réduction. On décale d’abord au maximum, puis on réduit, on obtient ainsi une associativité à droite.

Analyse sémantiqueOn se propose, maintenant, d’écrire une

grammaire attribuée qui prend en entrée un programme correct et rend un programme transformé qui est le programme initial dans lequel les variables sont remplacées par un triplet (identificateur, numéro du bloc de déclaration, rang dans ce bloc). La portée des variables est celle utilisée habituellement, une variable est visible dans tout un bloc sauf si une variable de même nom a été déclarée dans un des sous-blocs.

Analyse sémantique Par exemple, le

programme P ci-dessous …

Programmevar a, bdebut

var b, cdebutc <- a @ b ;var c, ddebut c <- c @ bfinfin ;b <- a @ bvar ddebutd <- b @ afin

finfin

devient le programme P’ ci-dessous.

Programmevar (a,1,1), (b,1,2)debut

var (b,2,1), (c,2,2)debut

(c,2,2) <- (a,1,1) @ (b,2,1) ;var (c,3,1), (d,3,2)debut (c,3,1) <- (c,3,1) @ (b,2,1) fin

fin ;(b,1,2) <- (a,1,1) @ (b,1,2)var (d,4,1)debut

(d,4,1) <- (b,1,2) @ (a,1,1)fin

finfin

Analyse sémantiqueG : Grammaire d’un langage impératif simplifié

prog → "programme" bloc "fin"bloc → "var" sdec corpssdec → dec "," sdecsdec → decdec → identcorps→ "debut" sinst "fin" sinst → inst ";" sinstsinst → instinst → blocinst → ident "←" expr expr → expr "@" exprexpr → ident ident → <lettre> sident sident → <lettre> sident sident → <chiffre> sident sident → ε

Analyse sémantiqueQuestion 2.10 : Sur une feuille dédiée, donner l’arbre

syntaxique correspondant au programme P. Cet arbre utilisera la grammaire G, en omettant les terminaux. Par exemple, la règle

Prog → "programme" bloc "fin"ne donnera qu’une seule branche partant de prog et arrivant sur bloc, et la règle

inst → ident "←" expr

ne donnera qu’une branche partant de inst et arrivant sur expr. Dans ce dernier cas, on mettra toute l’instruction sous expr (par exemple b <- a @ b). On mettra également les identificateurs sous dec.

Analyse sémantiqueQuestion 2.11 : Dans un premier temps, on

veut simplement fabriquer une table des symboles qui rassemble tous les triplets possibles. De manière exceptionnelle il est demandé que les compteurs de blocs et de rangs dans les blocs soient gérés par des variables globales. Quelle est la conséquence sur la stratégie de parcours de l’arbre.

Les attributs seraient plus difficiles à gérer car il faudrait un attribut synthétisé et un attribut hérité. La gestion des numéros de blocs deviendrait plus compliquée. La stratégie est de la gauche vers la droite et en profondeur d’abord.

Analyse sémantiqueLes deux compteurs mentionnés ci-dessus sont les

seules variables globales autorisées.La mise à jour des variables globales sera faite à l’aide

d’instructions impératives, mises entre accolades. On considèrera que cette mise à jour se fait avant tout calcul d’attributs. Par exemple dans les calculs suivants, X.a prend la valeur de ma_var après son incrémentation :

{ma_var := ma_var + 1}X.a = ma_var

On introduira les attributs explicitement, en indiquant leur objet, leur type et s’ils sont synthétisés ou hérités. On définira avec soin les structures de données utilisées. Il n’est absolument pas de code Yacc.

Analyse sémantiqueQuestion 2.12 : Construire une grammaire

attribuée GA1 attachée à la grammaire non contextuelle G qui permet de construire cette table des symboles.

Nous utilisons ici deux attributs : tableH et tableS. Le premier attribut est la table synthétisée à partir des déclarations pour un bloc donné, et l'autre table est la table héritée qui permettra de vérifier qu'un ident utilisé dans une expression est bien dans la table des symboles.Les deux attributs "table" sont des tableaux de triplets, et les triplets sont simplement des triplets d'éléments avec le nom de l'ident en premier élément, le bloc de l'ident en second et le rang en troisième élément ; c'est donc un triplet de type (string,int,int).Pour simplifier les expressions suivantes, on considère ici que la fonction conc permet de faire la concaténation de tableaux.

Analyse sémantiqueGA1 :

prog → "programme" bloc "fin" {bloc := 0 ; rang := 0 ;}bloc.tableH = []

bloc → "var" sdec corps {bloc := bloc + 1 ; rang := 0 ;}corps.tableH = conc(bloc.tableH,sdec.tableS)

sdec → dec "," sdec sdec0.tableS = conc(dec.tableS,sdec1.tableS)

sdec → dec sdec.tableS = dec.tableS

dec → ident {rang:= rang +1 ;}dec.tableS = [(ident,bloc,rang)]

corps → "debut" sinst "fin" sins.tableH = corps.tableH

sinst → inst ";" sinst sinst1.tableH = sinst0.tableH

sinst → inst sinst.tableH = inst.tableH

inst → bloc bloc.tableH = inst.tableH

inst → ident "←" expr expr.tableH = inst.tableH

expr → expr "@" expr expr1.tableH = expr0.tableHexpr2.tableH = expr0.tableH

expr → ident

Analyse sémantiqueQuestion 2.13 : Spécifier maintenant une

grammaire GA2, basée sur GA1, qui fabrique le programme transformé. Attention, on n’autorise pas d’autres variables globales que les compteurs de bloc et de rang dans les blocs.

Pour construire le programme P', notre grammaire attribuée GA2 comportera simplement un attribut programme qui sera construit au fur et à mesure. Il faudra tout de même réaliser une fonction get_triplet qui cherchera dans la liste de triplet le triplet correspondant à un ident. Si plusieurs triplets sont trouvés, la fonction rendra celui dont le numéro de bloc est le plus élevé.

Analyse sémantiqueComplément pour GA2 :

prog → "programme" bloc "fin" Prog.prg = "programme" +bloc.prg + "fin\n"

bloc → "var" sdec corps Bloc.prg = "var" + sdec.prg + corps.prg

sdec → dec "," sdec Sdec.prg = dec.prg + "," + sdec.prg

sdec → dec Sdec.prg = dec.prg

dec → ident Dec.prg = “(“ + ident + ”,” + bloc + rang +”)”

corps → "debut" sinst "fin" Corps.prg = "debut" + sinst.prg + "fin"

sinst → inst ";" sinst Sinst.prg = inst.prg + ";" + sinst.prg

sinst → inst Sinst.prg = inst.prg

inst → bloc Inst.prg = bloc.prg

inst → ident "←" expr Inst.prg = get_triplet(ident,inst.tableH) + "←" + expr.prg

expr → expr "@" expr Expr.prg = expr.prg + "@" + expr.prg

expr → ident Expr.prg = get_triplet(ident,expr.tableH)

Analyse sémantiqueQuestion 2.14 : Si on n’avait pas autorisé les

variables globales pour les compteurs, quelles auraient été les conséquences ?

Nous aurions eu à gérer des attributs hérités et synthétisés. La gestion des blocs aurait été un peu plus difficile.

A contrario, si on avait utilisé des variables globales à la questions 2.13 quelles auraient été les conséquences ?

La simple concaténation des chaînes de caractères aurait été difficile à gérer. (Ex : Prog.prg = "programme" +bloc.prg + "fin\n") L'utilisation d'attributs rend la chose beaucoup plus simple.

Analyse sémantiqueQu’en déduisez-vous quant au choix du langage

de programmation des grammaires à attributs GA1 et GA2 ?

Ocaml semble bien convenir.

Question 2.15 : On souhaiterait détecter les variables utilisées non déclarées. Dites en une ou deux phrases ce qu’il faudrait changer dans GA2.

La fonction get_triplet devrait renvoyer une exception lorsque l’on rencontre un attribut non déclaré. La grammaire pourrait alors afficher le triplet (ident,-1,-1).