%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input mias

\TD 5

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ttt#1{\hbox{\tt #1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% D\'efinition d'une instruction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\font\ttp = cmtt10 at 8pt
\def\ind#1{\modemath{{}_{\hbox{\ttp #1}}}}

\long\def\instr#1#2{\goodbreak\medskip{
{{\tt #1}}\hfill
{\vtop{\hsize 9cm #2\par}\goodbreak\medskip}
}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\hfq{\hfill\quad}
\def\cc#1{\hfq#1\hfq}% centr\'e
%%%\def\jg#1{\quad#1\hfq}% justification \`a gauche Revoir \c ca !!!!!!!!
\def\tvi{\vrule height 12pt depth 5pt width 0pt}
\def\tv{\tvi\vrule}
\def\trait{\noalign{\hrule}}

% les dollars de Yacc
\def\doldol{\$\$\ }
\def\dol#1{\$\kern -.05em #1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vskip 2cm
Le but de cette s\'erie d'exercices est d'illustrer les notions mises en cause par le projet.
\puce L'automate d'analyse $LALR(1)$ de la grammaire de {\sl Galileo} comporte $76$ \'etats :
vous ne pourrez donc pas vraiment l'utiliser et il faudra faire appel 
\`a un outil dont nos machines ne disposent pas : la  <<compr\'ehension>>
du processus d'analyse syntaxique de type $LR$. L'ordre dans lequel interviennent les r\`egles,
lors d'une analyse, est essentiel (et c'est peut \^etre la principale difficult\'e
du projet !). Pour cela, vous pouvez commencer par construire l'arbre d'analyse, puis consid\'erer
les r\`egles dans l'ordre convenable (lorsque vous aurez l'habitude, vous pourrez faire
de longues analyses sans vous appuyer sur un arbre).
\puce De m\^eme, il est difficile d'utiliser concr\`etement la pile d'analyse. Plut™t que cette
pile, il sera pratique :\pars
{\parindent 1cm
\item{--} d'indexer chaque occurrence des \'el\'ements du vocabulaire au fur et \`a mesure 
qu'ils apparaissent dans
l'analyse, par exemple,  une r\'eduction par la r\`egle 22, pourra se pr\'esenter
sous la forme\pars
\hfil  {\tt ES5} $\donne$ {\tt ES1 - T4},\pars
\item{--} de noter les \'el\'ements d'une production par les symboles index\'es ci--dessus, au
lieu d'utiliser les {\tt \dol i} de Yacc (dans l'exemple pr\'ec\'edent, on notera : {\tt ES5} pour 
{\tt \doldol}, {\tt ES1} pour {\tt\dol 1} et {\tt T4} pour {\tt \dol 3}),\par
\item{--} d'observer que dans la notation {\tt \dol i} de Yacc, {\tt i} 
d\'etermine une position dans la pile d'analyse
et qu'une affectation {\tt \dol i := a} correspond au rangement de la valeur de {\tt a}  \`a
cette position. Avec nos conventions, vous pourrez noter, par exemple {\tt T4 := a}
pour {\tt\dol 3 := a}, mais vous devrez vous m\'efier des ambigu\"\i t\'es que cela comporte.\par
}
\puce Le $P$--code est produit au fur et \`a mesure : lorsque la r\'eduction par une r\`egle
permet d'\'emettre
une (ou plusieurs) $P$--instruction(s), celle(s)--ci vien(nen)t se placer \`a la suite de 
celles qui sont d\'ej\`a \'ecrites 
(le cas des $P$--instructions de saut ({\tt UJP p, FJP p et  TJP p}) dont
on ne conna”t pas toujours la destination {\tt p} au moment o\`u on les \'ecrit, sera vu en d\'etail).
La suite des $P$--instructions \'emises lors d'une analyse {\tt Xi} $\donne$ \dots $\donne$ \dots \  
est appel\'ee <<{\sl le $P$--code de {\tt Xi}}>> (ou de l'analyse en question). 
%%%%%%%%%%%%%%%%%%%%%%%%%%
\exot{Les expressions.}
Soit {\tt Expr} une expression dont la valeur est {\tt Val(Expr)}
et soit {\tt E} $\donne$ \dots $\donne$ {\tt Expr} la d\'erivation de {\tt Expr}.\par
On veut v\'erifier que l'effet
global de l'ex\'ecution du $P$--code de {\tt E} est l'empilement de {\tt Val(Expr)} ; plus pr\'ecis\'ement,
si {\tt SP} est l'indice du sommet de {\tt PILE} juste avant l'ex\'ecution, alors, l'ex\'ecution
peut \^etre  r\'esum\'e par\par\vskip -.4ex
\centerline{\tt SP := SP + 1 PILE[SP] := Val(Expr).}
\pars
Pour cela, calculez le $P$--code de l'analyse de {\tt 12 + 5 * 10} et ex\'ecutez--le.
\pars
Nous verrons d'autres exemples par la suite.
%%%%%%%%%%%%%%%%%%%%%%%%%%
\exot{La d\'eclaration des variables.}
Pendant la partie <<d\'eclaration>>, chaque identificateur est rang\'e dans la table et la place
n\'ecessaire pour contenir les donn\'ees correspondantes est r\'eserv\'ee au d\'ebut de {\tt PILE}.
Par la suite, chaque identificateur sera caract\'eris\'e par son <<{\sl d\'eplacement}>>
c'est--\`a--dire par la distance \`a parcourir, en partant de la base de {\tt PILE}, pour atteindre
le d\'ebut des donn\'ees qu'il repr\'esente.
\pars
Calculez la table et le $P$--code des d\'eclarations suivantes, et ex\'ecutez--le.
\prog
\p variables
 \a x : entier 
 \p y : entier
 \p t : tableau[5]
\r fin
\endprog
(Ces d\'eclarations et la table correspondante nous serviront dans toute la suite.)
\exot{Les variables et les affectations.}
Les variables sont d\'efinies par les r\`egles 16 et 17.
Une variable est caract\'eris\'ee par une adresse, c'est--\`a--dire un d\'eplacement.
\par
L'ex\'ecution du $P$--code d'une variable a pour effet global d'empiler son adresse.
\par
On veut v\'erifier que l'ex\'ecution d'une instruction d'affectation (r\`egle 10) a pour effet global
de mettre la valeur affect\'ee \`a l'adresse de la variable.
\pars
Pour cela, calculez le $P$--code des deux affectations suivantes, et ex\'ecutez--les.
\puce {\tt x := 3}
\puce {\tt y := 12 + 5 * 10}
\puce {\tt t[4] := 12 + 5 * 10}
\exot{R\'esumons.}
L'ex\'ecution du $P$--code d'une expression d\'efinie par l'une des r\`egles 28 et 30 a pour effet
d'empiler la valeur (s'il y en a une !) qui se trouve \`a l'adresse de la variable correspondante.
\par
Calculez et ex\'ecutez le $P$--code des affectations suivantes :
\puce {\tt t[x] := y + x * t[4]}
\puce {\tt t[x - 1] := ( t[3] * t[4] ) * 2}
\exot{Les instructions conditionnelles.}
La syntaxe des instructions conditionnelles simples est d\'efinie par la r\`egle 
\puce $ 11 : I \donne \b{si} \k E \k \b{alors} \k Li \k \b{fin}$
\par
mais la r\`egle qui a \'et\'e retenue pour l'analyse syntaxique 
\puce $ 11 : I\donne \b{si} \k E \k Malors \k Li \k \b{fin}$
\par
comporte un non--terminal de <<marquage>> et une r\`egle de production 
\puce $ 33 : Malors \donne \b{alors}$\par
r\'etablissant la syntaxe voulue.
\pars
 \midinsert
\parm
\line{%
\hfil
\vtop{\hsize 4cm
\def\trait{&\omit\hrulefill&\cr}
\offinterlineskip
\halign{\hfil#\kern .3em&\tv\kern 1em\hfil {\tt #} \kern 1em\hfil\tv &#\cr
\trait
&$P$-code&\cr
&de&\cr
&{\tt E}&\cr\trait
&$P$-code&\cr
&de&\cr
&{\tt Li}&\cr\trait
&{\tt ??}&\cr\trait
}}
\hfil
\vtop{\hsize 4cm
\def\trait{&\omit\hrulefill&\cr}
\offinterlineskip
\halign{\hfil#\kern .3em&\tv\kern 1em\hfil {\tt #} \kern 1em\hfil\tv &#\cr
\trait
&$P$-code&\cr
&de&\cr
&{\tt E}&\cr\trait
$a $ : &{\tt FJP ?}&\cr\trait
&$P$-code&\cr
&de&\cr
&{\tt Li}&\cr\trait
}}
\hfil
}%fin de \line
\parb
\hfil {\bf Sans marquage.}\hfil {\bf Avec marquage.}
\parb
\endinsert
Les figures montrent l'aspect des $P$--codes produits par la r\`egle initiale et par la 
r\`egle <<marqu\'ee>>. Avec cette derni\`ere, le $P$--code de $Malors$
vient se placer entre ceux de $E$ et de $Li$ : l'adresse de destination de l'instruction de saut
{\tt FJP} n'est pas encore connue mais on enregistre son adresse {\tt a} dans une 
<<liste de sorties>> pour pouvoir compl\'eter
cette $P$--instruction lorsque ce sera possible. Remarquez que $Li$ elle--m\^eme peut comporter
des sorties : elles seront n\'ecessairement dirig\'ees vers la m\^eme adresse.
\pars
Calculez et ex\'ecutez le $P$--code de la liste d'instructions suivante :
\prog
\p si x < y alors 
 \a si x < t[3] alors x := 0 fin ;
 \p y := t[4]
\r fin ;
\p ecrire( x + y)
\endprog  
Remarque : le marquage de la r\`egle 9, relative aux listes d'instructions, correspond au fait
que les instructions d'une telle liste doivent \^etre ex\'ecut\'ees s\'equentiellement.
\exo
Appliquez la m\'ethode pr\'ec\'edente pour traiter la boucle (qui n'est pas dans le langage qui vous
est propos\'e) dont la syntaxe est $I\donne \b{repeter} \k Li \k \b{jusqua} \k E$ et
dont la signification vous est bien connue.
\pars
Calculez et ex\'ecutez le $P$--code 
 de la liste d'instructions suivante :
\prog
\p x := -1 ;
\p y := 1 ;
\p repeter
 \a x := x + 1 ;
 \p t[x] := y + 2 ;
 \p si x > 1 alors y := y * (x - 1 ) fin 
\r jusqua x = 5
\endprog
\exot{Evaluation partielle des op\'erations bool\'eennes.}
On rappelle que, pour {\sl Galileo}, 
toute expression peut s'interpr\'eter comme une expression bool\'eenne : 
fausse si elle est \'egale \`a {\tt 0} et vraie sinon.
\pars
Le projet propose des $P$--instructions 
capables de calculer la conjonction et la disjonction. Il y a cependant une autre fa\c con de proc\'eder.
Par exemple on sait que :\pars
{\parindent 1cm
\item{--} si {\tt A} est vraie alors {\tt (A et B) = B}\par
\item{--} si {\tt A} est fausse alors {\tt (A et B)} est fausse : dans ce cas, il n'est pas
n\'ecessaire de calculer la valeur de {\tt B} pour conclure.\par
}\pars
\puce Appliquez la m\'ethode de marquage \`a la r\`egle $E \donne E\k \b{et} \k E$ pour exploiter cette
remarque.
\puce Transposez ce qui pr\'ec\`ede au cas de la disjonction.
\parm
Vous pouvez utiliser 
une $P$--instruction {\tt TJP} analogue \`a {\tt FJP} pour laquelle le faux est remplac\'e
par le vrai.


\bye