%%
% lalr.tex
% LALR 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 LALR}
\institute{Université de Nice Sophia Antipolis}
\date{2005/2006}
  \refstepcounter{part}
  \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 LALR}
\frame{\partpage}

\section{Rappels}

\subsection{Analyse LR}

\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~:}
    \begin{columns}[t]
      \column{.2\textwidth}
      \mode<presentation>{\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}
      \mode<presentation>{\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}\mode<presentation>{\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{En résumé}
  \begin{itemize}
    \colorize<2>\item Le langage des contextes gauches des poignées
    est rationnel\only<2>{, puisque généré par la grammaire
    caractéristique, qui est linéaire}.
    \colorize<3>\item Un langage rationnel définit des classes
    d'équivalence sur les phrases du langage\only<3>{ par le biais des
    états de son automate à états finis déterministe minimal}.
    \colorize<4>\item Ces classes d'équivalence peuvent être calculées
    directement en utilisant les items valides LR($k$)
    \only<4>{~:\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}}
    \colorize<5>\item Ces classes d'équivalence servent d'états pour
    l'automate à pile LR($k$).
    \colorize<6>\item Il existe $2^{|\G||\Sigma|^k}$ classes
    d'équivalence distinctes possibles.
  \end{itemize}
  \uncover<7>{La classe de grammaires LR($k$) est la classe analysable
    par automates à pile déterministes la plus large possible.}
\end{frame}

\subsection{Le problème}

\begin{frame}
  \frametitle{Le problème}
  \begin{exercice}{\shades<1>
    Donnez les ensembles $\text{Valid}_0$ pour la grammaire \gdf{S\P
    aSa\gor bSb\gor c.} Combien y-a-t'il de classes d'équivalence
    LR(0)~? LR(1)~? LR($k$)~?}
  \end{exercice}
  \mode<presentation>{\uncover<2>{%
      Pour chacun des corps d'item $S\P a\p Sa$, $S\P aS\p a$, $S\P
      aSa\p$, $S\P b\p Sb$, $S\P bS\p b$, $S\P bSb\p$ et $S\P c\p$,
      n'importe quel ensemble de $k$ symboles ou moins, pris parmi
      $\{a,b\}$, peut apparaître en fenêtre, complété par des $\$$.
      Soit
      \begin{equation*}
        2^k+2^{k-1}+\dots+2+1=2^{k+1}-1
      \end{equation*}
      fenêtres de $k$ symboles possibles pour chaque corps.
      Soit au final \emph{$7(2^{k+1}-1)+1$} états LR($k$).      
  }}  
\end{frame}

\section{Analyse LALR}

\subsection{Principe de LALR}

