%%
% lr.tex
% LR parsing
%
%% Document class choice
\documentclass[a4paper]{article}\usepackage{beamerarticle}
%\documentclass[ignorenonframetext]{beamer}

%% Packages
\usepackage[latin1]{inputenc}
\usepackage{xspace}
\usepackage[english,francais]{babel}
\usepackage{beamerfrench}
\usepackage{macros}
\usepackage{amssymb}

%% Meta information
\title{Analyse LR}
\institute{Université de Nice Sophia Antipolis}
\date{2005/2006}
  \refstepcounter{part}

\mode<presentation>{
  \definecolor{nightblue}{rgb}{0.1,0.1,0.4}
  \setbeamercolor{structure}{fg=nightblue}

  \setbeamercolor*{palette primary}
                  {use=structure,fg=white,bg=structure.fg}
  \setbeamercolor*{palette secondary}
                  {use=structure,fg=white,bg=structure.fg}
  \setbeamercolor*{palette tertiary}
                  {use=structure,fg=white,bg=structure.fg}
  \setbeamercolor*{palette quaternary}
                  {use=structure,fg=white,bg=structure.fg}

%%   \setbeamercolor*{frametitle}{parent=palette primary}
%%   \setbeamercolor{block title}{parent=palette primary}
%%   \setbeamercolor{block title alerted}
%%                  {use=alerted text,fg=white,bg=alerted text.fg}
%%   \setbeamercolor{block title example}
%%                  {use=example text,fg=white,bg=example text.fg}

%%   \setbeamercolor{block body}
%%                  {parent=normal text,use=block title,bg=block title.bg!10!bg}
%%   \setbeamercolor{block body alerted}
%%                  {parent=normal text,use=block title alerted,
%%                    bg=block title alerted.bg!10!bg}
%%   \setbeamercolor{block body example}
%%                  {parent=normal text,use=block title example,
%%                    bg=block title example.bg!10!bg}

%%   \useinnertheme{inmargin}
  \useoutertheme{infolines}
  \setbeamercolor{item projected}{fg=black}

  \renewenvironment{equation}{\begin{equation*}}{\end{equation*}}
  \def\shadesb<#1>{%
    \temporal<#1>{\color{black}}{\color{black}}{\color{black!50}}}
  \def\shades<#1>{%
    \temporal<#1>{\color{black!50}}{\color{black}}{\color{black!50}}}
  \def\colorize<#1>{%
    \temporal<#1>{\color{black!50}}{\color{red}}{\color{black}}}
  \def\colorizeb<#1>{%
    \temporal<#1>{\color{black}}{\color{red}}{\color{black!50}}}
  \renewcommand{\emph}[1]{{\color{red} #1}}
}
\mode<article>{
  \usepackage{graphicx}
  \usepackage{vmargin}
  \def\shadesb<#1>{}
  \def\shades<#1>{}
  \def\colorize<#1>{}
  \def\colorizeb<#1>{}
  \renewcommand{\part}{\title}
  \renewcommand{\partpage}{\maketitle}
}

%% Document
\begin{document}

\part{Analyse LR}
\frame{\partpage}

\section{Rappels}

\subsection{Le problème}

\begin{frame}
  \frametitle{Génératif vers recognitif}
  Rappels du cours précédent~:
  \begin{itemize}
    \colorize<2>\item Syntaxe formalisée par une grammaire algébrique $\G=\tup{N,\Sigma,P,S}$.
    \colorize<3>\item Construction automatique d'un automate à pile ${\cal A}=\tup{Q,\Sigma,R,\f_s,F,\$,\|}$ pour $\G$.
  \end{itemize}
  \uncover<4>{Une solution~: l'automate à pile récursif descendant.}
\end{frame}

\begin{frame}
  \frametitle{Analyseur descendant}
  \begin{fdefinition}
    L'\define{analyseur récursif descendant} pour une grammaire
    algébrique $\G=\tup{N,\Sigma,P,S}$ est un automate à pile ${\cal
    A}_\text{desc}=\tup{Q,\Sigma,R,\f_s,F,\$,\|}$ où
    \begin{itemize}
      \colorize<2>\item $Q$ est l'ensemble des production pointées de
      $P'$, notées\mode<presentation>{\vspace{-1em}}
      \begin{equation}
        [A\P\a\p\a']\text{ si }A\P\a\a'\in P',
      \end{equation}\mode<presentation>{\vspace{-2em}}
      \colorize<3>\item $R$ est l'ensemble des règles\mode<presentation>{\vspace{-2em}}
      \begin{align*}
        [A\P\a\p B\a']\|&\vd{predict}[A\P\a B\p\a'][B\P\p\b]\|,\\
        [A\P\a\p a\a']\|a&\vd{match}[A\P\a a\p\a']\|,\\
        [A\P\a\p]\|&\vdash\|,
      \end{align*}\mode<presentation>{\vspace{-2em}}
      \colorize<4>\item $\f_s=[S'\P\p S\$]$,
      \colorize<5>\item $F=\{[S'\P S\p\$]\}$.
    \end{itemize}
  \end{fdefinition}
\end{frame}

\begin{frame}
  \frametitle{Analyse descendante}
  \begin{exemple}\mode<presentation>{
    \only<1>{\begin{center}\includegraphics{../fig/artiste_Dl1_fig}\end{center}}
    \only<2>{\begin{center}\includegraphics{../fig/artiste_Dl2_fig}\end{center}}
    \only<3>{\begin{center}\includegraphics{../fig/artiste_Dl3_fig}\end{center}}
    \only<4>{\begin{center}\includegraphics{../fig/artiste_Dl4_fig}\end{center}}
    \only<5>{\begin{center}\includegraphics{../fig/artiste_Dl5_fig}\end{center}}
    \only<6>{\begin{center}\includegraphics{../fig/artiste_Dl5b_fig}\end{center}}
    \only<7>{\begin{center}\includegraphics{../fig/artiste_Dl6_fig}\end{center}}
    \only<8>{\begin{center}\includegraphics{../fig/artiste_Dl7_fig}\end{center}}
    \only<9>{\begin{center}\includegraphics{../fig/artiste_Dl8_fig}\end{center}}
    \only<10>{\begin{center}\includegraphics{../fig/artiste_Dl9_fig}\end{center}}
    \only<11>{\begin{center}\includegraphics{../fig/artiste_Dl10_fig}\end{center}}
    \only<12->{\begin{center}\includegraphics{../fig/artiste_Dl10b_fig}\end{center}}}
    \begin{align*}
      \only<1>{&\$[S'\P\p\text{Ph }\$]\|\text{Det N V Det N}\$\\}
      \only<2>{\rewrt{predict}~&\$[S'\P\text{{\color{red}Ph}}\p\$][\text{Ph}\P\p\text{SN
            SV}]\|\text{Det N V Det N}\$\\}
      \only<3>{\rewrt{predict}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{{\color{red}SN}}\p
              \text{SV}][\text{SN}\P\p\text{Det N}]\|\text{Det N V Det N}\$\\}
      \only<4>{\rewrt{match}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN}\p
              \text{SV}][\text{SN}\P\text{{\color{red}Det}}\p\text{N}]\|\text{N V Det N}\$\\}
      \only<5>{\rewrt{match}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN}\p
              \text{SV}][\text{SN}\P\text{Det {\color{red}N}}\p]\|\text{V Det N}\$\\}
      \only<6>{\models~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN}\p
              \text{SV}]\|\text{V Det N}\$\\}
      \only<7>{\rewrt{predict}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN
        {\color{red}SV}}\p][\text{SV}\P\p\text{V SN}]\|\text{V Det N}\$\\}
      \only<8>{\rewrt{match}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN SV}\p][\text{SV}\P\text{{\color{red}V}}\p\text{SN}]\|\text{Det N}\$\\}
      \only<9>{\rewrt{predict}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN SV}\p][\text{SV}\P\text{V {\color{red}SN}}\p][\text{SN}\P\p\text{Det N}]\|\text{Det N}\$\\}
      \only<10>{\rewrt{match}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN SV}\p][\text{SV}\P\text{V SN}\p][\text{SN}\P\text{{\color{red}Det}}\p\text{N}]\|\text{N}\$\\}
      \only<11>{\rewrt{match}~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN
        SV}\p][\text{SV}\P\text{V SN}\p][\text{SN}\P\text{Det {\color{red}N}}\p]\|\$\\}
      \only<12>{\models~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN SV}\p][\text{SV}\P\text{V SN}\p]\|\$\\}
      \only<13>{\models~&\$[S'\P\text{Ph}\p\$][\text{Ph}\P\text{SN SV}\p]\|\$\\}
      \only<14>{\models~&\$[S'\P\text{Ph}\p\$]\|\$}
    \end{align*}
  \end{exemple}
\end{frame}

\begin{frame}
  \frametitle{Faiblesses de l'analyse descendante}
  \begin{enumerate}
    \colorize<1>\item L'automate à pile est non déterministe~; il nécessite un
    \textit{backtrack} coûteux~;
    \colorize<2>\item l'ensemble de règles $R$ permet des règles de la forme
    $[A\P\p A\a]\|\vd{predict}[A\P A\p\a][A\P\p A\a]\|$ si la grammaire est
    récursive gauche.
  \end{enumerate}
  \uncover<3->{Le non-déterminisme est lié aux conflits entre deux
  règles \textit{predict}.}
  \uncover<4>{Quelles autres possibilités s'offrent à nous~?}
\end{frame}

\section{Analyse ascendante}

\subsection{Automate à pile ascendant}

\begin{frame}
  \frametitle{Dérivations droites}
  \begin{exemple}
    \uncover<1-5>{Lors d'une dérivation droite~:}
    \only<1>{\begin{center}\includegraphics{../fig/artiste_Dr1_fig}\end{center}}
    \only<2>{\begin{center}\includegraphics{../fig/artiste_Dr2_fig}\end{center}}
    \only<3>{\begin{center}\includegraphics{../fig/artiste_Dr3_fig}\end{center}}
    \only<4-5>{\begin{center}\includegraphics{../fig/artiste_Dr4_fig}\end{center}}
    \only<6>{\begin{center}\includegraphics{../fig/artiste_a0_fig}\end{center}}
    \only<7>{\begin{center}\includegraphics{../fig/artiste_a1_fig}\end{center}}
    \only<8>{\begin{center}\includegraphics{../fig/artiste_a2_fig}\end{center}}
    \only<9>{\begin{center}\includegraphics{../fig/artiste_a3_fig}\end{center}}
    \only<10>{\begin{center}\includegraphics{../fig/artiste_a4_fig}\end{center}}
    \only<11>{\begin{center}\includegraphics{../fig/artiste_a5_fig}\end{center}}
    \only<12>{\begin{center}\includegraphics{../fig/artiste_a6_fig}\end{center}}
    \only<13>{\begin{center}\includegraphics{../fig/artiste_a7_fig}\end{center}}
    \only<14>{\begin{center}\includegraphics{../fig/artiste_a8_fig}\end{center}}
    \only<15>{\begin{center}\includegraphics{../fig/artiste_a9_fig}\end{center}}
  \end{exemple}
  \uncover<5->{Et si on inverse la relation~: si on évalue $\Dr^{-1}$
    depuis la chaîne terminale~?}
\end{frame}
  
\begin{frame}
  \frametitle{Analyseur ascendant}
  \begin{fdefinition}
    L'\define{analyseur ascendant} pour une grammaire
    algébrique $\G=\tup{N,\Sigma,P,S}$ est un automate à pile ${\cal
    A}_\text{asc}=\tup{V,\Sigma,R,\f_s,F,\$,\|}$ où
    \begin{itemize}
      \colorize<2>\item $R$ est l'ensemble des
      règles\mode<presentation>{\vspace{-2em}}
      \begin{align*}
        %% {\colorize<2>
          \a\|&\red{A\P\a}A\|,\\%}
        %% {\colorize<3>
          \|a&\shift a\|,\\%}
      \end{align*}\mode<presentation>{\vspace{-2em}}
      \colorize<3>\item $\f_s=\e$,
      \colorize<4>\item $F=\{S\}$.
    \end{itemize}
  \end{fdefinition}
  \uncover<5->{%
  \begin{fdefinition}
    Le \define{transducteur ascendant} $\tup{{\cal A},\t}$ est défini
    par\mode<presentation>{\vspace{-2em}}
    \begin{align*}
      %% {\colorize<7>
        \t(\a\|\red{A\P\a}A\|)&=A\P\a,\\%}
      %% {\colorize<8>
        \t(\|a\shift a\|)&=\e.\\%}
    \end{align*}
  \end{fdefinition}}
\end{frame}

\begin{frame}
  \frametitle{Analyse ascendante}
  \begin{exemple}\mode<presentation>{
    \only<1>{\begin{center}\includegraphics{../fig/artiste_a0_fig}\end{center}}
    \only<2>{\begin{center}\includegraphics{../fig/artiste_a1_fig}\end{center}}
    \only<3>{\begin{center}\includegraphics{../fig/artiste_a2_fig}\end{center}}
    \only<4>{\begin{center}\includegraphics{../fig/artiste_a3_fig}\end{center}}
    \only<5>{\begin{center}\includegraphics{../fig/artiste_a4_fig}\end{center}}
    \only<6>{\begin{center}\includegraphics{../fig/artiste_a5_fig}\end{center}}
    \only<7>{\begin{center}\includegraphics{../fig/artiste_a6_fig}\end{center}}
    \only<8>{\begin{center}\includegraphics{../fig/artiste_a7_fig}\end{center}}
    \only<9>{\begin{center}\includegraphics{../fig/artiste_a8_fig}\end{center}}
    \only<10>{\begin{center}\includegraphics{../fig/artiste_a9_fig}\end{center}}}
    \begin{align*}
      \only<1>{&\$\|\text{Det N V Det N}\$\\}
      \only<2>{\rewrt{shift}~&\$\text{{\color{red} Det}}\|\text{N V Det N}\$\\}
      \only<3>{\rewrt{shift}~&\$\text{Det {\color{red}N}}\|\text{V Det N}\$\\}
      \only<4>{\rewr{\text{SN}\P\text{Det N}}~&\$\text{{\color{red}SN}}\|\text{V Det N}\$\\}
      \only<5>{\rewrt{shift}~&\$\text{SN {\color{red}V}}\|\text{Det N}\$\\}
      \only<6>{\rewrt{shift}~&\$\text{SN V {\color{red}Det}}\|\text{N}\$\\}
      \only<7>{\rewrt{shift}~&\$\text{SN V Det {\color{red}N}}\|\$\\}
      \only<8>{\rewr{\text{SN}\P\text{Det N}}~&\$\text{SN V {\color{red}SN}}\|\$\\}
      \only<9>{\rewr{\text{SV}\P\text{V SN}}~&\$\text{SN {\color{red}SV}}\|\$\\}
      \only<10>{\rewr{\text{Ph}\P\text{SN SV}}~&\$\text{{\color{red}Ph}}\|\$\\}
    \end{align*}
  \end{exemple}
\end{frame}

\begin{frame}
  \frametitle{Exercice}
  \begin{exercice}{\shades<1>
    Soit la grammaire
    \gdf{E\P E+T\gor T,~T\P T*F\gor F,~F\P a\gor(E).}
    Donnez les étapes de l'analyse de la phrase $a+a*a$ par
    un automate à pile ascendant.
  }\end{exercice}
  \mode<presentation>{\uncover<2->{\begin{align*}
        \only<3-8>{&\$\|a+a*a+a\$\\}
        \only<4-9>{\rewrt{shift}~&\$a\|+a*a\$\\}
        \only<5-10>{\rewr{F\P a}~&\$F\|+a*a\$\\}
        \only<6-11>{\rewr{T\P F}~&\$T\|+a*a\$\\}
        \only<7-12>{\rewr{E\P T}~&\$E\|+a*a\$\\}
        \only<8-13>{\rewrt{shift}~&\$E+\|a*a\$\\}
        \only<9-14>{\rewrt{shift}~&\$E+a\|*a\$\\}
        \only<10-15>{\rewr{F\P a}~&\$E+F\|*a\$\\}
        \only<11-16>{\rewr{T\P F}~&\$E+T\|*a\$\\}
        \only<12->{\rewrt{shift}~&\$E+T*\|a\$\\}
        \only<13->{\rewrt{shift}~&\$E+T*a\|\$\\}
        \only<14->{\rewr{F\P a}~&\$E+T*F\|\$\\}
        \only<15->{\rewr{T\P T*F}~&\$E+T\|\$\\}
        \only<16->{\rewr{E\P E+T}~&\$E\|\$\\}
  \end{align*}}}
\end{frame}

\begin{frame}
  \frametitle{Un amélioration~?}
  \begin{itemize}
    \colorize<2>\item L'automate ascendant est lui aussi fortement
    non-déterministe, avec des conflits
    \begin{itemize}
      \colorize<3>\item \textit{shift/reduce} dans une configuration
      $\a\|a$ si la production $A\P\a$ existe,
      \colorize<4>\item \textit{reduce/reduce} dans une configuration
      $\b\a\|$ si les productions distinctes $A\P\a$ et $B\P\b\a$
      existent.
    \end{itemize}
    \colorize<5>\item En revanche, il n'a pas de problème avec la
    récursivité d'une grammaire acyclique.
  \end{itemize}
\end{frame}

\subsection{Contexte}

\begin{frame}
  \frametitle{Exercice}
  \begin{exercice}{\shades<1>
    Soit la grammaire
    \gdf{S\P A\gor B,~A\P cA\gor a,~B\P cB\gor b.}
    Montrez que l'automate à pile ascendant pour cette grammaire est
    déterministe. Que dire de l'automate descendant~?
  }\end{exercice}
  \mode<presentation>{%
    \only<2>{%
      Le langage reconnu par cette grammaire est ${\cal
        L}=\{c^n(a|b)\mid n\geq 0\}$. L'analyse d'une phrase de ce
      langage est la suivante~:
      \begin{align*}
        &\$\|c^n(a|b)\$\\
        \rewrt{shift}^n~&\$c^n\|(a|b)\$\\
        \rewrt{shift}~&\$c^n(a|b)\|\$\\
        \rewr{A\P a|B\P b}~&\$c^n(A|B)\|\$\\
        \rewr{A\P cA|B\P cB}^n~&\$(A|B)\|\$\\
        \rewr{S\P A|S\P B}~&\$S\|\$\\
      \end{align*}
    }
    \only<3>{%
      L'analyse descendante n'est pas déterministe~: il y a un conflit
      \textit{predict/predict} entre $[S'\P\p S\$]\|\vd{predict}[S'\P
        S\p\$][S\P\p A]\|$ et $[S'\P\p S\$]\|\vd{predict}[S'\P
        S\p\$][S\P\p B]\|$. Ce conflit ne peut être résolu par
      l'utilisation d'une fenêtre de longueur bornée par un $k$ donné.
    }
  }
  \uncover<4>{La décision de reconnaître une production de la grammaire
    est faite juste avant de reconnaître les constituants de cette
    production en analyse descendante, et une fois ces constituants
    reconnus en analyse descendante.}
\end{frame}

\begin{frame}
  \frametitle{Poignées}

  \begin{fdefinition}
    Une chaîne $\a$ est un \define{syntagme} (\textit{phrase} en
    anglais) de la forme sententielle $\f\a\s$ si il existe $A\P\a$
    dans $P$ et si $S\Da\f A\s\D\f\a\s$.
  \end{fdefinition}
  \only<2>{En d'autres termes, la réduction d'$\a$ à $A$ dans $\f\a\s$ nous
    donne bien une forme sententielle.}

  \uncover<3->{\begin{fdefinition}
      Un syntagme d'une forme sententielle droite dont la réduction
      donne à nouveau une forme sententielle droite est appelé une
      \define{poignée} (\textit{handle} en anglais)~:
      $\a$ est une poignée dans la forme sententielle $\d\a x$ si il
      existe $A\P\a$ dans $P$ et si $S\Dra\d Ax\Dr\d\a x$.
  \end{fdefinition}}
\end{frame}

\begin{frame}
  \frametitle{Poignées}
  \only<1>{%
    \begin{exemple}
      \begin{center}\includegraphics{../fig/artiste_poignee1_fig}\end{center}
      \begin{equation}
        \text{Ph}\Dra\text{SN V {\color{red}SN}}\Dr\text{SN V
        {\color{green} Det N}}
      \end{equation}
    \end{exemple}
  }
  \only<2>{%
    \begin{exemple}
      \begin{center}\includegraphics{../fig/artiste_poignee2_fig}\end{center}
      \begin{equation}
        \text{Ph}\Dra\text{SN {\color{red}SV} Det N}\Dr\text{SN
        {\color{green} V} Det N}
      \end{equation}
    \end{exemple}
  }
\end{frame}
La poignée d'une forme sententielle droite est unique pour une
grammaire non ambiguë.

\begin{frame}
  \frametitle{Contexte d'une poignée}
  \begin{fdefinition}
    Soit $\a$ une poignée de la forme sententielle $\d\a x$~; on
    appelle $\d\a$ son \define{contexte gauche} et $x$ son
    \define{contexte droit}.
  \end{fdefinition}
  \uncover<2->{De nombreuses méthodes d'analyse ascendante déterministe
    font jouer des relations entre symboles de la fin du contexte
    gauche et symboles du début du contexte droit~:
    \begin{itemize}
      \colorize<3>\item analyse par \textit{précédence} de symboles
      \cite{Floyd63,WirthW66,weakprec},
      \colorize<4>\item analyse considérant une portion \textit{bornée} des
      contextes gauches et droits~\cite{bc}.
    \end{itemize}
  }
  \uncover<5>{Elles sont tombées dans l'oubli face à LR...}
\end{frame}

\section{Analyse LR}

\subsection{Grammaire caractéristique}

Le principe fondateur de LR est d'exploiter la totalité du contexte
gauche des poignées. Nous commençons par donner un autre point de vue
sur ce contexte gauche.

\begin{frame}
  \frametitle{Préfixe viable}
  \begin{exemple}
  \gdf{S\P aA\gor bB,~A\P cAc\gor d,~B\P cBc\gor d.}
  \begin{columns}[t]
    \column{.5\textwidth}
    \mode<presentation>{\vspace{-2.5em}}
    \uncover<2->{\begin{center}\includegraphics{../fig/ab_fig}\end{center}}
    \column{.5\textwidth}
    \only<3>{La séquence $ac^n d$ est un préfixe viable complet de la
      grammaire~:
      \begin{fdefinition}
        Si $S\Dra\d Ax\Dr\d\a\b x$ dans $\G$, alors $\d\a$ est un
        \define{préfixe viable} de $\G$, et est \define{complet} si
        $\b=\e$.
      \end{fdefinition}
    }
%%     \only<5>{La poignée $d$ dans $ac^ndc^n$ est liée à la poignée
%%       $cAc$ dans $ac^nAc^n$ puisque l'on dispose de la dérivation
%%     $ac^nAc^n\Dr ac^ndc^n$~: on note alors $cAc\searrow d$.}
  \end{columns}
  \end{exemple}  
\end{frame}

L'intérêt de cette notion de préfixe viable est qu'elle est reflétée
par une notion similaire de pile viable de l'analyseur ascendant.

\begin{frame}
  \frametitle{Pile viable}
  \begin{fdefinition}
    La chaîne $\f$ de $Q^\ast$ est une \define{pile viable} pour
    l'automate à pile ${\cal A}=\tup{Q,\Sigma,R,\f_s,F,\$,\|}$ si 
    $\$\f_s\|w\$\models^\ast\$\f\|x\$\models^\ast\$\f_f\|\$$ pour
    $\f_f$ dans $F$ et $w$ et $x$ dans $\Sigma^\ast$.
  \end{fdefinition}
  \uncover<2>{\begin{theoreme}
    Soit $\G$ une grammaire et ${\cal A}_\text{asc}$ son automate à
    pile ascendant. Tout préfixe viable de $\G$ est une pile viable de
    ${\cal A}_\text{asc}$ et réciproquement.
  \end{theoreme}}
\end{frame}

Toute la force de la méthode LR réside dans le fait que les préfixes
viables d'une grammaire forment un langage régulier, et qu'ils peuvent
donc être reconnus par un automate à états finis déterministe.

\begin{frame}
  \frametitle{Grammaire caractéristique~\cite{Knuth65}}
  \begin{fdefinition}
    Soit une grammaire $\G=\tup{N,\Sigma,P,S}$.  La \define{grammaire
    caractéristique} de $\G$ est $\G_0=\tup{N_0,V,P_0,[S]}$ où
    \begin{itemize}
      \colorize<2>\item $N_0=\{[A]\mid A\in N\}$ et
      \colorize<3>\item $P_0=\{[A]\P\a\mid A\P\a\in P\}\cup\{[A]\P\a[B]\mid A\P\a B\b\in P\}$.
    \end{itemize}
  \end{fdefinition}
  \uncover<4->{\begin{exemple}
      La grammaire caractéristique pour\mode<presentation>{\vspace{-1em}}
      \gdf{S\P aA\gor bB,~A\P cAc\gor d,~B\P cBc\gor d}\mode<presentation>{\vspace{-1em}}
      est\mode<presentation>{\vspace{-1em}}
      \gdf{[S]\P a[A]\gor aA\gor b[B]\gor bB,~[A]\P c[A]\gor
        cAc\gor d,~[B]\P c[B]\gor cBc\gor d.}\mode<presentation>{\vspace{-1em}}
  \end{exemple}}
  \uncover<5>{La grammaire caractéristique d'une grammaire $\G$ génère tous
    les préfixes viables complets de $\G$.}
\end{frame}

La grammaire caractéristique est une grammaire linéaire à droite~; le
langage des préfixes viables complet est donc un langage rationnel.
L'exercice suivant est l'occasion d'exploiter cette propriété.

\begin{frame}
  \frametitle{Exercice}
  \only<1>{\begin{exercice}
      Donner un automate à états finis déterministe qui reconnaît les
      phrases du générées par la grammaire caractéristique
      \gdf{[S]\P a[A]\gor aA\gor b[B]\gor bB,~[A]\P c[A]\gor
        cAc\gor d,~B\P c[B]\gor cBc\gor d.}
  \end{exercice}}
  \mode<presentation>{\only<2>{\includegraphics[height=\textheight]{../fig/abFSA}}}
\end{frame}

\subsection{Items LR($k$)}
Cette construction de l'automate à états finis est formalisée
par la notion d'items LR. Nous utilisons une notion plus forte que le
simple préfixe viable complet~: nous souhaitons connaître exactement
quelles chaînes de longueur $k$ sont acceptables après ce préfixe.

\begin{frame}
  \frametitle{Item LR($k$) valide~\cite{Knuth65,au72}}
  \begin{fdefinition}
    Un \define{$k$-item} est un couple de la forme $[A\P\a\p\b,u]$ où
    $A\P\a\b$ est une production de $P$ et $u$ une chaîne de
    $\Sigma^k$. Il est \define{LR($k$)-valide} pour un préfixe $\g$ si
    \begin{equation}
      S'\Dra\d Ax\Dr\d\a\b x=\g\b x\text{ et }k:x=u.
    \end{equation}
  \end{fdefinition}
  \uncover<2->{Si $\g$ est un préfixe viable de $\G$, alors il existe
    un item valide pour $\g$, et réciproquement.}
  \only<3>{\begin{exemple}
      Les items $[A\P c\p Ac, c]$ et $[A\P\p d, c]$ sont valides pour
    $ac^n$, $n>1$ pour la grammaire\mode<presentation>{\vspace{-1em}}
      \gdf{S\P aA\gor bB,~A\P cAc\gor d,~B\P cBc\gor
    d~:}\mode<presentation>{\vspace{-2em}}
      \begin{equation}
        S'\Dra ac^{n-1}Ac^{n-1}\$\Dr ac^nAc^n\$\Dr ac^ndc^n\$\text{ et }1:c^n=c.
      \end{equation}
  \end{exemple}}
  \only<4>{%
      L'ensemble des $k$-items valides pour $\g$ est noté
      \begin{equation}
        \text{Valid}_k(\g)=\{\iota\mid \iota\text{ est un $k$-item valide pour
        }\g\}.
      \end{equation}
  }
\end{frame}

\begin{frame}
  \frametitle{Relations entre items LR($k$)}
  \begin{lemme}{\colorize<2>
      Si $S\P\s$ est une règle de $P$, alors $[S\P\p\s, \$^k]$ est un
      $k$-item valide pour $\e$.
  }\end{lemme}
  \begin{lemme}{\colorize<3>
      Si $[A\P\a\p X\b,u]$ est un $k$-item valide pour $\g$, alors $[A\P\a
        X\p\b,u]$ est un $k$-item valide pour $\g X$. On note
        $[A\P\a\p X\b,u]\mbox{$\stackrel{X}{\curvearrowright}$}[A\P\a X\p\b,u]$.
  }\end{lemme}
  \begin{lemme}{\colorize<4>
      Si $[A\P\a\p B\b, u]$ est un $k$-item valide pour $\g$, alors
      $[B\P\p\d, \text{First}_k(\b u)]$ est un $k$-item valide pour
      $\g$. On note $[A\P\a\p B\b, u]\mbox{$\stackrel{\e}{\curvearrowright}$}[B\P\p\d, \text{First}_k(\b u)]$.
  }\end{lemme}
  \uncover<5>{\begin{theoreme}
      \begin{equation}
        \text{Valid}_k(\g)=\{\iota\mid
        [S\P\p\s,\$^k]\mbox{$\stackrel{\g}{\curvearrowright}$}\iota\}.
      \end{equation}
  \end{theoreme}}
\end{frame}

\begin{frame}
  \frametitle{Exercice}
  \begin{exercice}{\shades<1>
    Donnez les ensembles $\text{Valid}_k$ pour la grammaire\mode<presentation>{\vspace{-1em}}
      \gdf{S\P aA\gor bB,~A\P cAc\gor d,~B\P cBc\gor
      d}\mode<presentation>{\vspace{-1em}}
  }\end{exercice}
  \mode<presentation>{\uncover<2->{\begin{align*}
        \only<3-6>{\text{Valid}_k(\e)&=\{[S\P\p aA,\$^k],[S\P\p bB,\$^k]\}\\}
        \only<4-7>{\text{Valid}_k(a)&=\{[S\P a\p A,\$^k],[A\P\p cAc,\$^k],[A\P\p d,\$^k]\}\\}
        \only<5-8>{\text{Valid}_k(ac^{n+1})&=\{[A\P c\p Ac,k:c^n\$^{k-n}],[A\P\p cAc,k:c^{n+1}\$^{k-n-1}],\\&~~[A\P\p d,k:c^{n+1}\$^{k-n-1}]\}\\}
        \only<6-9>{\text{Valid}_k(ac^nd)&=\{[A\P d\p,k:c^n\$^{k-n}]\}\\}
        \only<7-10>{\text{Valid}_k(aA)&=\{[S\P aA\p,\$^k]\}\\}
        \only<8-11>{\text{Valid}_k(ac^{n+1}A)&=\{[A\P cA\p c,k:c^n\$^{k-n}]\}\\}
        \only<9-12>{\text{Valid}_k(ac^{n+1}Ac)&=\{[A\P cAc\p,k:c^n\$^{k-n}]\}\\}
        \only<10-13>{\text{Valid}_k(b)&=\{[S\P b\p B,\$^k],[B\P\p cBc,\$^k], [B\P\p d,\$^k]\}\\}
        \only<11-14>{\text{Valid}_k(bc^{n+1})&=\{[B\P c\p Bc,k:c^n\$^{k-n}],[B\P\p cBc,k:c^{n+1}\$^{k-n-1}],\\&~~[B\P\p d,k:c^{n+1}\$^{k-n-1}]\}\\}
        \only<12-15>{\text{Valid}_k(bc^nd)&=\{[B\P d\p,k:c^n\$^{k-n}]\}\\}
        \only<13-16>{\text{Valid}_k(bB)&=\{[S\P bB\p,\$^k]\}\\}
        \only<14->{\text{Valid}_k(bc^{n+1}B)&=\{[B\P cB\p c,k:c^n\$^{k-n}]\}\\}
        \only<15->{\text{Valid}_k(bc^{n+1}Bc)&=\{[B\P cBc\p,k:c^n\$^{k-n}]\}\\}
        \only<16->{\text{Valid}_k(\g)&=\emptyset\text{ pour toute
            autre chaîne $\g$ de $\Va$.}\\}
  \end{align*}}}
\end{frame}

\begin{frame}
  \frametitle{Équivalence LR($k$)}
  \begin{fdefinition}
    La chaîne $\g_1$ est \define{LR($k$)-équivalente} à la chaîne $\g_2$,
    dénoté par $\g_1\equiv_\text{LR($k$)}\g_2$, si et seulement si
    $\text{Valid}_k(\g_1)=\text{Valid}_k(\g_2)$.
  \end{fdefinition}
  \uncover<2->{\begin{theoreme}
      Pour toute grammaire $\G=\tup{N,\Sigma,P,S}$ et entier naturel
      $k$, la relation $\equiv_\text{LR($k$)}$ est une relation
      d'équivalence sur $\Va$. De plus, $\equiv_\text{LR($k$)}$ a un
      index fini et borné par
      \begin{equation}
        2^{|\G||\Sigma|^k}.
      \end{equation}
  \end{theoreme}}
  \uncover<3>{\begin{exercice}
      Prouver le théorème précédent.
  \end{exercice}}
\end{frame}

\begin{exercice}
  Reformulez la définition d'une grammaire caractéristique pour
  utiliser la fenêtre de $k$ symboles.
\end{exercice}

\subsection{Automate LR($k$)}
L'équivalence LR($k$) est l'équivalence induite par l'automate d'états
finis reconnaissant $\G_k$. On note les classes d'équivalence de
$\equiv_\text{LR($k$)}$ par $[\g]_k$ où $\g$ est un élément de la
classe d'équivalence, et on note l'ensemble des classes d'équivalence
$E_k$.

\begin{frame}
  \frametitle{Automate LR($k$)}
  \begin{fdefinition}
    L'\define{automate LR($k$)} de la grammaire $\G$ est l'automate à
    pile ascendant ${\cal
    A}_\text{LR($k$)}=\tup{E_k,\Sigma,R,[\e],\{[S]\},\$,\|}$ où
    \begin{itemize}
      \colorize<2>\item $E_k$ est l'ensemble des classes
      d'équivalences $[\d]_k$ de $\equiv_\text{LR($k$)}$,
      \colorize<3>\item l'ensemble des règles $R$ est restreint aux
      règles\mode<presentation>{\vspace{-1em}}
      \begin{equation}
          [\d]_k[\d X_1]_k\dots[\d X_1\dots
          X_n]_k\|u\red{A\P X_1\dots X_n}[\d]_k[\d A]_k\|u,
      \end{equation}\mode<presentation>{\vspace{-1em}}
      si un item $[A\P X_1\dots X_n\p,u]$ est LR($k$)-valide pour
      $\d$, et\mode<presentation>{\vspace{-1em}}
      \begin{equation}
          [\d]_k\|au\shift [\d]_k[\d a]_k\|u,
      \end{equation}\mode<presentation>{\vspace{-1em}}
      si un item $[A\P\a\p a\b,v]$ est LR($k$)-valide pour
      $\d$ et si $u\in\text{First}_{k-1}(\b v)$.      
    \end{itemize}
  \end{fdefinition}
\end{frame}

\begin{frame}
  \frametitle{Analyse ascendante LR}
  \begin{exemple}
    Soit la grammaire
      \mode<presentation>{\vspace{-0.5em}}\gdf{S\P aA\gor bB,~A\P cAc\gor d,~B\P cBc\gor
    d~:}
      \mode<presentation>{%
    \begin{columns}[t]
      \column{.2\textwidth}
      \vspace{-3em}
      \only<1>{\begin{center}\includegraphics{../fig/ab_tree0_fig}\end{center}}
      \only<2>{\begin{center}\includegraphics{../fig/ab_tree1_fig}\end{center}}
      \only<3>{\begin{center}\includegraphics{../fig/ab_tree2_fig}\end{center}}
      \only<4>{\begin{center}\includegraphics{../fig/ab_tree3_fig}\end{center}}
      \only<5>{\begin{center}\includegraphics{../fig/ab_tree4_fig}\end{center}}
      \only<6>{\begin{center}\includegraphics{../fig/ab_tree5_fig}\end{center}}
      \only<7>{\begin{center}\includegraphics{../fig/ab_tree6_fig}\end{center}}
      \only<8>{\begin{center}\includegraphics{../fig/ab_tree7_fig}\end{center}}
      \only<9>{\begin{center}\includegraphics{../fig/ab_tree8_fig}\end{center}}
      \only<10>{\begin{center}\includegraphics{../fig/ab_tree9_fig}\end{center}}
      \only<11>{\begin{center}\includegraphics{../fig/ab_tree10_fig}\end{center}}
      \column{.8\textwidth}
      \vspace{-2.5em}     
      \only<1>{\includegraphics[scale=.75]{../fig/ab_valid0_fig}}
      \only<2>{\includegraphics[scale=.75]{../fig/ab_valid1_fig}}
      \only<3>{\includegraphics[scale=.75]{../fig/ab_valid2_fig}}
      \only<4>{\includegraphics[scale=.75]{../fig/ab_valid3_fig}}
      \only<5>{\includegraphics[scale=.75]{../fig/ab_valid4_fig}}
      \only<6>{\includegraphics[scale=.75]{../fig/ab_valid5_fig}}
      \only<7>{\includegraphics[scale=.75]{../fig/ab_valid6_fig}}
      \only<8>{\includegraphics[scale=.75]{../fig/ab_valid7_fig}}
      \only<9>{\includegraphics[scale=.75]{../fig/ab_valid8_fig}}
      \only<10>{\includegraphics[scale=.75]{../fig/ab_valid9_fig}}
      \only<11>{\includegraphics[scale=.75]{../fig/ab_valid10_fig}}
    \end{columns}\vspace{-1em}}
    \begin{align*}
      \only<1-2>{&\$[\e]\|accdcc\$\\}
      \only<2-3>{\rewrt{shift}&\$[\e][{\colorize<2> a}]\|ccdcc\$\\}
      \only<3-4>{\rewrt{shift}&\$[\e][a][a{\colorize<3>c}]\|cdcc\$\\}
      \only<4-5>{\rewrt{shift}&\$[\e][a][ac][ac{\colorize<4>c}]\|dcc\$\\}
      \only<5>{\rewrt{shift}&\$[\e][a][ac][acc][acc{\colorize<5>d}]\|cc\$\\}
      \only<6>{\rewrt{shift}&\$[\e][a][ac][acc][acc{\color{green}d}]\|cc\$\\}
      \only<6-7>{\rewr{A\P d}&\$[\e][a][ac][acc][acc{\colorize<6>A}]\|cc\$\\}
      \only<7>{\rewrt{shift}&\$[\e][a][ac][acc][accA][accA{\colorize<7>c}]\|c\$\\}
      \only<8>{\rewrt{shift}&\$[\e][a][ac][acc][accA][ac{\color{green}cAc}]\|c\$\\}
      \only<8-9>{\rewr{A\P cAc}&\$[\e][a][ac][ac{\colorize<8>A}]\|c\$\\}
      \only<9>{\rewrt{shift}&\$[\e][a][ac][acA][acA{\colorize<9>c}]\|\$\\}
      \only<10>{\rewrt{shift}&\$[\e][a][ac][acA][a{\color{green}cAc}]\|\$\\}
      \only<10>{\rewr{A\P cAc}&\$[\e][a][a{\colorize<10>A}]\|\$\\}
      \only<11>{\rewr{A\P cAc}&\$[\e][a][{\color{green}aA}]\|\$\\}
      \only<11>{\rewr{S\P aA}&\$[\e][{\color{red}S}]\|\$\\}
    \end{align*}
  \end{exemple}
\end{frame}

\begin{frame}
  \frametitle{Grammaires LR($k$)}
  \begin{fdefinition}
    Une grammaire est LR($k$) si 
    \begin{enumerate}
      \colorize<2>\item $S\Dra\d Ax\Dr\d\a x$,
      \colorize<3>\item $S\Dra\g By\Dr\g\b zy=\d\a zy$ et
      \colorize<4>\item $k:x=k:zy$
    \end{enumerate}
    {\colorize<5> impliquent $\d Ax=\g By$.}
  \end{fdefinition}
  \uncover<6->{\begin{theoreme}
      Une grammaire $\G$ est LR($k$) si et seulement si son automate
      LR($k$) est déterministe.
  \end{theoreme}}
  \uncover<6>{\begin{theoreme}
    Si une grammaire $\G$ est LR($k$), alors il existe une grammaire
    $\G'$ LR(1) équivalente.
  \end{theoreme}}
\end{frame}

\begin{frame}
  \frametitle{Langages déterministes}
  \begin{theoreme}
    Les langages générés par les grammaires LR(1)
    sont exactement les langages reconnus par un automate
    à pile déterministe. On appelle ces langages les \define{langages
    déterministes}.
  \end{theoreme}
\end{frame}

%% \begin{frame}
%%   \frametitle{Préfixe viable}
%%   \begin{fdefinition}
%%     Un automate à pile ${\cal
%%     A}_\text{asc}=\tup{V,\Sigma,R,\f_s,F,\$,\|}$ a la propriété du
%%     \define{préfixe viable} si $\$\f_s\|xy\$\models^\ast\$\f\|y\$$ n'est vrai
%%     que si $x$ est le préfixe d'une phrase de ${\cal L}_{{\cal A}}$.
%%   \end{fdefinition}~\cite{Knuth65,backhouse}
  
%% \end{frame}


\begin{frame}
\selectlanguage{english}
\bibliographystyle{alpha}
\bibliography{parsing.bib}
\end{frame}

\end{document}