COMPOSITION D'INFORMATIQUE


Jean-Jacques Lévy
30 Mars 1998, 2h

Avertissement On attachera une grande importance à la clarté, à la précision, à la concision de la rédaction. Seules les notes de cours sont autorisées.

Question 1 Expressions régulières

a) Donner une expression régulière pour décrire les nombres réels de Pascal.

b) Une chaîne de caractères en Pascal est une suite de caractères encadrée par des apostrophes ('). Le caractère ' est lui représenté par deux apostrophes consécutives ''. Donner un automate fini et une expression régulière reconnaissant les chaînes Pascal. Mettre cette expression sous forme d'une expression régulière acceptée par Lex.

Question 2 On considère les expressions arithmétiques éventuellement parenthésées contenant les identifieurs (considérés comme des symboles terminaux), les entiers (aussi symboles terminaux) et les opérateurs + et *.

a) Donner une syntaxe context-free non ambigüe.

b) Peut-on décrire ces expressions par une expression régulière? Donner une raison précise en utilisant les propriétés des langages réguliers.

Question 3 Expliquer pourquoi on peut répondre oui et non à la question suivante: Pascal est-il un langage context-free?

Question 4 Portée des variables:

a) Quelle est la valeur imprimée par le programme Pascal suivant? Indéfinie, 1 ou 2?

    program test;
      var y: integer;
      procedure f; begin writeln (y) end;
      procedure g; 
      var y: integer;
      begin y := 1; f end;
    begin y := 2; g end.

b) A quoi sert le lien statique dans les blocs d'activation de Pascal? Donner des exemples simples et précis de fonctions dont l'activation n'a pas besoin de ce lien.

c) Pouvez-vous décrire la pile des blocs d'activation après quelques appels de fonctions dans le programme Pascal suivant:

    program test;
      var y : integer;
      function f(x,y:integer): integer; 
        function g(z: integer): integer; 
            begin g := if z = 0 then 1 else z + f(z-1,x) end;
        function h(x,y: integer): integer; 
            begin h := g(x)+y end;
      begin f := h(x,y) end;
    begin  y := 1; writeln (f(2,1)) end.

d) On veut diminuer le nombre d'appels de procédure en remplaçant le corps de g dans h (inlining). Donner le texte du programme résultant?

Question 5 La boucle for x:=e₁ step e₂ until e₃ do s a deux sémantiques possibles:

a) e₂ et e₃ sont réévalués à chaque itération de la boucle et le test $(x - e_3) \times \mbox{signe}(e_2) \gt 0$ est réalisé.

b) e₁, e₂ et e₃ sont évalués une seule fois avant d'entrer dans la boucle.

Dans chacun des cas, donner une traduction intuitive de cette instruction. Quelle est la meilleure implantation linéaire?

Question 6 Calculer la durée de vie des variables dans le programme suivant (où l'indentation fait office de délimitation des blocs):

1     while d > 0 do
2         a := b + c;
3         d := d - b;
4         e := a + f;
5         if e <> 0 
6             then f := a - d;
7             else b := d + f;
8                  e := a - c;
9         b := a + c;

b, c, d, e et f sont supposés nécessaires après ce programme.

Question 7 Dans du code à 3 adresses, si on a une instruction de la forme x := 5, on peut essayer de remplacer les expressions utilisant x par la valeur constante 5 (propagation des constantes). Pour cela il faut savoir si seule cette définition de x est valable dans cette expression. On calcule donc l'ensemble des définitions dont une instruction dépend.

Montrer qu'en faisant une variation sur le schéma de calcul de la durée de vie des variables, on peut calculer les ensembles $\mathop{\mbox{in}}(n)$ et $\mathop{\mbox{out}}(n)$ des définitions pouvant atteindre le début et la fin de chaque nud n en faisant intervenir pour tout nud n les ensembles $\mathop{\mbox{gen}}(n)$ et $\mathop{\mbox{kill}}(n)$ des définitions générées et annulées par le nud n.

Appliquer ce calcul au programme:

1        x := 5
2        z := 1
3    l1: if z > x goto l2
4        z := z + z
5        goto l1
6    l2: x := z - x
7        z := 0