Examen de majeure 2
Langages et compilation
(Durée 2h)

29 mars 1999

On attachera une importance particulière à la clarté, à la précision et la la concision de la rédaction.

1	Expansion en ligne

L'expansion en ligne (inlining) consiste à remplacer dans le source des appels à des fonctions par le corps de ces fonctions. On considère la fonction carré suivante:

function carré (n : integer) : integer; begin carré := n * n end;

1.1 Donner un code SPIM possible pour la fonction carré en prenant comme registres conventionnels a0, a1, a2, et a3 pour les arguments et v0 pour le résultat.

carre: mul $v0, $a0, $a0 # v0 <- n n j $ra # Retour à l'appelant

Réponse

1.2 On considère la fonction cube suivante:

function cube (n : integer) : integer; begin cube := carré(n) * n end;

  a)   Donner un code SPIM possible pour cette fonction (en utilisant les mêmes conventions d'appel), sans faire d'hypothèse sur le code de la fonction carré (on indiquera brièvement en commentaires les opérations effectuées par chaque instruction).
Réponse

  b)   Donner le code source résultant de l'expansion en ligne de la fonction carré dans la fonction cube.
Réponse

  c)   Donner un code SPIM pour le code source résultant de l'expansion en ligne.
Réponse

1.6   On s'appuyera sur l'exemple ci-dessus.

  a)   Quel sont les différentes sources de gain de l'expansion en ligne?
Réponse

  b)   Expliquer comment une partie des gains de l'expansion en ligne, dits indirects, peuvent se retrouver simplement sans effectuer l'expansion en ligne.
Réponse

  c)   Quel est le coût de l'expansion en ligne? Quel compromis proposer?
Réponse

1.10   L'expansion en ligne naïve ne fonctionne pas correctement. Considérons la fonction:

function quatre (n : integer) : integer; begin quatre := carré (carré (n*n)) end;

  a)   Expliquer sur cet exemple un problème lié à l'expansion naïve.
Réponse

  b)   En déduire un exemple montrant que l'expansion naïve peut aussi être incorrecte.
Réponse

  c)   Donner une meilleure version de l'expansion de carré dans la fonction quatre qui suggère un schéma général et correct.
Réponse

2	Langage de parenthèses

Sur l'alphabet S = {g, d} on considère la grammaire G₁ (resp. G₂) définie par l'axiome S₁ (resp. S₂) et les règles de production ci-dessous à gauche (resp. à droite):

S₁ ® E

E ® g E d

E ® E E

E ® e

S₂ ® E

E ® g E d E

E ® e

2.1

  a)   Donner deux dérivations de ggdgdd l'une dans G₁ et l'autre dans G₂.
Réponse

  b)   Les grammaires G₁ et G₂ sont-elles ambigües? LL(1) ? LR(1) ?
Réponse

2.4   La grammaire G₁ définit le langage des parenthèses L. Peut-on reconnaître L par une expression régulière ? par un lexeur ? (Justifier très brièvement chaque réponse).

Réponse

2.5   Montrer que le langage reconnu par G₂ est un sous ensemble de L.
Réponse

2.6   On peut représenter les arbres syntaxiques (ou arbres de dérivations) de la grammaire G₁ par un type concret Ocaml:

type g1 = G1_S of e1 and e1 = G1_gEd of e1 | G1_EE of e1 * e1 | G1_0;;

  a)   Donner en Ocaml une définition de type g2 représentant les arbres syntaxiques de la grammaire G₂.
Réponse

  b)   Donner en Ocaml l'arbre syntaxique a2 correspondant à la dérivation de ggdgdd dans G₂ que vous avez donnée ci-dessus.
Réponse

  c)   Écrire en Ocaml une fonction mot1 qui prend un arbre syntaxique de type g1 et qui retourne le mot (chaîne de caractères) du langage L lui correspondant.
Réponse

  d)   Écrire en Ocaml une fonction totale réécrit qui transforme un arbre syntaxique a1 de type g1 en un arbre syntaxique a2 de type g2 tel que a2 représente le même mot que a1 (la preuve de correction n'est pas demandée dans cette question).
Réponse

  e)   Justifier la terminaison de ce programme.
Réponse

  f)   On admet la correction de la fonction réécrit. En déduire que G₂ reconnaît tout L.
Réponse

This document was translated from L^AT_EX by H^EV^EA and H^AC^HA.