\input{format1.tex}
  \input{intro1.tex}

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

\begin{document}

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

\normalsize

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

\ex
Construire un sch\'ema de traduction dirig\'e par la syntaxe qui traduit 
des expressions arithm\'etiques infix\'ees en expressions pr\'efix\'ees 
o\`u un op\'erateur appara\^{\i}t avant ses op\'erandes. Ex: $- ~x~ y$ 
est la notation pr\'efix\'ee de $x - y$. Construire les arbres d\'ecor\'es 
pour les entr\'ees $9 - 5 + 2$ et $9 - 5 * 2$.
\exe

\ex
Construire un sch\'ema de traduction pour transformer une expression 
pr\'efixe en l'expression \'equivalente \'ecrite en notation infixe. 
Construire l'arbre d\'ecor\'e pour les expressions $+ - 9~5~2$ et 
$* 9 + 5~ 2$.\\
Attention aux priorit\'es des op\'erateurs\,!
\exe

\ex
Construire un sch\'ema de traduction dirig\'e par la syntaxe qui traduit 
des expressions arithm\'etiques infix\'ees en expressions arithm\'etiques 
infix\'ees sans parenth\`eses redondantes.\\
Construire l'arbre d\'ecor\'e pour le texte\,:\\
$(((1 + 2) * (3 * 4)) + 5)$ \hspace*{.2in} $\rightarrow$ \hspace*{.2in} 
$(1 + 2) * 3 * 4 +5$ 
\exe

\ex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% D E C A L A G E S  D E  T A B L E A U X
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
On considère ici que les éléments d'un tableau sont stockés
consécutivement dans la mémoire. On veut, à partir d'une expression
d'accès à un tableau, calculer l'expression qui donne le décalage par
rapport à l'origine du tableau de l'élément considéré. Voici la
grammaire des accès aux tableaux :
\begin{verbatim}
  nom := id
  nom := id[Liste]
  Liste := expr
  Liste := Liste,expr.
\end{verbatim}
Considérons la référence de tableau A[I,J,K]. Supposons que le
tableau ait été déclaré de dimension 3 avec $n_1\times n_2 \times n_3$
éléments, le décalage est :
\[(I-1)*n_2*n_3+(J-1)*n_3+(K-1).\]

\begin{itemize}
\item
  Construisez des attributs qui permettent de calculer ce décalage.
\item
  Proposez un ordre d'évaluation de vos attributs.
\item
  Ajoutez un traîtement d'erreur quand on accède à un tableau avec une
  fonction d'accès de dimension différente de sa dimension déclarée ou
  que l'expression du décalage est évaluable statiquement et qu'on
  dépasse les bornes du tableau.
\item
  Modifiez la grammaire pour pouvoir calculer le décalage en une passe
  de bas en haut de l'arbre de dérivation.
\end{itemize}
\exe

\ex
Les r\`egles suivantes d\'efinissent la traduction d'un mot fran\c{c}ais 
en gaulois de cuisine\,:
\begin{enumerate}
\item si le mot commence par une cha\^{\i}ne non vide de consonnes,
d\'eplacer ces consonnes \`a la fin du mot et ajouter le suffixe 
{\em um}\,;\\
ex. {\em babaor} devient {\em abaorbum}
\item si le mot d\'ebute par une voyelle, ajouter le suffixe {\em ix}\,;\\
ex. {\em aster} devient {\em asterix}
\item Un {\em u} qui suit un {\em q} est une consonne\,;
\item Un {\em y} au d\'ebut d'un mot est une voyelle s'il n'est pas suivi
par une voyelle\,;
\item les mots d'une lettre ne sont pas modifi\'es.
\end{enumerate}
\begin{itemize}
\item Ecrire la grammaire qui d\'efinit les r\`egles du gaulois de cuisine.
\item D\'efinir l'attribut n\'ecessaire et ajouter \`a votre grammaire des
actions pour obtenir la traduction d'un mot fran\c{c}ais en gaulois de
cuisine. 
\item Construire les arbres d\'ecor\'es pour {\em aster, yopi} et {\em brr}. 
\end{itemize}
\exe

\end{document}