\input{format1.tex}
\usepackage[dvips]{epsfig}
  \input{intro1.tex}



\begin{document}

\noindent \Large {\bf Universit\'e d'Orl\'eans} \hfill {\bf Ma\^{\i}trise d'Informatique}

\normalsize
%\hfill {\bf Ann\'ee 2000-01}

\begin{center}
{\it Feuille de Travaux Dirig\'es 1}
\end{center}
\hrule

%\ex
%L'objectif est de compiler un langage qui accepte, en plus
%des expressions arithmétiques usuelles~: 
%\begin{itemize}
%\item des déclarations de variables, de la forme~:
%{\tt decl variable1;}
%\item des affectations~:
%{\tt variable1 = 2+3;
%variable1 = (2+variable1)*5;}
%\item des instructions d'affichage~:
%{\tt print variable1+3;}
%\end{itemize}
%Proposer une solution pour g\'er\'er la table des symboles.
%\exe

\ex
En utilisant les r\`egles de port\'ee de Pascal, d\'eterminer pour chaque 
occurrence des noms $a$ et $b$ dans le programme suivant, quelle 
d\'eclaration s'y applique. Que fait ce programme\,?

\begin{verbatim}
program a;
  procedure b(u, v, x, y : integer);
     var a : record a, b : integer end;
         b : record b, a : integer end;
     begin with a do begin a := u; b := v end;
           with b do begin a := x; b := y end;
           writeln(a.a, a.b, b.a, b.b)
     end;
begin
  b(1, 2, 3, 4)
end.
\end{verbatim}
\exe

\ex
Pour la configuration de la table des symboles vue en cours, et pour le 
programme Pascal suivant, indiquez l'\'etat de la tds lorsque le 
reconnaisseur d'identificateurs est situ\'e au niveau de *. 

\begin{verbatim}
program param;
  procedure b(function h (n:integer):integer);
    var m : integer;
    begin m := 3; writeln(h(2)) end {b} ;

  procedure c;
    var m : integer;

    function f (n : integer) : integer;
      begin f := m + n end {f} ;

    procedure r ;
      var m : integer;
      begin {*} m := 7; b(f) end {r} ;

  begin m := 0; r end {c} ;

begin
  c
end.   
\end{verbatim}
Quelle est la valeur affich\'ee par le programme\,?
\exe

\ex
Ecrire la fonction d'insertion d'un nouvel identificateur dans la table 
des symboles dont la structure est la suivante\,:
\begin{figure}[h]
    \centering
    \noindent
    \hbox{\psfig{figure=fig-tds.eps,height=7cm,width=7cm}}
\end{figure}
\begin{itemize}
\item $dertds$ est la prochaine place libre dans la tds.
\item $derlex$ est la prochaine place libre dans le vecteur Lexemes.
\item $longtamp$ est la longueur du tampon.
\item $longlexemes$ est la taille du vecteur Lexemes.
\item $longtds$ est la taille de la tds.
\item $longsymb$ est la longueur du lex\`eme reconnu.
\end{itemize}
Cette fonction retourne l'adresse de l'identificateur ins\'er\'e.

\vspace*{2 mm}
Pour cette m\^eme structure de la tds, \'ecrire la fonction qui recherche un
identificateur dans la tds. Cette fonction retournera 0 si l'identificateur
ne figure pas dans la tds.
\exe

\ex
Inf\'erer le type polymorphe de la fonction {\em longueur} dont le corps 
d'instructions est le suivant\,:

\begin{tabular}{|l|} 
\hline
  fun longueur(pliste) =  \\
      \hspace*{2cm}   if null(pliste) then 0  \\
      \hspace*{2cm}  else longueur( tl(pliste)) + 1 ; \\
\hline 
\end{tabular}

M\^eme question pour la proc\'edure {\em append}\,:\\
\begin{tabular}{|l|}
\hline
  fun append(l1, l2) = \\
   \hspace*{2 cm}     if null(l1) then l2 \\
   \hspace*{2 cm}     else cons(hd(l1), append(tl(l1), l2)) ; \\
\hline
\end{tabular}

M\^eme question pour la proc\'edure {\em mappe}\,: \\
\begin{tabular}{|l|} \hline
  fun mappe (f, l) = \\
    \hspace*{2 cm} if null(l) then nil \\
    \hspace*{2 cm} else cons( f( hd(l)), mappe(f, tl(l)) ); \\
\hline
\end{tabular}

\exe

\end{document}