%%
% nlalr.tex
% Noncanonical 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}
\usepackage{stmaryrd}

%% Meta information
\title{Analyse non canonique}
\institute{Université de Nice Sophia Antipolis}
\date{2005/2006}
  \refstepcounter{part}
  \refstepcounter{part}
  \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 non canonique}
\frame{\partpage}

\section{Rappels}

\subsection{Analyse LR}

\begin{frame}
  \frametitle{Grammaires LR($k$)}
  La classe des grammaires LR($k$) est la classe de grammaires la plus
  large analysable de gauche à droite avec un automate à pile
  déterministe.
  \uncover<2->{\begin{exercice}{\shades<2>
    Montrer que la grammaire suivante n'est pas LR($k$) pour aucune
    valeur de $k$~:
    \gdf{S\P BC\gor AD,~A\P a,~B\P a,~C\P CA\gor A,~D\P aD\gor b.}
  }\end{exercice}}
  \mode<presentation>{\uncover<3>{%
      On a les dérivations
      \begin{gather*}
        S\Dr AD\Dra Aa^nb\Dr aa^nb\\
        S\Dr BC\Dra Ba^m\Dr aa^m.
      \end{gather*}
      Il faudrait une fenêtre non bornée pour résoudre le conflit dans
      l'état $[a]$.
  }}
\end{frame}

\section{Analyse non canonique}

\subsection{Principes}

\begin{frame}
  \frametitle{Au-delà de LR($k$)}
  \begin{itemize}
    \colorize<2>\item Ne plus utiliser un automate à pile
    déterministe, mais un automate à deux piles déterministe.
    \colorize<3>\item L'entrée sert de seconde pile.
    \colorize<4>\item Les réductions se font en plaçant le symbole
    réduit sur la pile d'entrée.
    \colorize<5>\item Les symboles non terminaux peuvent être utilisés
    en fenêtre.
    \colorize<6-7>\item Les réductions de syntagmes qui ne sont pas des
    poignées sont permises.
  \end{itemize}
  \uncover<7>{\begin{exemple}
    L'analyse non canonique pour 
    \gdf{S\P BC\gor AD,~A\P a,~B\P a,~C\P CA\gor A,~D\P aD\gor b}
    va permettre la réduction de $b$ à $D$ dans la forme sententielle
    ${\color{green}a}a^n{\color{blue}b}$. 
  \end{exemple}}
\end{frame}

