%  \input{../format1.tex}
\documentclass[12pt]{article}
\usepackage{a4wide}

  \input{../intro1.tex}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}


\begin{document}

\noindent \Large {\bf Université d'Orléans} \hfill {\bf Maîtrise d'Informatique}

\normalsize
\hfill {\bf Année 2002-03}

\begin{center}
{\it Partiel de compilation}\\
-- durée ~: 1h30 --
\end{center}
\hrule
\smallskip
\emph{Barème à titre indicatif~: 12 + 8}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% E X E R C I C E   1   :   S Q L
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ex
Nous voulons écrire un compilateur pour le langage SQL.
Rappelons qu'une base de données relationnelle est formée
de \emph{tables}, ayant chacune un certain nombre de \emph{champs}.
A titre d'exemple, nous utiliserons une base de données ayant trois 
tables\footnote{excuser le manque d'originalité...}~:
\begin{verbatim}
    Etudiants(numero_etudiant, nom_etudiant, prenom_etudiant)
    Cours(code_cours, descriptif)
    InscriptionsCours(numero_etudiant, code_cours, note)
\end{verbatim}
La grammaire (restreinte) des requêtes SQL qui nous intéressent est la suivante~:
\begin{verbatim}
    Requete     : select ListeChamps
                  from ListeTables
                  where Terme = Terme ;
    ListeChamps : IdChamp
                | ListeChamps, IdChamp
    IdChamp     : id
                | id.id
    Terme       : const
                | IdChamp
    ListeTables : id
                | ListeTables, id
\end{verbatim}
Les symboles terminaux de la grammaire sont les caractères ';', '.', ',','=', les mots-clés
\texttt{select}, \texttt{from}, \texttt{where}, ainsi que \texttt{const} qui désigne une 
constante et l'identificateur \texttt{id} qui désigne un nom de champ ou de table. 
\begin{enumerate}
%\textbf{Question 1}\\
\item
Proposer une structure de données pour la table des symboles, afin de
pouvoir stocker les noms des tables de la base de données,
ainsi que les noms des champs de chaque table.
Donner le contenu de votre TDS pour la base de données ci-dessus.
\item
%\textbf{Question 2}\\
Attribuer la grammaire afin de vérifier qu'une requête
respecte les critères suivants~:
\begin{enumerate}
\item Chaque table de la partie \texttt{from} doit exister dans la base.
\item Chaque champ utilisé dans la requête doit exister dans l'une des tables listées dans 
le \texttt{from}.
\item Chaque champ doit être identifié de manière non ambiguë~: la requête
\begin{verbatim}
 select numero_etudiant, nom_etudiant, note 
 from Etudiants, InscriptionsCours
 where Etudiants.numero_etudiant = 
       InscriptionsCours.numero_etudiant
\end{verbatim}
est incorrecte parce que l'identificateur \texttt{numero\_etudiant} de la
première ligne correspond à deux mêmes noms de champ des tables dans la deuxième ligne.
Si l'on remplace, dans la partie \texttt{select}, l'identificateur de champ 
\texttt{numero\_etudiant} par \texttt{Etudiants.numero\_etudiant}, la requête devient correcte.
\end{enumerate}
Préciser, en plus des règles de calcul des attributs et des autres actions sémantiques,
le rôle, le type et la nature de chaque attribut, ainsi que
l'ordre d'évaluation des attributs. Spécifier les fonctions de manipulation de la TDS
dont vous vous servez.
\end{enumerate}
\exe

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% E X E R C I C E   2   :   T R A D U C T I O N
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ex
Soient les déclarations suivantes~:
\begin{verbatim}
type t = record
           a : array [4..7, 0..5] of integer;
           suite : ^t
         end;
var elt : t;
    i : ^t;
\end{verbatim}
Les tableaux sont rangés par lignes, les entiers et les pointeurs occupent
{\bf quatre} octets.
En supposant que l'allocation mémoire soit effectuée à partir de l'adresse 20,
préciser l'adresse de chaque variable et traduire cet extrait de programme~: 
\begin{verbatim}
i := elt.suite;
while i <> NIL do
begin
    i^.a[5,3] := 0;
    i := i^.suite;
end
\end{verbatim}
\exe

\end{document}