\input mias
\hsize=16cm \vsize=24cm
%%%%% 
\TD 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% pour les tableaux :
\def\cc#1{\hfq#1\hfq}% centr\'e
\def\ad#1{\hfq#1\quad}%call\'e \`a droite
\def\ag#1{\quad#1\hfq}%call\'e \`a gauche
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
\def\id{{\bf id}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\eg{{\mathop{\hbox{\tt =}}}}
\def\oplus{+}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Des exercices  sont \'enonc\'es au verso de cette feuille.

\remm
La grammaire $G_1$.
\endrem
Alphabets :
$Vt = \{\oplus,  * , ( , ) , \id\}$ et
$Vn = \{E , T , F\}$. Axiome : $E$.
\remm
Productions et une table d'analyse $LR$ pour $G_1$.
\endrem
\pars
\line{\hfil
\vtop{\hsize  5cm 
\parindent 1cm
\vskip 1cm
\item{1 : } $E \prod E\oplus T$\par
\item{2 : } $E \prod T$\par
\item{3 : } $T \prod T * F$\par
\item{4 : } $T \prod F$\par
\item{5 : } $F \prod (E)$\par
\item{6 : } $F \prod \id $\par
}\hfil
$$\vtop{
\offinterlineskip
\halign{#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}%
&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#\cr
&&\omit&\multispan{18}\hrulefill\cr
&&&$\$ $&&$\oplus$&&$*$&&$($&&$)$%
&&$\id$&&$E$&&$T$&&$F$&\cr
\trait
\tv&0&& && && &&$4$&& &&$5$&&$1$&&$2$&&$3$&\cr
\trait
\tv&1&&Acc&&$6$&& && && && && && && &\cr
\trait
\tv&2&&$r2$&&$r2$&&$7$&& &&$r2$&& && && && &\cr
\trait
\tv&3&&$r4$&&$r4$&&$r4$&& &&$r4$&& && && && &\cr
\trait
\tv&4&& && && &&$4$&& &&$5$&&$8$&&$2$&&$3$&\cr
\trait
\tv&5&&$r6$&&$r6$&&$r6$&& &&$r6$&& && && && &\cr
\trait
\tv&6&& && && &&$4$&& &&$5$&& &&$9$&&$3$&\cr
\trait
\tv&7&& && && &&$4$&& &&$5$&& && &&$10$&\cr
\trait
\tv&8&& &&$6$&& && &&$11$&& && && && &\cr
\trait
\tv&9&&$r1$&&$r1$&&$7$&& &&$r1$&& && && && &\cr
\trait
\tv&10&&$r3$&&$r3$&&$r3$&& &&$r3$&& && && && &\cr
\trait
\tv&11&&$r5$&&$r5$&&$r5$&& &&$r5$&& && && && &\cr
\trait
}}$$
\hfil}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\parb
\remm
Exemple d'analyse dans $G_1$, avec la table pr\'ec\'edente : $\id\oplus\id*\id$ 
\endrem
%%%%%%%%%
$$\vbox{\def\k{\mkern 4mu}
\offinterlineskip
\halign{\tv#&\ag{#}&\tv#&\ag{#}&\tv#&\ad{#}&\tv#&\ag{#}&\tv#\cr
\trait
&\hfill Pile &&\hfill Pile d'\'etats&&Entr\'ee\hfill&&\hfill Actions&\cr
\trait
&$\varepsilon $&&$0$&&$\id\oplus\id*\id\k \$ $&&($5$ : lecture de $\id$)&\cr
\trait
&$\id$&&$0\k 5 $&&$\oplus\k \id*\id\k \$ $&&$r6 : F\prod \id$&\cr
\trait
&$F$&&$0\k 3 $&&$\oplus\k \id*\id\k \$ $&&$r4 : T\prod F$&\cr
\trait
&$T$&&$0\k 2 $&&$\oplus\k \id*\id\k \$ $&&$r2 : E\prod T$&\cr
\trait
&$E$&&$0\k 1 $&&$\oplus\k \id*\id\k \$ $&&($6$ : lecture de $\oplus$)&\cr
\trait
&$E\oplus$&&$0\k 1\k 6 $&&$\id*\id\k \$ $&&($5$ : lecture de $\id$)&\cr
\trait
&$E\oplus\id$&&$0\k 1\k 6\k 5 $&&$*\k \id\k \$ $&&$r6 : F\prod \id$&\cr
\trait
&$E\oplus F$&&$0\k 1\k 6\k 3 $&&$*\k \id\k \$ $&&$r4 : T\prod F$&\cr
\trait
&$E\oplus T$&&$0\k 1\k 6\k 9 $&&$*\k \id\k \$ $&&($7$ : lecture de $*$)&\cr
\trait
&$E\oplus T *$&&$0\k 1\k 6\k 9\k 7 $&&$\id\k \$ $&&($5$ : lecture de $\id$)&\cr
\trait
&$E\oplus T * \id$&&$0\k 1\k 6\k 9\k 7\k 5 $&&$\$ $&&$r6 : F\prod \id$&\cr
\trait
&$E\oplus T * F$&&$0\k 1\k 6\k 9\k 7\k 10 $&&$\$ $&&$r3 : T\prod T*F$&\cr
\trait
&$E\oplus T$&&$0\k 1\k 6\k 9 $&&$\$ $&&$r1 : E\prod E\oplus T$&\cr
\trait
&$E$&&$0\k 1 $&&$\$ $&&$Acc$&\cr
\trait
}}
$$
\parb

\remm
La grammaire $G_2$.
\endrem
Alphabets :
$Vt = \{\eg , * ,\id\}$ et $Vn = \{S , G , D\}$. Axiome : $S$.
\remm
Productions et une table d'analyse $LR$ pour $G_2$.
\endrem
\pars
\line{\hfil
\vtop{\hsize  5cm 
\parindent 1cm
\vskip 1cm
\item{1 : } $S \prod  G\eg D$\par
\item{2 : } $S \prod  D$\par
\item{3 : } $G \prod  * D$\par
\item{4 : } $G \prod \id$\par
\item{5 : } $D \prod G$\pars
}
\hfil
$$\vtop{
\offinterlineskip
\halign{#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}%
&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#&\cc{#}&\tv#\cr
&&\omit&\multispan{14}\hrulefill\cr
&&&$\$ $&&$\eg$&&$*$&&$\id$&&$S$%
&&$G$&&$D$&\cr
\trait
\tv&$0$&& && &&$4$&&$5$&&$1$&&$2$&&$3$&\cr
\trait
\tv&$1$&&$Acc$&& && && && && && &\cr
\trait
\tv&$2$&&$r5$&&$6$&& && && && && &\cr
\trait
\tv&$3$&&$r2$&& && && && && && &\cr
\trait
\tv&$4$&& && &&$4$&&$5$&& &&$8$&&$7$&\cr
\trait
\tv&$5$&&$r4$&&$r4$&& && && && && &\cr
\trait
\tv&$6$&& && &&$4$&&$5$&& &&$8$&&$9$&\cr
\trait
\tv&$7$&&$r3$&&$r3$&& && && && && &\cr
\trait
\tv&$8$&&$r5$&&$r5$&& && && && && &\cr
\trait
\tv&$9$&&$r1$&&$r1$&& && && && && &\cr
\trait
}
}$$
}
\par\vskip 1cm
\remm
Comment lire une table d'analyse.
\endrem
{\parindent 1cm
\item{--} la premi\`ere colonne contient les num\'eros des \'etats 
d'un automate,\par
\item{--} la premi\`ere ligne contient le symbole $\$ $ et tous les symboles de la grammaire :
ces derniers constituent le <<vocabulaire>> de l'automate,\par
\item{--} dans la table elle--m\^eme, 
les num\'eros isol\'es d\'efinissent les transitions d'un automate fini : \par
\itemitem{--} pour les symboles terminaux, une transition correspond \`a une lecture
(d'o\`u l'expression {\tt shift} (d\'ecalage) utilis\'ee par Yacc dans ses tables),\par
\itemitem{--} pour tout non terminal $X$, les transitions indiqu\'ees doivent 
s'effectuer apr\`es toute <<r\'eduction>> sur une r\`egle relative \`a $X$
(Yacc utilise l'expression {\tt goto}),\par
\item{--}l'entr\'ee de cet automate est num\'erot\'ee $0$ 
(les sorties ne jouent aucun r™le ici et ne sont
donc pas mentionn\'ees),\par
\item{--} les autres informations port\'ees dans la table sont les <<actions>> suivantes :\par
\itemitem{--} $Acc$ : accepter (fin d'analyse d'une phrase <<correcte>>),
\itemitem{--} $ri$ : r\'eduire par la r\`egle num\'ero $i$,\par
\itemitem{--} les cases vides correspondent \`a des erreurs de syntaxe
(les {\tt error} de Yacc).\par
}
\par\vskip 1cm
\remm
Exercices \`a faire sur chacune de ces grammaires.
\endrem
\puce Tracer le diagramme de transition de l'automate d\'efini par la table.
\puce Comment faire des diagnostics d'erreur ? 
reporter ces diagnostics sur la table d'analyse. 
\puce Faire l'analyse de phrases \'ecrites dans le vocabulaire (terminal) 
de la grammaire consid\'er\'ee.
\puce Proposer des actions s\'emantiques et les ex\'ecuter sur les analyses pr\'ec\'edentes.
\puce Ecrire un programme Yacc capable de produire
un analyseur syntaxique ex\'ecutant les actions s\'emantiques.


\bye