\begin{frame}
  \frametitle{Exemple d'analyse}
  \begin{exemple}
    Soit la grammaire
    \gdf{S\P BC\gor AD,~A\P a,~B\P a,~C\P CA\gor A,~D\P aD\gor b.}
    L'analyse non canonique de la phrase $aaa$ se fait par les étapes~:
    \begin{align*}
      \only<2-6>{&\$[\e]\|aaa\$\\}
      \only<3-7>{\rewrt{shift}~&\$[\e][a]\|aa\$\\}
      \only<4-8>{\rewrt{shift}~&\$[\e][a]\st{aa}\|a\$\\}
      \only<5-9>{\rewrt{shift}~&\$[\e][a]\st{aa}\st{aaa}\|\$\\}
      \only<6-10>{\rewr{A\P a}~&\$[\e][a]\st{aa}\|A\$\\}
      \only<7-11>{\rewr{A\P a}~&\$[\e][a]\|AA\$\\}
      \only<8-12>{\rewr{B\P a}~&\$[\e]\|BAA\$\\}
      \only<9-13>{\rewrt{shift}~&\$[\e][B]\|AA\$\\}
      \only<10-14>{\rewrt{shift}~&\$[\e][B][BA]\|A\$\\}
      \only<11-15>{\rewr{C\P A}~&\$[\e][B]\|CA\$\\}
      \only<12-16>{\rewrt{shift}~&\$[\e][B][BC]\|A\$\\}
      \only<13->{\rewrt{shift}~&\$[\e][B][BC][BCA]\|\$\\}
      \only<14->{\rewr{C\P CA}~&\$[\e][B]\|C\$\\}
      \only<15->{\rewrt{shift}~&\$[\e][B][BC]\|\$\\}
      \only<16->{\rewr{S\P BC}~&\$[\e]\|S\$\\}
      \only<17->{\rewrt{shift}~&\$[\e][S]\|\$\\}
    \end{align*}
  \end{exemple}
\end{frame}

\begin{frame}
  \frametitle{Les méthodes d'analyse non canonique}
  \begin{itemize}
    \colorize<2>\item LR($k$,$t$) permet de réduire le $t$\ieme
    syntagme depuis l'extrémité gauche d'une forme
    sententielle~\cite{Knuth65}~;
    \colorize<3>\item \textit{Total Precedence} étend l'analyse
    ascendante par précédence~\cite{tp}~;
    \colorize<4>\item BC($m$,$n$) étend les méthodes à contexte
    borné~\cite{bcp}~;
    \colorize<5>\item LR($k$,$\infty$) et FSPA($k$) généralisent
    LR($k$,$t$)~\cite{sz-wl}~;
    \colorize<6>\item NSLR(1) étend l'analyse SLR(1)~\cite{nslr}~;
    \colorize<7>\item NDR est une extension de DR($k$)~\cite{bcndr}.
  \end{itemize}
  \uncover<8>{Nous allons présenter une analyse LALR(1) non canonique.}
\end{frame}

\subsection{Analyse NLALR(1)}

\begin{frame}
  \frametitle{Calcul des états non canoniques}
  Comment passer des positions $B\P a\p$ et $A\P a\p$ de l'état $[a]$
  aux positions $A\P a\p$ et $D\P a\p D$ de l'état $\st{aa}$~?
  \only<1-6>{\begin{columns}[t]
    \column{.4\textwidth}
    \begin{center}
      \only<1>{\includegraphics{../fig/BC_tree_fig}\\}
      \only<2>{\includegraphics{../fig/BC_tree_lookback_fig}\\}
      \only<3>{\includegraphics{../fig/BC_tree_eps1_fig}\\}
      \only<4>{\includegraphics{../fig/BC_tree_eps2_fig}\\}
      \only<5>{\includegraphics{../fig/BC_tree_eps3_fig}\\}
      \only<6>{\includegraphics{../fig/BC_tree_eps4_fig}\\}
    \end{center}
    \column{.6\textwidth}
    \begin{center}
      \only<1>{\includegraphics[scale=.7]{../fig/BC_valid_fig}\\}
      \only<2>{\includegraphics[scale=.7]{../fig/BC_valid_lookback_fig}\\}
      \only<3-4>{\includegraphics[scale=.7]{../fig/BC_valid_eps1_fig}\\}
      \only<5>{\includegraphics[scale=.7]{../fig/BC_valid_eps2_fig}\\}
      \only<6>{\includegraphics[scale=.7]{../fig/BC_valid_eps4_fig}\\}
    \end{center}
  \end{columns}}
  \only<7->{L'état $\st{aa}$ est l'\emph{union} des états LR(0)
    $[BC^\ast a]$ et $[Aa^+]$.}
\end{frame}

\begin{frame}
  \frametitle{Couvertures valides}

  On dit que les préfixes valides $BC^\ast a$ et $Aa^+$
  \emph{couvrent} le préfixe de forme sententielle $aa$\only<2->{, et
    effectivement $Ba\Da aa$ et $Aa\Da aa$}.

  \uncover<3->{\begin{fdefinition}
      La chaîne $\g$ est une \define{couverture valide} dans $\G$
      pour la chaîne $\d$ si et seulement si $\g$ est un préfixe
      valide et $\g\Da\d$.
      
      On écrit $\hat{\d}$ pour dénoter une couverture de $\d$ et
      $\text{Cover}(\d)$ pour dénoter l'ensemble de toutes les
      couvertures valides pour $\d$.
  \end{fdefinition}}
  \uncover<4->{\begin{theoreme}
  Soit $\a$ un syntagme tel que $S'\Da\d AX\w\D\d\a X\w$ avec
  $q=[\hat{\d}\a]$, alors
  \begin{equation*}
    \text{Cover}(\hat{\d}A X)=\{\g CX\mid
    (q,A\P\a)\rel{lookback}\circ\rela{includes}\circ\rela{reads}([\g],C)\}.
  \end{equation*}
  \end{theoreme}}
\end{frame}

\begin{frame}
  \frametitle{Fenêtres NLALR(1)}
  
  \only<1-2>{\begin{fdefinition}{\colorize<2>
        L'ensemble des \define{fenêtres réduites} pour une réduction par
        $A\P\a$ dans l'état LR(0) $q$ est défini par
        \begin{equation}\label{eq:dredla}
          \text{RLA}(q,A\P\a)=\{X\mid
          S'\Dla zA\g X\w,\g\Da\e, X\Da ax,\mbox{ et
          }q=[\hat{z}\a]\}.
        \end{equation}
  }\end{fdefinition}}
  
  \only<2-3>{\begin{fdefinition}{\colorize<3>
        L'ensemble des \define{fenêtres dérivées} pour une réduction par
        $A\P\a$ dans l'état LR(0) $q$ est défini par
        \begin{equation}\label{eq:dLAV}
          \text{DLA}(q,A\P\a)=\{X\mid
          S'\Da\d AX\w, X\Da ax,\mbox{ et }q=[\hat{\d}\a]\}.
        \end{equation}
  }\end{fdefinition}}
  
  \only<3-4>{\begin{fdefinition}{\colorize<4>
        L'ensemble des \define{fenêtres en conflit} pour une réduction par
        $A\P\a$ dans un ensemble d'états LR(0) $s$ est défini par
        \begin{align*}\label{eq:CLA}
          \text{CLA}(s,A\P\a)=\{&X\in\text{DLA}(q,A\P\a)\mid q\in
          s,
          ((q,X)\mbox{ ou } \exists p\in s,\\& X\in\text{DLA}(p,B\P\b))
          \mbox{ et }X\not\in\text{RLA}(q,A\P\a)\}.
        \end{align*}
        
        L'ensemble de \define{fenêtres non canoniques} pour une réduction par
        $A\P\a$ dans un ensemble d'états LR(0) $s$ est défini par
        \begin{equation}\label{eq:NLA}
          \text{NLA}(s,A\P\a)=\bigl(\bigcup_{q\in s}\text{DLA}(q,A\P\a)\bigr)-\text{CLA}(s,A\P\a).
        \end{equation}
  }\end{fdefinition}}
  
  \only<4-5>{\begin{theoreme}
      \begin{align*}
        \text{RLA}(q,A\P\a)=\{&X\mid X\Da ax,\psi\Da\e,
        C\D\r B\p\psi X\s\in\text{Kernel}(\d\r B)\mbox{ et }\\
        &(q,A\P\a)\rel{lookback}\circ\rela{includes}([\d\r],B)\}.
      \end{align*}
      Soit
      \begin{align*}%\label{eq:LAVrel}
        \text{DR}([\d],A)&=\{X\mid ([\d A],X)\mbox{ et }X\Da ax\},\\
        \intertext{alors}%\label{eq:LAV}
        \text{DLA}(q, A\P\a) &= \bigcup_{(q,A\P\a)\rel{lookback}\circ\rela{includes}\circ\rela{reads}(r,C)}\text{DR}(r,C).
      \end{align*}
  \end{theoreme}}
\end{frame}

\begin{frame}
  \frametitle{Exemple}
  \begin{exemple}
    Les fenêtres non canoniques pour la réduction par $A\P a$ dans l'état non
    canonique $\st{aa}=\{[BC^\ast a],[Aa^+]\}$ sont
    \begin{equation*}
      \begin{array}{r@{=}l}
        \text{RLA}([BC^\ast a],A\P a)&\{ A, \$ \},\\
        \text{DLA}([BC^\ast a],A\P a)&\{ A, a, \$ \},\\
        \text{CLA}(\st{aa},A\P a)&\{ a \},\mbox{ et}\\
        \text{NLA}(\st{aa},A\P a)&\{ A, \$ \}.
    \end{array}\end{equation*}
  \end{exemple}
\end{frame}

\begin{frame}
  \frametitle{État non canonique NLALR(1)}

  \begin{fdefinition}\label{def:nstate}
    L'\define{état non canonique} $\st{\d}$ est l'ensemble d'états LR(0)
    défini par
    \begin{align}
      \st{\e}=&\{[\e]\}\mbox{ et}\\
      \st{\d X}=&\begin{array}[t]{l}
        ~~~~\{[\widehat{\hat{\g} AX}]\mid X\in\text{CLA}(\st{\d},A\P\a)\mbox{
          et }[\hat{\g}\a]\in\st{\d}\}\\%%\mbox{ and}\\
        %%      ~~~~~~\psi CX\in\text{Cover}(\g AX)\}\\%%(q,A\P\a)\negthinspace\rel{lookback}\negthinspace\circ\negthinspace\rela{includes}\negthinspace\circ\negthinspace\rela{reads}\negthinspace([\g],C)\}\\
        \cup~\{[\f X]\mid[\f]\in\st{\d}\}.\\[-1em]
      \end{array}
    \end{align}
    
    La \define{transition non canonique} depuis $\st{\d}$ vers $\st{\d
      X}$ sur le symbole $X$, dénotée par $(\st{\d},X)$, existe si et
    seulement si $\st{\d X}\neq\emptyset$.
    
    La réduction $(\st{\d},A\P\a)$ existe si et seulement si il existe
    une réduction $(q,A\P\a)$ et si l'état LR(0) $q$ est un élément de
    $\st{\d}$.
  \end{fdefinition}
