\documentclass[12pt]{article}

\input{../intro1.tex}

%caractères
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}


\begin{document}
\noindent
{\small Maîtrise d'informatique \hfill le 26 novembre 2003}

\begin{center}
{\LARGE Compilation}\\
--- examen de première session ---
\end{center}

\ex {\bf Traduction, génération et optimisation de code}
\begin{enumerate}
\item Traduire en code SPARC virtuel le programme suivant, sachant
qu'un entier occupe 4 octets.

\begin{verbatim}
program Tris;

var T: array[0..NMAX-1] of integer;
    n: integer;  

procedure echange(var x,y: integer); 
    {échange les valeurs des deux variables}

function TriBulles(n : integer): integer;
var i,j;
begin
    for i := 1 to n-1 do
        for j := n downto i+1 do 
            if T[j-1] > T[j] then echange(T[j-1],T[j])
    TriBulles := T[n/2] 
        {cette instruction équivaut à "return T[n/2]"}
end

begin
    {code correspondant à la lecture de n et de T}
    println(TriBulles(n))
end
\end{verbatim}

\item Donner le code à trois adresses correspondant aux boucles de la
fonction \texttt{TriBulles}.
\item Construire ensuite le graphe de flot de contrôle pour ce code.
\item Optimiser le code obtenu, en précisant soigneusement les techniques
d'optimisation utilisées.
\end{enumerate}
\exe

\ex {\bf Graphe de flot de contrôle et grammaires attribuées}

Considérons la grammaire suivante, représentant un langage de programmation 
très simple. 

\begin{verbatim}
instr : affectation
      | instr instr
      | WHILE exprBool DO instr ENDWHILE
\end{verbatim}

L'objectif est d'attribuer cette grammaire afin d'obtenir le graphe du flot
de contrôle d'un programme écrit dans ce langage. Faute de temps, on ne 
générera pas le code à trois adresses, mais seulement les blocs et les arcs
les reliant. On suppose disposer de fonctions de manipulation de graphes
comme \texttt{CreerBloc():bloc}, \texttt{AjouterArc(b1, b1: bloc)}, 
\texttt{FusionnerBlocs(b1, b2: bloc)} ou d'autres que vous aurez spécifiées.

\begin{enumerate}
\item Construire le graphe de flot de contrôle pour un programme de la forme
\begin{verbatim}
WHILE exprBool 
DO 
    affectation 
    affectation 
ENDWHILE 
affectation
\end{verbatim}
\item Construire la grammaire attribuée obtenant le graphe de flot de contrôle.
Pour ce faire, remarquer que le gfc correspondant à toute \texttt{instr} 
possède un \emph{bloc d'entrée}, par lequel on rentre dans le code de 
l'instruction, et un \emph{bloc de sortie}, par lequel on quitte le code 
de l'instruction.
\item Même question que précédemment, si l'on rajoute à la grammaire la règle
de production
\begin{verbatim}
instr : IF exprBool THEN instr ELSE instr ENDIF
\end{verbatim}
Observer que maintenant le gfc d'une instruction peut comporter plusieurs
blocs de sortie!
\end{enumerate}
\exe
\end{document}