CORRIGÉ de la COMPOSITION D'INFORMATIQUE


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



Question 1 Expressions régulières
a) $\mbox{chiffre}= 0 \vert 1 \vert 2 \vert 3 \vert 4 \vert 5 \vert 6 \vert 7 \vert 9$,   $\mbox{nombre}= \mbox{chiffre}\;\mbox{chiffre}^*$,    $\mbox{réel}= \mbox{nombre}(\epsilon \vert .\mbox{nombre})$
En Lex: (0-9)(0-9)*[.(0-9)(0-9)*]

b) $\mbox{lettre}= V - \{\mbox{\tt '}\}$,   $\mbox{chaîne}= \mbox{\tt '}\mbox{lettre}^* \mbox{\tt '}(\mbox{\tt '}\mbox{lettre}^* \mbox{\tt '})^*$
En Lex: '[^']*'('[^']*')*



Question 2 Expressions arithmétiques
a) $E \rightarrow E + P \quad E \rightarrow P \quad P \rightarrow P + F \quad P ... ...F \rightarrow(E) \quad F \rightarrow\mbox{id}\quad F \rightarrow\mbox{nombre}$

b) Si le langage $\mathcal A$ des expressions arithmétiques est régulier, alors en appliquant le lemme de l'étoile pour n grand dans l'expression (n x )n, il existe un facteur répétitif, ce qui est syntaxiquement impossible.



Question 3 On peut donner une syntaxe context-free de Pascal, cf celle du cours pour CTigre. Pourtant cette syntaxe ne tient pas compte des déclarations. Un programme correct en Pascal doit avoir ses identificateurs déclarés, ce qui n'est pas décrit dans la syntaxe context-free.

Très rigoureusement, si Pascal est context-free, alors $Pascal \cap \mathcal L$ est aussi context-free en considérant le langage régulier $\mathcal L$:

program test; var id1:integer; begin id2 := 1 end.

où id1 et id2 peuvent être des identificateurs quelconques. Soit $\phi$ l'homorphisme envoyant les lettres p r o g a m t e s ; v : i n ; b = 1 d . vers le mot vide. Alors $\mathcal L' = \phi(Pascal \cap \mathcal L)$ est context-free. Mais $\mathcal L' = \{w w \}$ où w est un mot sur l'alphabet $\phi(ASCII)$. Donc $\mathcal L'$ n'est pas contex-free. Contradiction.



Question 4 a) 2

b) A adresser les variables libres des fonctions. Ce lien n'est pas nécessaire si une fonction n'a pas de variables libres. Par exemple, dans: 

function succ(x:integer): integer; begin succ := x+1 end

c) 

b0=(y=1,nil)
b1=f(x=2,y=1,s=b0)  
b2=h(x=2,y=1,s=b1)
b3=g(z=2,s=b1)
b4=f(x=1,y=2,s=b0)

d) 

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




Question 5 La seule différence vient du calcul de l'incrément et du test de fin. Dans le premier cas, on garde l'incrément et la fin dans des registres. Pour optimiser l'implantation linéaire et supprimer l'execution d'un jump à chaque itération, il suffit de mettre en fin de boucle le test de fin: 


move x e1
move s e2
move b e3
goto test
loop:
  corps de la boucle
test:
    add x s
    cmp x b
    branz loop



Question 6 On calcule itérativement les ensembles

$\mathop{\mbox{in}}(n) = \mathop{\mbox{use}}(n) \cup (\mathop{\mbox{out}}(n) - \mathop{\mbox{def}}(n))$
$\mathop{\mbox{out}}(n) = \cup \{\mathop{\mbox{in}}(s) \mid s \in \mathop{\mbox{succ}}(n) \}$


noeud 1     2     3     4     5     6     7    8     9     10
use   d     bc    bd    af    e     ad    df   ac    ac    bcdef
def         a     d     e           f     b    e     b  
in    d     bc    bd    af    e     ad    df   ac    ac    bcdef 
out   bcdef bd    af    e     adf   ac    ac   ac    d  
in    bcdef bcd   abdf  af    adef  acd   acdf ac    acd   bcdef 
out   bcdef abdf  af    adef  acdf  acd   ac   acd   bcdef  
in    bcdef bcdf  abdf  adf   acdef acd   acdf acd   acdef bcdef 
out   bcdef abdf  adf   acdef acdf  acdef acd  acdef bcdef  
in    bcdef bcdf  abdf  acdf  acdef acde  acdf acdf  acdef bcdef 
out   bcdef abdf  acdf  acdef acdef acdef acdf acdef bcdef  
in    bcdef bcdf  abcdf acdf  acdef acde  acdf acdf  acdef bcdef 
out   bcdef abcdf acdf  acdef acdef acdef acdf acdef bcdef  
in    bcdef bcdf  abcdf acdf  acdef acde  acdf acdf  acdef bcdef 
out   bcdef abcdf acdf  acdef acdef acdef acdf acdef bcdef



Question 7 On calcule itérativement les ensembles des numeros de lignes de définitions pouvant atteindre chaque noeud:

$\mathop{\mbox{in}}(n) = \cup \{\mathop{\mbox{out}}(s) \mid s \in \mathop{\mbox{pred}}(n) \}$
$\mathop{\mbox{out}}(n) = \mathop{\mbox{gen}}(n) \cup (\mathop{\mbox{in}}(n) - \mathop{\mbox{kill}}(n))$ 


     1   2   3    4    5   6    7
gen  1   2        4        6    7
kill 6   47       27       1    24
out  1   2        4        6    7 
in       1   124  2    4   2    6 
out  1   12  2    4    4   6    67 
in       1   124  124  4   124  26 
out  1   12  124  4    4   26   67 
in       1   124  124  14  124  246 
out  1   12  124  14   4   246  67 
in       1   124  124  14  124  246 
out  1   12  124  14   14  246  67 
in       1   124  124  14  124  246 
out  1   12  124  14   14  246  67


4/6/1998