\end{frame}

\begin{frame}
  \frametitle{Exemple}
  \vspace{-10em}\hspace{-6em}$\negthickspace\negthickspace\negthickspace\negthickspace\negthickspace\negthickspace\negthickspace\negthickspace\negthickspace\negthickspace$\includegraphics{../fig/q1_BCAD}
\end{frame}

\begin{frame}
  \frametitle{Automate NLALR(1)}
  \begin{fdefinition}
    Un \define{automate NLALR(1)} pour la grammaire $\G$ a pour
   configuration initiale $\st{\e}\|w\eof$ avec $w$ la chaîne d'entrée
   de $\Sigma^\ast$, pour configuration finale $\st{\e}\st{S}\|\eof$,
   et des règles de réécriture de la forme
   \begin{itemize}
   \item\define{shift} $X$ dans l'état
     $\st{\d}$\mode<presentation>{\vspace{-1em}}
     \begin{equation}\label{eq:NLALR1_shift}
       \st{\d}\|X\shift\st{\d}\st{\d X}\|,
     \end{equation}\mode<presentation>{\vspace{-1em}}
     défini si il existe une transition $(\st{\d},X)$, ou
%%    \item\define{reduce} par $A\P X_1\dots X_n$ dans l'état
%%      $\st{\d X_1\dots X_n}$ \mode<presentation>{\vspace{-1em}}
%%      \begin{equation}\label{eq:NLR0_red}
%%        \st{\d X_1}\dots\st{\d X_1\dots X_n}\|\red{A\P
%%        X_1\dots X_n}\|A,
%%      \end{equation}\mode<presentation>{\vspace{-1em}}
%%      défini si $A\P X_1\dots X_n$ est une réduction de $\st{\d X_1\dots
%%      X_n}$, ou
   \item \define{reduce} par $A\P X_1\dots X_n$ dans l'état
     $\st{\d X_1\dots X_n}$ avec la fenêtre $X$\mode<presentation>{\vspace{-1em}}
     \begin{equation}\label{eq:NLA_red}
       \st{\d X_1}\dots\st{\d X_1\dots X_n}\|X\red{A\P
         X_1\dots X_n}\|AX,
     \end{equation}\mode<presentation>{\vspace{-1em}}
     défini si $A\P X_1\dots X_n$ est une réduction de $\st{\d X_1\dots
     X_n}$ et si la fenêtre $X$ appartient à $\text{NLA}(\st{\d X_1\dots
     X_n},A\P X_1\dots X_n)$.
   \end{itemize}
\end{fdefinition} 
  
\end{frame}

\section{Conclusion}

\begin{frame}
  \frametitle{En bref}
  \begin{itemize}
    \colorize<2>\item Des méthodes d'analyse déterministes.
    \colorize<3>\item Des méthodes plus puissantes que leurs pendants
    canoniques.
    \colorize<4>\item Analyse en temps linéaire si la fenêtre a une
    longueur bornée.
    \colorize<5>\item Peuvent être étendues pour utiliser une fenêtre
    de longueur non bornée à la LRR~!
  \end{itemize}
\end{frame}


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

\end{document}