\begin{frame}
  \frametitle{Fusion d'états}
  Les trois états {\colorize<2>
  \begin{tabular}{|l|}
    \hline
    $S\P a\p Sa, \$$\\
    $S\P\p aSa, a$\\
    $S\P\p bSb, a$\\
    $S\P\p c, a$\\
    \hline
  \end{tabular}}, {\colorize<3>
  \begin{tabular}{|l|}
    \hline
    $S\P a\p Sa, a$\\
    $S\P\p aSa, a$\\
    $S\P\p bSb, a$\\
    $S\P\p c, a$\\
    \hline
  \end{tabular}} et {\colorize<4>
  \begin{tabular}{|l|}
    \hline
    $S\P a\p Sa, b$\\
    $S\P\p aSa, a$\\
    $S\P\p bSb, a$\\
    $S\P\p c, a$\\
    \hline
  \end{tabular}}

  sont fusionnés en un seul {\colorize<5>
  \begin{tabular}{|l|}
    \hline
    $S\P a\p Sa, \{\$,a,b\}$\\
    $S\P\p aSa, \{a\}$\\
    $S\P\p bSb, \{a\}$\\
    $S\P\p c, \{a\}$\\
    \hline
  \end{tabular}}.
  \uncover<6>{\begin{fdefinition}[\cite{KM81}]
    La fenêtre LALR($k$) d'un corps valide pour un préfixe $\g$ est
    \begin{equation}
      LA([\g],A\P\a\p\a')=\{k:z\mid S\Dra\d Ax\Dr\d\a\a'x\Dra\d\a z\text{ et }\d\a\equiv_{\text{LR(0)}}\g\}.
    \end{equation}
  \end{fdefinition}}
\end{frame}

\begin{frame}
  \frametitle{Équivalence d'arbres}
  Le corps d'item $S\P a\p Sa$ peut apparaître dans trois types
  d'arbres différents~:
  \begin{center}
    \includegraphics{../fig/aSa_fig}
  \end{center}
  \uncover<2>{Les préfixes viables correspondants sont \emph{LR(0)-équivalents}~:
    \begin{equation*}
      [a]_0=\{wa\mid w\in\{a,b\}^\ast\}=(a|b)^\ast a.
    \end{equation*}}
\end{frame}

\subsection{Calcul d'une fenêtre}

\begin{frame}
  \frametitle{Fenêtre sur un arbre}
  \only<1>{Le calcul de la fenêtre est compliqué par la présence de règles vides.}
  \begin{exemple}
    \gdf{S\P CBBa,~A\P d,~B\P\e,~C\P bC\gor bAB\gor bDBb,~D\P d.}
    \mode<presentation>{\vspace{-2em}}
    \begin{columns}[t]
      \column{.3\textwidth}
      \mode<presentation>{%
      \only<2-3>{\begin{center}%
          \includegraphics{../fig/CBa_lookahead_fig}\end{center}}
      \only<4>{\begin{center}%
          \includegraphics{../fig/CBa_lookback_fig}\end{center}}
      \only<5>{\begin{center}%
          \includegraphics{../fig/CBa_includes1_fig}\end{center}}
      \only<6>{\begin{center}%
          \includegraphics{../fig/CBa_includes2_fig}\end{center}}
      \only<7>{\begin{center}%
          \includegraphics{../fig/CBa_reads1_fig}\end{center}}}
      \only<8->{\begin{center}%
          \includegraphics{../fig/CBa_reads2_fig}\end{center}}
      \column{.7\textwidth}
        \only<3>{Une position dans un arbre syntaxique équivaut à une
          position dans une forme sententielle droite. On écrit une
          telle position $\d[A\P\a\p\a']x$, où $\d\a\a'x$ est une
          forme sententielle droite et $\a\a'$ une poignée dans cette
          forme sententielle droite.
        
        Par exemple, on écrirait $bbb[A\P d\p]a$ pour la position dans
        l'arbre ci-contre.}
        \only<4>{\begin{fdefinition}
            Si $\d Cy\Dr\d\g A\s y\Dra\d\g Axy\Dr\d\g\a xy$, alors
            \begin{equation}
              \d\g[A\P\a\p]xy\rel{lookback}\d[C\P\g A\p\s]y.
            \end{equation}
        \end{fdefinition}
        Par exemple, $bbb[A\P d\p]a\rel{lookback}bb[C\P bA\p B]a$.}
        \only<5-6>{\begin{fdefinition}
            Si $\d Cy\Dr\d\g A\s y\Dra\d\g Axy\Dr\d\g\a\f xy\Dra\d\g\a xy$, alors
            \begin{equation}
              \d\g[A\P\a\p\f]xy\rel{includes}\d[C\P\g A\p\s]y.
            \end{equation}
        \end{fdefinition}
        Par exemple, $bb[C\P bA\p B]a\rel{includes}b[C\P bC\p]a$\only<6>{ et
        $b[C\P bC\p]a\rel{includes}[S\P bC\p BBa]$}.}
        \only<7-8>{\begin{fdefinition}
            Si $\d Cy\Dr\d\g A\s y\Dra\d\g Axy\Dr\d\g xy$, alors
            \begin{equation}
              \d[C\P\g\p A\s]y\rel{reads}\d[C\P\g A\p\s]y.
            \end{equation}
        \end{fdefinition}
        Par exemple, $[S\P bC\p BBa]\rel{reads}[S\P bCB\p Ba]$\only<8>{ et
        $[S\P bCB\p Ba]\rel{reads}[S\P bCBB\p a]$}.}
    \end{columns}
  \end{exemple}
\end{frame}

\begin{frame}
  \frametitle{Et LALR(1)~?~\cite{lalr}}
  \begin{theoreme}
    $S\Dra\d Aax\Dr\d\a ax$ si et seulement si
    \begin{equation}
    \d[A\P\a\p]ax\rel{lookback}\circ\rela{includes}\circ(\rela{reads}\circ\mbox{$\stackrel{\e}{\curvearrowright}$}^\ast)^\ast\g[C\P\b\p a\b']y.
    \end{equation}
  \end{theoreme}
  \uncover<2-3>{%
    Pour faire un calcul de fenêtre LALR(1), il suffit de faire ces
    opérations modulo l'équivalence $\equiv_{\text{LR(0)}}$ sur le
    préfixe de la position.}
  \uncover<3>{%
    Les relations définies en
    termes d'états et de transitions LR(0) deviennent~:
    \begin{align*}
      ([\d\a], A\P\a)&\rel{lookback}([\d],A)\\
      ([\d\b], A)&\rel{includes}([\d], B)\mbox{ ssi }B\P\b A\g\mbox{
        et }\g\Da\e,\\
      ([\d], A)&\rel{reads}([\d A], C)\mbox{ ssi }([\d A],C)\mbox{ et
      }C\Da\e.
    \end{align*}}
\end{frame}

\begin{frame}
  \frametitle{Exemple}
  \begin{center}
    \only<1>{\includegraphics[scale=.6]{../fig/CBa_valid_fig}\\}
    \only<2>{\includegraphics[scale=.6]{../fig/CBa_valid0_fig}\\}
    \only<3>{\includegraphics[scale=.6]{../fig/CBa_valid1_fig}\\}
    \only<4>{\includegraphics[scale=.6]{../fig/CBa_valid2_fig}\\}
    \only<5>{\includegraphics[scale=.6]{../fig/CBa_valid3_fig}\\}
    \only<6>{\includegraphics[scale=.6]{../fig/CBa_valid4_fig}\\}
    \only<7>{\includegraphics[scale=.6]{../fig/CBa_valid5_fig}\\}
    \only<8>{\includegraphics[scale=.6]{../fig/CBa_valid6_fig}\\}
    \only<9>{\includegraphics[scale=.6]{../fig/CBa_valid7_fig}\\}
    \only<10>{\includegraphics[scale=.6]{../fig/CBa_valid8_fig}\\}
    \only<11>{\includegraphics[scale=.6]{../fig/CBa_valid9_fig}\\}
    \only<12>{\includegraphics[scale=.6]{../fig/CBa_valid10_fig}\\}
  \end{center}
\end{frame}

\section{Conclusion}

\begin{frame}
  \frametitle{En résumé}
  \begin{itemize}
    \colorize<2>\item Le calcul du contexte droit d'une position n'est
    pas forcément un calcul LR($k$) précis, il peut utiliser une
    équivalence.
    \colorize<3>\item Cette relation d'équivalence est la relation
    $\equiv_{\text{LR(0)}}$ pour LALR(1).
    \colorize<4>\item Cette approximation est assez précise pour
    analyser tous les langages déterministes~\cite{lalrslr}.
    \colorize<5>\item On peut imaginer d'autres approximations~\cite{korenjak,anderson}\dots
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Limites de LALR}
  Les limites de LALR sont les limites de l'approximation par LR(0).
  \begin{exercice}
    Donner l'automate LALR(1) pour la grammaire
    \gdf{S\P aAa\gor bAb\gor aBb\gor bBa,~A\P c,~B\P c.}
  \end{exercice}
\end{frame}

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

\end{document}