Enoncé et corrigé en Postscript Réponses intégrées ou à la demande

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 G1 (resp. G2) définie par l'axiome S1 (resp. S2) et les règles de production ci-dessous à gauche (resp. à droite):
S1 ® E
E ® g E d
E ® E E
E ® e
          
S2 ® E
E ® g E d E
E ® e

2.1  

  a)   Donner deux dérivations de ggdgdd l'une dans G1 et l'autre dans G2.
Réponse

  b)   Les grammaires G1 et G2 sont-elles ambigües? LL(1) ? LR(1) ?
Réponse

2.4   La grammaire G1 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 G2 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 G1 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 G2.
Réponse

  b)   Donner en Ocaml l'arbre syntaxique a2 correspondant à la dérivation de ggdgdd dans G2 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 G2 reconnaît tout L.
Réponse


This document was translated from LATEX by HEVEA and HACHA.