\documentclass[12pt]{article}
\usepackage{caml}
\usepackage{a4}
\usepackage{url}
\usepackage{alltt}
\usepackage{shadow}
\usepackage{graphicx}
\usepackage{color}
\usepackage{portland}
\usepackage{times}
\usepackage{slide}
\usepackage{xypic}
\newenvironment{derivd}{\begin{array}{l}}{\end{array}}
\newenvironment{pile}{\begin{array}{@{(}l@{\qquad,\qquad}r@{)}}}{\end{array}}
\newenvironment{pilecomm}{\begin{array}{@{(}l@{\qquad,\qquad}r@{)\qquad}l}}{\end{array}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{D\'efinition}
\newtheorem{notation}[theorem]{Notation}
\newcommand{\sderd}{\ensuremath{\Rightarrow_{d}}}
\newcommand{\sdernd}{\ensuremath{\Rightarrow^{\ast}_{d}}}
\newcommand{\derd}[2]{\ensuremath{#1\Rightarrow_{d}#2}}
\newcommand{\dernd}[2]{\ensuremath{#1\Rightarrow^{\ast}_{d}#2}}
\newcommand{\lrzitem}[2]{(\ensuremath{#1\rightarrow #2})}
\newcommand{\slritem}[2]{\ensuremath{#1\rightarrow #2}}
\newcommand{\lroitem}[3]{(\ensuremath{#1\rightarrow #2},\;#3)}
\newcommand{\lrstate}[2]{\framed<5pt>{(#1)\begin{array}{l}#2\end{array}}}
\newcommand{\lalroitem}[3]{\ensuremath{#1\rightarrow #2}}
\newcommand{\goto}[3]{\ensuremath{\mbox{\bf goto}(#1,#2)=#3}\quad}
\long\def\ignore#1{\relax}
\begin{document}
\landscape
\refstepcounter{section}
\begin{plaintexslide}
\LARGE
\mbox{}
\vfill
\centershabox{\huge Analyse Syntaxique ascendante}
\vfill
  \begin{itemize}
    \item D\'efinition d'analyse ascendante LR
    \item D\'efinition de poign\'ee et pr\'efixe viable
    \item Structure d'un analyseur ascendant
    \item D\'efinition et construction des Items LR(k)
    \item D\'efinition et construction des tables LR(k)
    \item Un exemple LR(0)
    \item Un exemple LR(1)
    \item Construction des tables SLR
    \item Construction des tables LALR(1)
  \end{itemize}
\vfill
\end{plaintexslide}


\begin{texslide}{Analyse ascendante}

Cette m\'ethode  cherche a construire une  d\'erivation droite en la reconstituant \`a
l'envers \`a partir de la cha\^{\i}ne de terminaux vers le symbole initial, ou de fa\c{c}on
\'equivalente, cherche \`a  construire un arbre  de d\'erivation a partir des feuilles
selon un  parcours inverse  d'un parcours  en   profondeur d'abord de  gauche  a
droite.\\

Pour  savoir  simplement  quand  l'analyse  s' arr\^ete avec  succ\`es  pour  une
grammaire $G$,  on travaille toujours sur une  grammaire dite \emph{augment\'es}
$G'$ qui  est $G$  avec un nouveau  symbole $S'$  comme symbole de  d\'epart, un
nouveau   symbole   terminal   \$   et  une   transition   suppl\'ementaire   
\[S'\quad\rightarrow\quad S\$ \]
\end{texslide}
\begin{texslide}{Terminologie}
\begin{notation} Dans ce  qui suit, on utilisera les conventions suivantes: 

  \begin{description}
    \item[des lettres majuscules $A,\ldots{} Z$] indiquent des  symboles non-terminaux
    \item[des lettres grecques $\alpha,\beta,\gamma,\ldots{}$] indiquent des
          \emph{s\'equences} de symboles terminaux ou non-terminaux
    \item[des lettres minuscules $a,b,c,\ldots{}$] indiquent des  symboles terminaux
    \item[des lettres minuscules $\ldots{},u,v,x,y,w,z$] indiquent des
          \emph{s\'equences} de symboles terminaux
  \end{description}
\end{notation}

\begin{definition}{Analyseurs LR}
Les  analyseurs ascendants  le plus  connus sont  dans la  classe  \emph{LR} des
analyseurs qui  lisent le flot de  tokens en entr\'ee \emph{de  gauche a droite}
(le \emph{L}  dans \emph{LR})  pour reconstruire une  d\'erivation \emph{droite}
(le \emph{R} dans \emph{LR}).
\end{definition}
\end{texslide}

\begin{texslide}{D\'efinitions techniques}
\begin{definition}[D\'erivation droite]
Une d\'erivation droite est une d\'erivation qui remplace \`a chaque \'etape le symbole non terminal
le plus \`a droite.\\
On notera \derd{\alpha}{\beta} une \'etape de d\'erivation droite entre $\alpha$ et $\beta$,
et on notera \dernd{\alpha}{\beta} une s\'erie (m\^eme vide) d'\'etapes de d\'erivation droite
entre $\alpha$ et $\beta$.
\end{definition}
\begin{definition}[Protophrase d'une grammaire $G$]
Une protophrase est une s\'equence de symboles terminaux et non terminaux qui peut
appara\^{\i}tre en cours d'une d\'erivation du symbole initial $S$ d'une grammaire $G$.\\
On parle de protophrase \emph{droite} (resp. \emph{gauche}) lorsque cette s\'equence peut appara\^{\i}tre
dans une d\'erivation droite (resp. gauche) de $G$.\\
\end{definition}

\end{texslide}

\begin{texslide}{D\'efinitions techniques, suite}
\begin{definition}[Poign\'ee (handle)]
Dans une protophrase $\phi$, la s\'equence $\gamma$ est une \emph{poign\'ee} \'a
la  position  $n$ pour  la  grammaire  $G$ si  ell'est  la  partie gauche  d'une
production  $X\rightarrow   \gamma$,  et   que  cette  production   doit  \^etre
appliqu\'ee  \`a   $\phi$  en  position  $n$  pour   construire  la  protophrase
pr\'ec\'edente dans une d\'erivation droite \'a  partir de $S$ vers $\phi$ avec la
grammaire $G$.
\end{definition}

\begin{definition}[Pr\'efixe viable]
Une s\'equence  $\gamma$ est  un \emph{pr\'efixe viable}  pour une grammaire  $G$ si
$\gamma$  est  un  pr\'efixe  de  $\alpha\beta$,  o\`u  $\phi=\alpha\beta  w$  est  une
protophrase droite de $G$ est $\beta$ est une poign\'ee dans cette
protophrase.\\
Autrement dit, un pr\'efixe viable est un pr\'efixe $\gamma$ d'une protophrase
$\phi$, mais  qui ne s' \'etend pas plus \`a droite d'une poign\'ee $\beta$
de $\phi$.
\end{definition}
\end{texslide}

\begin{texslide}{Un exemple}
\large
Sur la grammaire augment\'ee
\[
  \begin{array}{c@{\qquad\rightarrow\qquad}l}
   S  & E\; \$            \\
   E  & E + T\; |\; T       \\
   T  & id \\
  \end{array}
\]
l'unique d\'erivation droite pour $id+id+id\;\$$ est la suivante:
\[
\begin{derivd}
 \overline{S} \\
 \overline{E}\;\$\\
 {E + \overline{T}}\; \$\\
 \overline{E} + {id}\; \$\\
 {E + \overline{T}} + id\;\$\\
 \overline{E} + {id} + id\;\$\\
 {\overline{T}} + id + id\; \$\\
 {id}+ id + id\; \$\\
\end{derivd}
\qquad\qquad
\begin{derivd}
 {S} \\
 \underline{E\;\$}\\
 \underline{E + {T}}\; \$\\
 {E} + \underline{id}\; \$\\
 \underline{E + {T}} + id\;\$\\
 {E} + \underline{id} + id\;\$\\
 \underline{{T}} + id + id\; \$\\
 \underline{id}+ id + id\; \$\\
\end{derivd}
\]
Chaque ligne est une protophrase droite, en surlign\'e les symboles produits, et
en souligne les poign\'ees.\\
Les pr\'efixes viables sont les pr\'efixes qui ne s'\'etendent
pas plus loin qu'une poign\'ee. Par exemple, sur la protophrase
\( {E} + \underline{id} + id\;\$\) ce sont \(\epsilon,E,E+,E+id\).
\end{texslide}

\begin{texslide}{D\'efinitions techniques, fin}
\begin{definition}[$FIRST_k(\gamma)$]
\'Etant  donn\'ee une  grammaire  $G$, l'ensemble  $FIRST_k(\gamma)$ contient  les
pr\'efixes de longueur $k$ des s\'equences de non terminaux de longueur au moins $k$
d\'erivables   \`a   partir  de   $\gamma$ dans $G$, \emph{et} les s\'equences de
non terminaux de longueur inf\'erieur \`a $k$ d\'erivables depuis $\gamma$.
\end{definition}

\begin{definition}[$EFF_k(\gamma)$ ($\epsilon-free\; FIRST_k$)]
\'Etant donn\'ee  une grammaire  $G$, $EFF_{k}$ est  le sousensemble  de $FIRST_k$
obtenu en  consid\'erant seulement  les d\'erivations qui  ne r\'eduisent  pas sur
$\epsilon$  un   non  terminal   en  t\^ete  de   cha\^{\i}ne.
\end{definition}
\end{texslide}

\begin{texslide}{Exemples}
Pour la grammaire:
\[
  \begin{array}{c@{\qquad\rightarrow\qquad}l}
   S  & A\;B            \\
   A  & B\;a\; |\; \epsilon       \\
   B  & C\;b\;|\;C \\
   C  & c\;|\;\epsilon \\
  \end{array}
\]
on a:
\begin{description}
\item[$FIRST_2(S)$] = \(\{\epsilon,a,b,c,ab,ac,ba,ca,cb\}\)
\item[$EFF_2(S)$] = \(\{ca,cb\}\)
\end{description}

\end{texslide}

\begin{texslide}{Grammaires LR(k)}
On peut maintenant donner la d\'efinition formelle de la classe des grammaires $LR(k)$.
\begin{definition}[Grammaire LR(k)]
Une grammaire G est dans LR(k) ($k\geq 0$) si les trois conditions suivantes:
  \begin{itemize}
    \item $S\sdernd \alpha Aw \sderd \alpha\beta w$
    \item $S\sdernd \gamma Bx \sderd \alpha\beta y$
    \item $FIRST_{k}(w) = FIRST_k(y)$
  \end{itemize}
impliquent $\alpha=\gamma, A=B, x=y$
\end{definition}
Autrement dit,  il suffit de  regarder  les premiers  $k$  symboles en entr\'ee au
moment ou il faut choisir une production pour la r\'eduction dans la d\'erivation droite.
\end{texslide}

\begin{texslide}{Structure de l'analyseur}
\Large
Les grammaires $LR(k)$ sont celles dont le langage est reconnu par un analyseur d\'eterministe
$LR(k)$. Cet analyseur utilise une pile et le flot d'entr\'ee, qui d\'ecrivent
une \emph{configuration} de l'analyseur, not\'ee
\[
\begin{pile}
X_1\ldots{}X_j & a_i\ldots{}a_{n}
\end{pile}
\]
o\`u les $X$ sont de symboles, terminaux ou non terminaux, stoqu\'es sur la pile, alors que les $a$ sont
seulement des symboles terminaux, et correspondent aux terminaux non encore lus sur le flot d'entr\'ee.

L'analyseur travaille en effectuant quatre actions possibles:
\begin{description}
  \item[shift (d\'ecalage)] on transfert le terminal $a_i$ du flot d'entr\'ee vers la pile
  \item[reduce (r\'eduction)] on reconna\^{\i}t sur le sommet de la pile une partie droite d'une
                            production $Y\rightarrow X_{j-k}\ldots{}X_{j}$, on l'enl\`eve
                            et on la remplace par sa partie gauche $Y$
  \item[erreur]	l'analyseur s'arr\^ete et signale un erreur
  \item[accept] l'analyseur s'arr\^ete et signale que la phrase a \'et\'e reconnue
\end{description}
Pour choisir les actions, on utilise une table d'analyse que l'on verra plus avant.
\end{texslide}

\begin{texslide}{Un exemple}
\large
Sur la grammaire augment\'ee
\[
  \begin{array}{c@{\qquad\rightarrow\qquad}l}
   S  & E\; \$            \\
   E  & E + T\; |\; T       \\
   T  & id \\
  \end{array}
\]
Une possible s\'equence de reconnaissance pour $id + id + id\; \$$ pour un analyseur ascendant serait:
\[
\begin{pilecomm}
\obeyspaces
        & id + id + id\; \$ & shift\\
 \underline{id}     & + id + id\; \$ & reduce\\
 \underline{T}      & + id + id\; \$ & reduce\\
 E      & + id + id\; \$ & shift\\
 E +    & id + id\; \$ & shift\\
 E + \underline{id} & + id\; \$ & reduce\\
 \underline{E + T}  & + id\; \$ & reduce\\
 E      & + id\; \$ & shift\\
 E +    & id\; \$ & shift\\
 E + \underline{id} & \$ & reduce\\
 \underline{E + T}  & \$ & reduce\\
 E      & \$ & accept\\
\end{pilecomm}
\]
\end{texslide}

\begin{texslide}{Remarques Importantes}

\paragraph{Configurations et protophrases:}la concatenation  de la partie gauche
et droite  d'une configuration d'un analyseur  ascendant pour  une grammaire $G$
est toujours une protophrase \emph{droite} de $G$ (si  l'analyse se termine avec
succ\`es).\\

\paragraph{Pr\'efixes viables:} un pr\'efixe viable  peut  toujours se compl\'eter  en
une  protophrase droite. En  d'autre termes, il n'y  a pas d'erreur  au cours de
l'analyse tant que l'on a sur la pile un pr\'efixe viable.
\end{texslide}

\begin{texslide}{Un autre exemple, avec look-ahead}\label{ex:derivright}
\large
Sur la grammaire augment\'ee
\[
  \begin{array}{ccc}
   S  & \rightarrow & E\; \$            \\
   E  & \rightarrow  & T + E \;|\; T       \\
   T  & id \\
  \end{array}
\]
Une possible s\'equence de reconnaissance pour $id + id + id \; \$$ pour un analyseur ascendant serait:
\[
\begin{pilecomm}
            & id + id + id \; \$ & shift\\
 \underline{id}         & + id + id \; \$ & reduce\\
 T          & + id + id \; \$ & shift\\
 T +        & id + id \; \$ & shift\\
 T + \underline{id}     & + id \; \$ & reduce\\
 T + T      & + id \; \$ & shift (\ast)\\
 T + T +    & id \; \$ & shift\\
 T + T + \underline{id} & \; \$ & reduce\\
 T + T + \underline{T}  & \; \$ & reduce (\ast)\\
 T + \underline{T + E}  & \; \$ & reduce\\
 \underline{T + E}      & \; \$ & reduce\\
 E          & \; \$ & accept\\
\end{pilecomm}
\]
\end{texslide}


\begin{texslide}{Analyseurs LR}
Un analyseur LR est compos\'e de
  \begin{description}
    \item[une pile et un flot d'entr\'ee] comme vu dans les exemples \\
    \item[une table d'analyse] qui d\'ecrit un automate \`a \'etats finis
         augment\'e avec des actions \'a effectuer \'eventuellement sur 
         la pile (shift, reduce, accept, error)\\
  \end{description}
L'ex\'ecution de l'automate est cens\'ee d\'ecaler sur la pile des symboles
jusqu'\`a atteindre une pr\'efixe viable maximale (i.e.\ pas extensible \`a
droite, i.e.\ contenant une poign\'ee $\gamma$ en fond \`a droite, i.e.\ en sommet de
pile), puis r\'eduire la poign\'ee en la rempla\c{c}ant avec la partie droite $X$
de la production $X\quad\rightarrow\quad\gamma$ concern\'ee.
\end{texslide}

\begin{texslide}{Fonctionnement d'un analyseur LR}
Sur un \'etat d'analyseur \((\alpha\quad,\quad xw)\) le fonctionnement de
l'analyseur LR est le suivant:
  \begin{itemize}
    \item ex\'ecuter l'automate \`a partir de l'\'etat initial $s_1$ sur la pile $\alpha$,
          ce qui nous laisse sur un \'etat $s_k$ 
    \item ex\'ecuter l'action d\'ecrite dans la table d'analyse associ\'ee au symbole
          terminal  $x$ en entr\'ee pour l'\'etat $s_k$
    \begin{description}
      \item[shift] (not\'e $s$) d\'eplacer le symbole d'entr\'ee $x$ sur la pile, 
      \item[reduce n] (not\'e $rn$) sur le sommet de la pile il y a la partie gauche
                      de la r\`egle num\'ero $n$, disons $X\rightarrow\gamma$;
                      d\'epiler $\gamma$ et empiler $X$
      \item[accept] (not\'e $a$) arr\^eter avec succ\`es
      \item[error] (not\'e par une case vide) arr\^eter sur erreur
    \end{description}
    \item recommencer avec le nouvel \'etat d'analyseur
  \end{itemize}
\end{texslide}

\begin{texslide}{Exemple d'ex\'ecution avec une table d'analyse LALR(1)}
\[
  \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c@{\quad}c@{\qquad\rightarrow\qquad}l}
  0 & S  & E\; \$            &  2 & E  & T                 \\
  1 & E  & T + E             &  3 & T  & id                
  \end{array}
\]
\[
\begin{array}{c|ccc|ccccc|}
  & \multicolumn{3}{|c|}{Action} & \multicolumn{5}{c|}{Transition}\\\hline
  & id & + & \$ & id & + & \$ & E & T\\\hline
1 & s  &   &    & 5  &   &    &  2 & 3\\
2 &    &   &  a &    &   &    &    &  \\
3 &    & s & r2 &    & 4 &    &    &  \\
4 & s  &   &    & 5  &   &    &  6 & 3\\
5 &    & r3& r3 &    &   &    &    &  \\
6 &    &   & r1 &    &   &    &    &  \\\hline
\end{array}
\qquad\qquad
\begin{pilecomm}
 {}_1    & id + id\; \$ & shift\\
 {}_1\underline{id}{}_5 & + id\; \$ & reduce\\
 {}_1T{}_3 & + id\; \$ & shift (\ast)\\
 {}_1T{}_3+{}_4 & id\; \$ & shift\\
 {}_1T{}_3+{}_4 \underline{id}{}_5 & \; \$ & reduce\\
 {}_1T{}_3+{}_4 \underline{T}{}_3  & \; \$ & reduce (\ast)\\
 \underline{{}_1T{}_3+{}_4E{}_6}  & \; \$ & reduce\\
 {}_1E{}_2          & \; \$ & accept\\
\end{pilecomm}
\]
Ici on a marqu\'e en bas les \'etats de l'automate apr\`es lecture de chaque
symbole sur la pile.
\end{texslide}

\begin{texslide}{Analyseur avec \'etats sur la pile}
\Large
Si on garde les \'etats sur la pile, en modifiant la notion de configuration pour
que chaque symbole soit suivi par un \'etat, on peut \'eviter de
relire toute la pile \`a chaque fois: sur une configuration d'analyseur
\((s_1X_1\ldots{}s_{k-1}X_{k-1} s_k\quad,\quad xw)\) le fonctionnement de
l'analyseur LR est le suivant:
  \begin{itemize}
    \item ex\'ecuter l'action d\'ecrite dans la table d'analyse associ\'ee au symbole
          terminal  $x$ en entr\'ee pour l'\'etat $s_k$
    \begin{description}
      \item[shift k] d\'eplacer le symbole d'entr\'ee $x$ sur la pile, et empiler
            l'\'etat num\'ero $k$
      \item[reduce n] sur le sommet de la pile il y a la partie gauche
                      de la r\`egle num\'ero $n$, disons $X\rightarrow\gamma$;
                      d\'epiler $\gamma$ et tous les \'etats associ\'es, en
                      d\'ecouvrant l'\'etat $s'$; empiler $X$ et l'\'etat $s''$
                      contenu dans la table \'a la ligne $s'$, colonne $X$
      \item[accept] arr\^eter avec succ\`es
      \item[error] arr\^eter sur erreur
    \end{description}
    \item recommencer avec le nouvel \'etat d'analyseur
  \end{itemize}
\end{texslide}

\begin{texslide}{Comment produire une table d'analyse?}
Il faut savoir reconna\^{\i}tre les pr\'efixes viables, et savoir d\'eterminer
quelles productions utiliser pour les r\'eductions, \'eventuellement en utilisant
$k$ tokens en entr\'ee pour aider dans la d\'ecision.\\

Pour reconna\^{\i}tre les pr\'efixes viables, on d\'efinit d'abord

\begin{definition}[ITEM LR(k)]
Un \emph{ITEM LR(k)} pour une grammaire $G$ est une production
$X\quad\rightarrow\quad\gamma$ de $G$ plus une position $j$ dans $\gamma$ et une
s\'equence $w$ de longueur $\leq k$. Cela est not\'e, si $\gamma=\alpha\beta$ avec $j$
la longueur de $\alpha$
\[ X\quad\rightarrow\quad\alpha\cdot\beta, w\]
sauf dans le cas LR(0) pour lequel on \'ecrit simplement
\( X\quad\rightarrow\quad\alpha\cdot\beta\)
\end{definition}
L'intuition de \((A\;\rightarrow\;\alpha\cdot\beta,w)\) est
que l'on a d\'ej\`a vu en entr\'ee le pr\'efixe $\alpha$ d'une protophrase et que
l'on attende sur l'entr\'ee une s\'equence d\'erivable \`a partir de $\beta w$.
\end{texslide}

\begin{texslide}{Reconna\^{\i}tre les pr\'efixes viables: la fermeture}
Si on a \((A\quad\rightarrow\quad\alpha\cdot X\beta,z)\), i.e.\ on a
a d\'ej\`a vu en entr\'ee le pr\'efixe $\alpha$ et on attende une 
s\'equence d\'erivable \`a partir de $X\beta z$, on est aussi en condition
d'attendre une s\'equence d\'erivable depuis $X$, suivie d'une s\'equence d\'erivable
depuis $\beta z$. C'est cela que capture la notion suivante de fermeture

\begin{definition}[Fermeture (Closure) LR(k)]\mbox{}
\begin{alltt}
Fermeture(\(I\)) = 
r\'ep\'eter tant que \(I\) grandit
pour tout item \((A\quad\rightarrow\quad\alpha\cdot X\beta,z)\) dans I
  pour toute production \(X\quad\rightarrow\quad\gamma\)
    pour tout \(w\in FIRST_{k}(\beta z)\)
       \(I \leftarrow I \cup \{(X\quad\rightarrow\quad\cdot\gamma,w)\}\)
retourner \(I\)
\end{alltt}
\end{definition}
\end{texslide}
\begin{texslide}{Reconna\^{\i}tre les pr\'efixes viables: GOTO}
\begin{definition}[GOTO]\mbox{}
Supposons d'avoir \((A\quad\rightarrow\quad\alpha\cdot X\beta,z)\), pour un symbole
\emph{terminal ou non terminal} $X$: on a donc d\'ej\`a vu en entr\'ee le pr\'efixe $\alpha$ et on attende une 
s\'equence d\'erivable \`a partir de $X\beta z$. Si maintenant l'on reconna\^{\i}t $X$,
alors on a vu $\alpha X$ et on attende une s\'equence d\'erivable \`a partir de $\beta z$.\\
C'est cela que capture la notion suivante de GOTO
\begin{alltt}
Goto(I,X) = 
\(J\leftarrow \emptyset\)
pour tout item \((A\quad\rightarrow\quad\alpha\cdot X\beta,z)\) dans I
       \(J \leftarrow J \cup \{(X\quad\rightarrow\alpha X\cdot\beta,z)\}\)
retourner Fermeture(J)
\end{alltt}
\end{definition}
\end{texslide}
\begin{texslide}{L'automate qui reconna\^{\i}t les pr\'efixes viables}
Soit   G  un   grammaire  augment\'ee,   et  soit   ${\cal  I}$   la  collection
\(\{s_0;s_1;\ldots{};s_k\}\) d'ensembles d'ITEMS  LR(k) attaignables depuis la fermeture
de l'item \(s_0=(S'\;\rightarrow\;\cdot S\$,\epsilon)\) par la fonction GOTO.\\
On peut alors construire l'automate \`a \'etat fini suivant:
  \begin{description}
    \item[\'etats] \(\{s_0;s_1;\ldots{};s_k\}\) avec $s_0$ \'etat initial et
                comme \'etats finaux ceux qui contiennent au moins un ITEM LR(k)
                avec le point au fond \`a droite (i.e.\ de la forme \((X\rightarrow\gamma\cdot,w)\))
    \item[transitions] on a une transition de l'\'etat $s_i$ vers l'\'etat $s_j$ sur
         le symbole $X$ si $GOTO(s_i,X)=s_j$
  \end{description}
\end{texslide}

\begin{texslide}{La construction de la table LR(k)}
\Large
Soit   G  un   grammaire  augment\'ee,  pour laquelle on a construit l'automate.\\
La table d'analyse a une ligne par \'etat et un colonne par s\'equence de symboles terminaux
de longueur $\leq k$ (le look-ahead) et une colonne par symbole terminal et non-terminal, que
l'on remplit de la fa\c{c}on suivante:\\
Pour tout \'etat $s_i\in {\cal I}$, 
  \begin{itemize}
    \item on met $reduce\;n$ dans la case $s_i, u$ si $(A\rightarrow\beta\cdot,u)\in s_i$
          et $A\rightarrow\beta$ est la production num\'ero $n\geq 1$
    \item on met $accept$ dans la case $s_i, \$$ si $(S'\rightarrow\beta\cdot,\$)\in s_i$
    \item on met $shift$ dans la case $s_i, u$ si $(A\rightarrow\beta_1\cdot\beta_2,v)\in s_i$
          et $u\in EFF_k(\beta_2 v)$ 
    \item on laisse vide (i.e.\ on signale erreur) autrement
  \end{itemize}
\begin{theorem}[fondamental de l'analyse ascendante]
Si une grammaire $G$ est LR(k), alors l'automate construit reconna\^{\i}t les pr\'efixes viables
de $G$ et tout \'etat contenant un ITEM LR(k) de la forme \((X\rightarrow\gamma\cdot,w)\) ne contient
pas un ITEM \((X'\rightarrow\gamma_1\cdot\gamma_2,u)\) avec $w\in EFF_k(\beta_2 v)$.
(en d'autre terme, on n'aura pas dans la table des entr\'ees multiples d\'ecaler
et r\'eduire ou entre deux r\'eductions).
\end{theorem}
\end{texslide}

\begin{texslide}{Comment l'analyseur peut-il choisir l'action \`a effectuer?}
Un analyseur LR dispose de plus d'information qu'un analyseur LL pour d\'eterminer
la prochaine action.\\

Imaginons d'avoir en entr\'ee une cha\^{\i}ne $uvw$, et d'avoir d\'ej\`a lu $u$.
Pour d\'eterminer la production \`a appliquer\\

  \begin{itemize}
    \item un analyseur LL(k) conna\^{\i}t $u$ et FIRST${}_k(vw)$\\
    \item un analyseur LR(k) conna\^{\i}t $uv$ (en effet, il conna\^{\i}t un
          pr\'efixe viable $\gamma$ obtenu \`a partir de $uv$) et FIRST${}_k(w)$\\
  \end{itemize}

\end{texslide}


\begin{texslide}{Un exemple LR(0)}
\large
La grammaire $G~\ref{g:seq}$ suivante est $LR(0)$ 
\begin{equation}\label{g:seq}
\begin{array}{crl@{\qquad}cr@{\quad\rightarrow\quad}l@{\qquad}cr@{\quad\rightarrow\quad}l}
0&S'  \quad\rightarrow\quad& S\; \$ 
               & 1 & S   & ( L )  &  3 & L & S\\
 &    &        & 2 & S   & x      &  4 & L & L,S\\
\end{array}
\end{equation}
Voici la construction compl\`ete de la table LR(0) de $G~\ref{g:seq}$\\
{\bf \'Etats et transitions (2,4,6,7,9 sont terminaux)}
\begin{enumerate}
  \item \(\{
         \lrzitem{S'}{\cdot S\$}, \lrzitem{S}{\cdot (L)}, \lrzitem{S}{\cdot x}
        \}\) \({}\qquad\goto{1}{S}{4} \goto{1}{(}{3}, \goto{1}{x}{2}\)
  \item \(\{
         \lrzitem{S}{x\cdot}
        \}\)
  \item \(\{
         \lrzitem{S}{(\cdot L)}, \lrzitem{L}{\cdot S}, \lrzitem{L}{\cdot L,S}, \lrzitem{L}{\cdot S} \lrzitem{S}{\cdot (L)}, \lrzitem{S}{\cdot x}
        \}\)\\  \({}\qquad \goto{3}{(}{3} \goto{3}{x}{2} \goto{3}{S}{7} \goto{3}{L}{5}\)
  \item \(\{
         \lrzitem{S'}{S\cdot\$}
        \}\)
  \item \(\{
         \lrzitem{S}{(L\cdot)}, \lrzitem{L}{L\cdot ,S}
        \}\) \({}\qquad\goto{5}{)}{6} \goto{5}{,}{8}\)
  \item \(\{
         \lrzitem{S}{(L)\cdot}
        \}\)
  \item \(\{
         \lrzitem{L}{S\cdot}
        \}\)
  \item \(\{
         \lrzitem{L}{L,\cdot S}, \lrzitem{S}{\cdot(L)}, \lrzitem{S}{\cdot x}
        \}\) \({}\qquad\goto{8}{x}{2} \goto{8}{(}{3} \goto{8}{S}{9}\)
  \item \(\{
         \lrzitem{L}{L,S\cdot}
        \}\)
\end{enumerate}
\end{texslide}
\begin{texslide}{La table d'analyse LR(0)}
\Large
Pour remplir la table LR(0), on \'ecrit la table de transition de l'automate
et on introduit les actions de d\'ecalage ($s$ pour $shift$) comme d\'ecrit plus
en haut.\\
Pour les r\'eductions ($rk$ pour \emph{$reduce$ avec la production $k$}), n'ayant
pas de look-ahead dans les \'etats, on met $rk$ dans toute la ligne action de
l'\'etat $j$ si l'\'etat $j$ contient un ITEM LR(0) $X\rightarrow\gamma\cdot$,
et que $X\rightarrow\gamma$ est la production num\'ero $j$.
\[
\begin{array}{c|c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}|c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}|}
  & \multicolumn{5}{|c|}{Action} & \multicolumn{7}{c|}{Transition}\\\hline
  & (  & ) & x  & ,  & \$& (  & ) & x  & ,  & \$& S  & L    \\\hline
1 &  s &   & s  &    &   & 3  &   &  2 &    &   &  4 &      \\
2 & r2 & r2& r2 & r2 &r2 &    &   &    &    &   &    &      \\
3 &  s &   & s  &    &   & 3  &   &  2 &    &   &  7 &  5   \\
4 &    &   &    &    & a &    &   &    &    &   &    &      \\
5 &    & s &    & s  &   &    & 6 &    &  8 &   &    &      \\
6 & r1 & r1& r1 & r1 &r1 &    &   &    &    &   &    &      \\
7 & r3 & r3& r3 & r3 &r3 &    &   &    &    &   &    &      \\
8 &  s &   & s  &    &   & 3  &   &  2 &    &   &  9 &      \\
9 & r4 & r4& r4 & r4 &r4 &    &   &    &    &   &    &      \\\hline
\end{array}
\]
\end{texslide}
\begin{texslide}{La table d'analyse LR(0), versions compacte}
\large
\paragraph{Remarque}Les g\'en\'erateurs d'analyseurs, comme Yacc, fusionnent les colonnes des actions
et des transitions pour les terminaux: plut\^ot que d'avoir une case case $(1,x)$ 
qui contient $s$(hift) pour les actions, et une case $(1,x)$ qui contient $2$
pour les transitions, on pr\'ef\`ere avoir une seule case $(1,x)$ qui contient $s2$,
pour ``l'action est un shift et la transition est vers l'\'etat $2$''.\\
Dans ce cas, on \'ecrit souvent $gk$ dans les colonnes transitions restantes
(celles des non-terminaux). C'est une abr\'eviation pour ``goto $k$'',
plus lisible que juste $k$.
\[
\begin{array}{c|c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}|c@{\quad}c@{\quad}|}
  & \multicolumn{5}{|c|}{Action} & \multicolumn{2}{c|}{Transition}\\\hline
  & (  & ) & x  & ,  & \$& S  & L    \\\hline
1 & s3 &   & s2 &    &   & g4 &      \\
2 & r2 & r2& r2 & r2 &r2 &    &      \\
3 & s3 &   & s2 &    &   & g7 & g5   \\
4 &    &   &    &    & a &    &      \\
5 &    & s6&    & s8 &   &    &      \\
6 & r1 & r1& r1 & r1 &r1 &    &      \\
7 & r3 & r3& r3 & r3 &r3 &    &      \\
8 & s3 &   & s2 &    &   & g9 &      \\
9 & r4 & r4& r4 & r4 &r4 &    &      \\\hline
\end{array}
\]
\end{texslide}
\begin{texslide}{Un exemple LR(1) non LR(0)}
\Large
La grammaire $G~\ref{g:sommes}$
\begin{equation}\label{g:sommes}
  \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c@{\quad}c@{\qquad\rightarrow\qquad}l}
  0 & S  & E\; \$            &  2 & E  & T                 \\
  1 & E  & T + E             &  3 & T  & id                \\
  \end{array}
\end{equation}

est une grammaire $LR(1)$ mais pas $LR(0)$.\\
En effet, dans l'automate on a un probl\`eme pour l'\'etat
\(\{\lrzitem{E}{T\cdot+E},\lrzitem{E}{T\cdot} \}\).
\[
\diagram
\lrstate{1}{
         \slritem{S}{\cdot E\$}\\
         \slritem{S}{\cdot T+E}\\
         \slritem{E}{\cdot T}\\
         \slritem{T}{\cdot id}
}
\dto_(.7){E}\drto_{id}\rto_(.5){T}
&
\lrstate{3}{
         \textcolor{red}{\slritem{E}{{T\cdot +E}}}\\
         \textcolor{red}{\slritem{E}{{T\cdot}}}
}
\rto<1ex>^(.5){+}
& 
\lrstate{4}{
         \slritem{E}{T+\cdot E}\\
         \slritem{E}{\cdot T+ E}\\
         \slritem{E}{\cdot T}\\
         \slritem{T}{\cdot id}
}
\lto<1ex>^(.5){T}
\dto_(.70){E}
\dlto_(.55){id}
\\
\lrstate{2}{
         \slritem{S}{E\cdot \$}
}
&
\lrstate{5}{
         \slritem{T}{id\cdot}
}
&
\lrstate{6}{
         \slritem{E}{T+E\cdot}
}
\\
\enddiagram
\]
\end{texslide}
\begin{texslide}{Un exemple LR(1) non LR(0) (suite)}
Donc dans la table d'analyse $LR(0)$ on trouve un conflit $shift/reduce$ dans la
case $3,+$
\[
\begin{array}{c|c@{\quad}c@{\quad}c@{\quad}|c@{\quad}c|}
  & \multicolumn{3}{|c|}{Action} & \multicolumn{2}{c|}{Transition}\\\hline
  &  + & id& \$ & \quad E  & T  \\\hline
1 &    & s5&    & \quad g2 & g3 \\
2 &    &   & a  &    &    \\
3 &  \framebox{\textcolor{red}{r2,s4}}& r2& r2 &    &   \\
4 &    & s7&    & \quad g6 & g3 \\
5 &  r3& r3& r3 &    &    \\
6 &  r1& r1& r1 &    &    \\\hline
\end{array}
\]
\end{texslide}
\begin{texslide}{Les \'etats LR(1) de $G~\ref{g:sommes}$}
Regardons alors la construction LR(1), qui garde trace des look-aheads dans les \'etats\ldots{}
\vfill
\large
{\bf \'Etats et transitions (2, 5 et 6 sont terminaux)}
\vfill
\[
\diagram
\lrstate{1}{
         \lroitem{S}{\cdot E\$}{\epsilon}\\
         \lroitem{S}{\cdot T+E}{\$}\\
         \lroitem{E}{\cdot T}{\$}\\
         \lroitem{T}{\cdot id}{+}\\
         \lroitem{T}{\cdot id}{\$}
}
\dto_(.7){E}\drto_{id}\rto_(.55){T}
&
\lrstate{3}{
         \lroitem{E}{T\cdot +E}{\$}\\
         \lroitem{E}{T\cdot}{\$}
}
\rto<1ex>^(.5){+}
& 
\lrstate{4}{
         \lroitem{E}{T+\cdot E}{\$}\\
         \lroitem{E}{\cdot T+ E}{\$}\\
         \lroitem{E}{\cdot T}{\$}\\
         \lroitem{T}{\cdot id}{\$}
}
\lto<1ex>^(.5){T}
\dto_(.6){E}
\dlto_(.55){id}
\\
\lrstate{2}{
         \lroitem{S}{E\cdot \$}{\epsilon}
}
&
\lrstate{5}{
         \lroitem{T}{id\cdot}{+}\\
         \lroitem{T}{id\cdot}{\$}
}
&
\lrstate{6}{
         \lroitem{E}{T+E\cdot}{\$}
}
\\
\enddiagram
\]
\end{texslide}
\begin{texslide}{Comparons les automates LR(0) et LR(1) pour $G~\ref{g:sommes}$}
\normalsize
\[
LR(0)\qquad \diagram
\lrstate{1}{
         \slritem{S}{\cdot E\$}\\
         \slritem{S}{\cdot T+E}\\
         \slritem{E}{\cdot T}\\
         \slritem{T}{\cdot id}
}
\dto_(.7){E}\drto_{id}\rto_(.5){T}
&
\lrstate{3}{
         \textcolor{red}{\slritem{E}{{T\cdot +E}}}\\
         \textcolor{red}{\slritem{E}{{T\cdot}}}
}
\rto<1ex>^(.5){+}
& 
\lrstate{4}{
         \slritem{E}{T+\cdot E}\\
         \slritem{E}{\cdot T+ E}\\
         \slritem{E}{\cdot T}\\
         \slritem{T}{\cdot id}
}
\lto<1ex>^(.5){T}
\dto_(.70){E}
\dlto_(.55){id}
\\
\lrstate{2}{
         \slritem{S}{E\cdot \$}
}
&
\lrstate{5}{
         \slritem{T}{id\cdot}
}
&
\lrstate{6}{
         \slritem{E}{T+E\cdot}
}
\\
\enddiagram
\]
\[
LR(1)\qquad \diagram
\lrstate{1}{
         \lroitem{S}{\cdot E\$}{\epsilon}\\
         \lroitem{S}{\cdot T+E}{\$}\\
         \lroitem{E}{\cdot T}{\$}\\
         \lroitem{T}{\cdot id}{+}\\
         \lroitem{T}{\cdot id}{\$}
}
\dto_(.7){E}\drto_{id}\rto_(.55){T}
&
\lrstate{3}{
         \lroitem{E}{T\cdot +E}{\$}\\
         \lroitem{E}{T\cdot}{\$}
}
\rto<1ex>^(.5){+}
& 
\lrstate{4}{
         \lroitem{E}{T+\cdot E}{\$}\\
         \lroitem{E}{\cdot T+ E}{\$}\\
         \lroitem{E}{\cdot T}{\$}\\
         \lroitem{T}{\cdot id}{\$}
}
\lto<1ex>^(.5){T}
\dto_(.6){E}
\dlto_(.55){id}
\\
\lrstate{2}{
         \lroitem{S}{E\cdot \$}{\epsilon}
}
&
\lrstate{5}{
         \lroitem{T}{id\cdot}{+}\\
         \lroitem{T}{id\cdot}{\$}
}
&
\lrstate{6}{
         \lroitem{E}{T+E\cdot}{\$}
}
\\
\enddiagram
\]
\end{texslide}
\begin{texslide}{La table d'analyse LR(1) de $G~\ref{g:sommes}$}
On garde trace des look-ahead pour introduire dans la table les actions
\emph{reduce}, donc il y en a moins et le conflit dispara\^{\i}t!
\vfill
\[
\begin{array}{c|ccc|cccccc|}
  & \multicolumn{3}{|c|}{Action} & \multicolumn{6}{c|}{Transition}\\\hline
  &  + & id& \$ & + & id& \$ & E  & T & \\\hline
1 &    & s &    &   & 5 &    & 2  & 3 & \\
2 &    &   & a  &   &   &    &    &   & \\
3 &  s &   & r2 & 4&    &    &    &   & \\
4 &    & s &    &   & 5 &    & 6  & 3 & \\
5 &  r3&   & r3 &   &   &    &    &   & \\
6 &    &   & r1 &   &   &    &    &   & \\\hline
\end{array}
\]
\end{texslide}
\begin{texslide}{La table d'analyse LR(1) de $G~\ref{g:sommes}$, version compacte}
\[
\begin{array}{c|c@{\quad}c@{\quad}c|c@{\quad}c@{\quad}|}
  & \multicolumn{3}{|c|}{Action} & \multicolumn{2}{c|}{Transition}\\\hline
  &  + & id& \$ & \quad E  & T \\\hline
1 &    & s5&    & \quad g2 & g3\\
2 &    &   & a  &    &   \\
3 &  s4&   & r2 &    &   \\
4 &    & s5&    & \quad g6 & g3\\
5 &  r3&   & r3 &    &   \\
6 &    &   & r1 &    &   \\\hline
\end{array}
\]
\end{texslide}
\begin{texslide}{Comparons les tables LR(0) et LR(1) pour $G~\ref{g:sommes}$}
\large
\[
\begin{array}{c@{\qquad}c}
LR(0) & LR(1) \\
\begin{array}{c|c@{\quad}c@{\quad}c@{\quad}|c@{\quad}c|}
  & \multicolumn{3}{|c|}{Action} & \multicolumn{2}{c|}{Transition}\\\hline
  &  + & id& \$ & \quad E  & T  \\\hline
1 &    & s5&    & \quad g2 & g3 \\
2 &    &   & a  &    &    \\
3 &  \framebox{\textcolor{red}{r2,s4}}& r2& r2 &    &   \\
4 &    & s7&    & \quad g6 & g3 \\
5 &  r3& r3& r3 &    &    \\
6 &  r1& r1& r1 &    &    \\\hline
\end{array}
& \begin{array}{c|c@{\quad}c@{\quad}c@{\quad}|c@{\quad}c|}
  & \multicolumn{3}{|c|}{Action} & \multicolumn{2}{c|}{Transition}\\\hline
  &  + & id& \$ & \quad E  & T  \\\hline
1 &    & s5&    & \quad g2 & g3 \\
2 &    &   & a  &    &    \\
3 &  s4&   & r2 &    &   \\
4 &    & s5&    & \quad g6 & g3 \\
5 &  r3&   & r3 &    &    \\
6 &    &   & r1 &    &    \\\hline
\end{array}
\\
\end{array}
\]
\end{texslide}
\begin{texslide}{Trouver sa place parmi les LR(k)}
Comme nous  venons de voir,  la classe d'analyseurs  LR(0) est trop  faible pour
traiter les langages de programmations: m\^eme le simple langage des expressions
pose probl\`eme.\\

Les  classes LR(2),  LR(3), \ldots{}  ont par  contre une  table  d'analyse trop
grosse en  pratique en raison du  nombre de colonnes pour  le ``look-ahead'': un
analyseur  moderne utilise  plusieurs dizaines  de tokens,  et une  colonne pour
chaque s\'equence de  token de longueur inf\'erieur ou \'egale  \`a $k$, pour $k\geq
2$ est d\'eraisonnable.\\

{\bf Exercice}: combien de s\'equences de longueur inf\'erieure ou \'egale \`a $k$
y-at-il si on se donne $n$ tokens diff\'erents?\\
\end{texslide}

\begin{texslide}{Trouver sa place entre LR(0) et LR(1)}
Heureusement,  la  classe  LR(1)  est  largement suffisante  pour  les  langages
modernes, et  la table n'a qu'\emph{une  colonne} par token.\\  Mais l\`a, c'est
\emph{le  nombre d'\'etats}  qui  grandit trop,  en  raisons de  la pr\'esence  de
look-ahead dans les \'etats qui d\'epartage des \'etats qui sont tr\`es peu
diff\'erents. 

C'est pour cela que dans la pratique on utilise deux types d'analyseurs dont la
puissance est comprise entre celle de LR(0) et celle de LR(1): SLR et LALR(1)
\end{texslide}
\begin{texslide}{Analyseurs SLR}
  \begin{description}
    \item[SLR] (Simple LR) est un analyseur dont l'automate est celui de
         LR(0),  donc la  partie  transition est  la  m\^eme que  LR(0), et  les
         actions de d\'ecalage aussi, mais  la table d'analyse est construite de
         une fa\c{c}on plus fine: on pallie \`a l'absence de look-ahead dans les
         \'etat avec l'information contenue dans les ensembles FOLLOW construits
         \`a partir  de la grammaire.\\  La r\`egle de placement  des r\'eductions
         devient alors:\\
    \begin{quote}
             si l'\'etat $j$ contient un ITEM LR(0) $X\rightarrow\gamma\cdot$,
             et que $X\rightarrow\gamma$ est la production num\'ero $j\geq 1$, on met 
             $rk$ dans toutes les cases $(j,t)$ telles que $t\in FOLLOW(X)$.
    \end{quote}
  \end{description}
\end{texslide}
\begin{texslide}{SLR pour la grammaire G~\ref{g:sommes}}
L'automate SLR \'etant le m\^eme que celui LR(0), on ne le montrera pas \`a
nouveau, mais maintenant la table SLR contiendra des entr\'ees \emph{reduce}
seulement sur certains nonterminaux, pas tous! En particulier, on pourra \'eviter
le conflit $shift/reduce$ dans l'\'etat \(\{\lrzitem{E}{T\cdot+E},\lrzitem{E}{T\cdot} \}\).\\
\[
\begin{array}{c|c@{\quad}c@{\quad}c@{\quad}|c@{\quad}c|}
  & \multicolumn{3}{|c|}{Action} & \multicolumn{2}{c|}{Transition}\\\hline
  &  + & id& \$ & \quad E  & T  \\\hline
1 &    & s5&    & \quad g2 & g3 \\
2 &    &   & a  &    &    \\
3 &  s4&   & r2 &    &   \\
4 &    & s5&    & \quad g6 & g3 \\
5 &  r3&   & r3 &    &    \\
6 &    &   & r1 &    &    \\\hline
\end{array}
\]
Dans ce cas pr\'ecis, SLR fait aussi bien que LR(1), avec bien moins d'effort.
\end{texslide}
\begin{texslide}{Analyseurs LALR(1)}
  \begin{description}
    \item[LALR(1)] (\emph{Look-Ahead LR(1)}) est une classe d'analyseurs dont
         l'automate est obtenu de l'automate  LR(1) en  \emph{fusionnant} les
         \'etats  qui diff\`erent seulement  par leur  look-ahead. 
  \end{description}

On dit  aussi que  l'on fusionne  les \'etats ayant  le m\^eme  \emph{coeur}, le
coeur d'un \'etat  \'etant l'ensemble des parties gauches  des ITEMS LR(1) qu'il
contient, i.e.\  sans le  look-ahead, i.e.\ des  ITEMS LR(0).\\
Donc  un analyseur LALR(1) a autant d'\'etats qu'un LR(0) ou SLR.\\

Les analyseurs LALR(1) sont les plus utilis\'es parce que, m\^eme s'ils ont moins
d'\'etats qu'un analyseur LR(1), il est tr\`es rare qu'on retrouve un conflit
dans la table LALR(1) quand il n'y en a pas dans la table LR(1).\\
En particulier, on peut prouver que si un analyseur LR(1) n'a pas de conflits
\emph{shift/reduce}, l'analyseur LALR(1) n'en a pas non plus.\\
Par contre, on peut introduire des conflits \emph{reduce/reduce}.
\end{texslide}
\begin{texslide}{LALR(1) pour $G~\ref{g:sommes}$}
Dans le cas pr\'ecis de cette grammaire, l'automate LR(1) pour $G~\ref{g:sommes}$ n'ayant pas 
d'\'etats diff\'erents avec le m\^eme coeur, la table d'analyse LALR(1) de
$G~\ref{g:sommes}$ est la m\^eme que celle LR(1).

\vcentershabox{Mais  la  grammaire suivante,  qui  capture  un sous-ensemble  des
expressions du langage C, est un  exemple de grammaire LALR(1) qui n'est pas SLR
et pour laquelle l'automate LALR(1) est plus petit que l'automate LR(1).}

  \begin{equation}\label{g:cref}
  \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c@{\quad}c@{\qquad\rightarrow\qquad}l}
  0 & S'  & S\; \$            &  3 & E  & V                 \\
  1 & S   & V = E             &  4 & V  & id                \\
  2 & S   & E                 &  5 & V  & * E               \\
  \end{array}
  \end{equation}

\end{texslide}
\begin{texslide}{LR pr\'ef\`ere l'associativit\'e \`a gauche}
Contrairement \`a ce qui se passe dans le cas des analyseurs LL, 
dans l'analyse ascendante on a plut\^ot int\'er\^et \`a utiliser des grammaires
r\'ecursives \`a gauche.\\

Consid\'erons les analyseurs LR pour la grammaire r\'ecursive \`a droite

\[
  \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c@{\quad}c@{\qquad\rightarrow\qquad}l}
   & S  & E\; \$            &   & E  & T                 \\
   & E  & T + E             &   & T  & id                \\
  \end{array}
\]

vus en cours: pour reconna\^{\i}tre \(id+id+\ldots{}+id\$\), ils empilent toute la suite
de symboles (en r\'eduisant $id$ sur $T$ \`a chaque coup) avant de faire la pr\'emi\`ere reduction
non triviale.\\
Par contre, la grammaire recursive \`a gauche

\[
  \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c@{\quad}c@{\qquad\rightarrow\qquad}l}
   & S  & E\; \$            &   & E  & T                 \\
   & E  & E + T             &   & T  & id                \\
  \end{array}
\]

mantiendra la dimension de la pile \`a un minimum.\\
\end{texslide}
\begin{texslide}{Utilisation de grammaires ambigu\"es}
Une grammaire ambigu\"e n'est jamais LR(k), quelque soit $k$.\\
Pourtant, on a int\'er\^et \`a essayer d'utiliser une grammaire ambigu\"e,
quitte \`a trafiquer l'automate $LR(k)$, si on peut.\\

  \begin{description}
    \item[efficacit\'e] dans une grammaire obt\'enue par d\'esambiguation,
         l'analyseur passe beaucoup de temps \`a reduire des productions
         triviales (comme $E\rightarrow T$ dans l'exemple pr\'ec\'edent),
         dont le seul but \'etait d'expliciter \emph{dans la grammaire}
         les priorit\'es entre op\'erateurs et leur associativit\'e droite ou gauche.
    \item[praticit\'e] si on peut d\'ecrire de fa\c{c}on concise 
         ces priorit\'es entre op\'erateurs et leur associativit\'e droite ou gauche,
         sans toucher \`a la grammaire, on obtient une description plus modulaire
         du langage qui nous int\'eresse.
  \end{description}
\end{texslide}
\begin{texslide}{Exemple}
Consid\'erons la grammaire (ambigu\"e) suivante:
\[
  \begin{array}{c@{\qquad\rightarrow\qquad}l}
    S  & E\; \$  \\
    E  & E * E \\
    E  & E + E \\  
    E  & id 
  \end{array}
\]
et sa table d'analyse SLR.\\

Voyons comment les nombreux conflits apparents peuvent s'expliquer
en terme d'associativit\'e et pr\'ecedence d'op\'erateurs, que l'on
peut r\'esoudre \emph{en travaillant directement sur les entr\'ees de la table}\ldots{}\\

(fait au tableau, pas dans les notes... si un ame gentille veut tout taper...)
\end{texslide}
\end{document}


