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

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

\begin{document}
\thispagestyle{empty}

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

\normalsize
%\hfill {\bf Année 2000-01}

\begin{center}
{\it Feuille de Travaux Dirigés 3}
\end{center}
\hrule



\ex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% A F F E C T A T I O N S   E T   V A L E U R S - G A U C H E S
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Les expressions engendr\'ees par la grammaire qui suit peuvent contenir 
des affectations\,:\\
\hspace*{.2in} $S \rightarrow E$\\
\hspace*{.2in} $E \rightarrow E := E~|~E + E~|~(E)~|~id$\\
La s\'emantique des expressions est la m\^eme qu'en C. Plus pr\'ecis\'ement,
$b := c$ est une expression qui affecte \`a $b$ la valeur de $c$\,;\,la
valeur-d de cette expression est la m\^eme que celle de $c$. Par
cons\'equent, $a := (b := c)$ affecte la valeur de $c$ \`a $b$ puis \`a
$a$.\\
Construire une d\'efinition dirig\'ee par la syntaxe pour v\'erifier que le
membre gauche d'une affectation est bien une valeur-g. 
%On utilisera un
%attribut h\'erit\'e c\^ot\'e, attach\'e au non-terminal $E$, pour indiquer
%si l'expression engendr\'ee par $E$ appara\^{\i}t en partie gauche ou droite
%d'une affectation.
\exe




\ex
Construire une gramaire attribu\'ee qui traduit 
les nombres entiers d\'ecimaux en nombres \'ecrits en chiffres romains. 
On prend pour convention qu'un nombre romain d\'epassant mille s'\'ecrit 
en juxtaposant le nombre de milliers avec M. Ex\,:\,32400 s'\'ecrit XXXIIMCD

On utilisera un attribut h\'erit\'e {\em type} de type cha\^{\i}ne de 3 
caract\`eres qui indique les lettres \`a utiliser pour construire les 
chiffres romains et un attribut synth\'etis\'e {\em romain} qui stocke la 
valeur en romain du nombre d\'ecimal.
\exe

\ex
Construire un sch\'ema de traduction dirig\'e par la syntaxe qui traduit 
les nombres \'ecrits en chiffres romains en entiers d\'ecimaux naturels.
\exe


\ex
On s'int\'eresse \`a d\'ecrire un sous-ensemble des expressions 
r\'eguli\`eres o\`u l'union est repr\'esent\'ee par $+$, la concat\'enation 
par $*$ et $e^*$ (la fermeture de $e$) par $\{e\}$. On consid\`ere la 
grammaire suivante\,:\\
\begin{tabular}{llllllll}\\
\mbox{} & $Z$ & $\rightarrow$ & E$\$$ & \mbox{} & \mbox{} & \mbox{} & 
\mbox{} \\
\mbox{} & $E$ & $\rightarrow$ & $E + T$ & $|$ & $T$ & \mbox{} & \mbox{} \\
\mbox{} & $T$ & $\rightarrow$ & $T * P$ & $|$ & $P$ & \mbox{} & \mbox{} \\
\mbox{} & $P$ & $\rightarrow$ & $(E)$ & $|$ & $\{E\}$ & $|$ & $a$
\end{tabular}

\vspace*{2 mm}
On veut associer \`a chaque atome son rang de gauche \`a droite \`a partir
de 1 et l'ensemble de ses suivants. D\'efinir le type et le r\^ole
des attributs n\'ecessaires permettant de collecter pour une cha\^{\i}ne
donn\'ee une ensemble de couples de la forme\,:

(rang de l'atome, ensemble des rangs de ses suivants) et \'ecrire les 
actions correspondantes.

\vspace*{2 mm}
\noindent Donner l'arbre d\'ecor\'e pour la cha\^{\i}ne $(a + a * \{a\}) *
a~\$$\\
$Z$.r\'esultat $= \{(1,~\{4\}),~(2,\{3,~4\}),~(3,~\{3,~4\}),~(4,~\{5\})\}$ 
o\`u le rang \'egal \`a 5 d\'esigne le dollar de fin.
\exe

\end{document}