%%
% formlang.tex
% Formal languages.
%
%% Document class choice
\documentclass[a4paper]{article}\usepackage{beamerarticle}
%\documentclass[ignorenonframetext]{beamer}

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

%% Meta information
\title{Grammaires algébriques}
\institute{Université de Nice Sophia Antipolis}
\date{2005/2006}

\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{Grammaires algébriques}
\frame{\partpage}

\section*{Motivation}

\subsection*{Définition}

Comment définir ce qu'est un langage~? Pour décrire les différents sens
prêtés à ce terme, le \textit{Trésors de la Langue Française} propose
les catégories suivantes~:

\begin{frame}
  \frametitle{Langage, \textipa{[l\~Aga\string:Z], n. m.~:}}
  \begin{enumerate}%[I]
    {\mode<presentation>{\large}
      \colorize<2>\item Faculté ou système\mode<presentation>{\vspace{.4em}}
      \begin{enumerate}%[A]
        {\mode<presentation>{\large}
          \shades<3>\item Faculté d'expression\mode<article>{ et de communication}\mode<presentation>{\vspace{.4em}}
          \colorize<3>\item Système de signes\mode<article>{ vocaux et/ou graphiques}\mode<presentation>{\vspace{.4em}}
          \begin{enumerate}%[1]
            {\mode<presentation>{\large}
              \colorize<4>\item Naturel\mode<presentation>{\vspace{.4em}}
              \colorize<4>\item Artificiel\mode<presentation>{\vspace{.4em}}
            }
          \end{enumerate}
        }
      \end{enumerate}
      \shades<2>\item Moyen d'expression\mode<article>{, usage}
    }
  \end{enumerate}
\end{frame}

L'analyse syntaxique est consacrée au traitement de textes issus de
tels systèmes de signes.

\mode<presentation>{\subsection*{Objectifs}}

\begin{frame}
  \frametitle{Syntaxe valide\uncover<2->{... ou non}}
  \begin{exemple}\label{ex:artiste}
    \begin{itemize}
      \shadesb<2>\item Cet artiste peint la nuit.
      \colorizeb<2>\item *Cet artiste la nuit peint.
      \shadesb<2>\item La nuit, cet artiste peint.
    \end{itemize}%
  \end{exemple}
  \uncover<3>{\emph{Formaliser} permet de reconnaître exactement ce qui
  est valide.}
\end{frame}

Cependant, l'analyse syntaxique n'est pas une fin en soi, mais une
étape vers l'analyse sémantique et la compréhension du texte. La
manière dont est décrit le langage doit se prêter à une analyse
sémantique, ce qui suppose qu'elle soit révélatrice de la structure
syntaxique du texte.

\begin{frame}
  \frametitle{Structure syntaxique}
  Exhiber une structure donne une interprétation {\colorize<1> sémantique}.
  \mode<article>{%
    Les linguistes décomposeraient la phrase «~Cet artiste peint la
    nuit.~» comme illustré dans la Figure~\ref{fig:artiste} à l'aide
    de \define{syntagmes}, de groupes syntaxiques~:
    \begin{description}
      \item[Ph] représente une phrase,
      \item[SN] représente un syntagme nominal,
      \item[SV] représente un syntagme verbal,
      \item[SP] représente un syntagme propositionnel.
    \end{description}
    \begin{figure}[ht]
      \begin{center}
        \includegraphics{../fig/artiste1_fig}\qquad
        \includegraphics{../fig/artiste2_fig}
        \caption{\label{fig:artiste}Deux structures possibles pour la
          phrase de l'Exemple~\ref{ex:artiste}.}
      \end{center}
    \end{figure}
  }
  \mode<presentation>{%
    \only<1>{\begin{center}\includegraphics{../fig/artiste1_fig}\end{center}}
    \only<2>{\begin{center}\includegraphics{../fig/artiste2_fig}\end{center}}
  }
\end{frame}

\begin{frame}
  \frametitle{Cycle de développement}
  \mode<article>{%
    \begin{figure}[ht]
      \begin{center}
        \includegraphics{../fig/devV1_fig}\qquad
        \includegraphics{../fig/devV2_fig}
        \caption{\label{fig:dev}Le cycle de développement logiciel en
          V.}
      \end{center}
    \end{figure}
    Le cycle de développement de la Figure~\ref{fig:dev} montre la vie
    (un peu idéalisée) d'un programme
    depuis sa spécification jusqu'aux tests vérifiant que
    l'implémentation vérifie bien les détails de la spécification. Ce
    cycle se prête à des erreurs en particulier lors de la phase
    d'implémentation.

    Un formalisme bien étudié utilisé comme spécification permet
    d'automatiser la tâche de dériver une implémentation~: celle-ci est
    alors assurée de respecter la spécification.

    C'est un objectif de plus pour la formalisation de la syntaxe~:
    pouvoir automatiquement dériver un analyseur syntaxique correct.
  }
  \mode<presentation>{%
    \only<1>{%
      \begin{center}
        \includegraphics{../fig/devV_fig}
      \end{center}
    }
    \only<2>{%
      \begin{center}
        \includegraphics{../fig/devV1_fig}
      \end{center}
    }
    \only<3>{%
      \begin{center}
        \includegraphics{../fig/devV2_fig}
      \end{center}
    }
  }
\end{frame}

\begin{frame}
  \frametitle{En bref}
  \begin{itemize}
    \colorize<1>\item Formaliser
    \colorize<1>\item Exhiber la structure
    \colorize<2>\item Permettre de dériver un analyseur
  \end{itemize}
%%   \begin{enumerate}
%%     \item Formaliser les langages\pause
%%     \item Raisonner sur la structure
%%   \end{enumerate}
  \tableofcontents[pausesections,part=1]
\end{frame}

\section{Langages}

Comment comprendre un langage d'un point de vue mathématique~? C'est
un ensemble de séquences de symboles, tous issus d'un alphabet. En
algèbre, on définit des monoïdes pour représenter cette structure.

\subsection{Monoïdes}
\begin{fdefinition}
  Un triplet $\tup{M,\cdot,\e}$ est un \define{monoïde} si
  \begin{itemize}
    \item $M$ est un ensemble,
    \item $\cdot$ est une opération binaire \define{associative},
      vérifiant donc pour tout $x$, $y$ et $z$ de $M$
      \begin{equation}
        x\cdot(y\cdot z) = (x\cdot y)\cdot z,
      \end{equation}
    \item et $\e$ est l'\define{identité} pour $\cdot$, c'est-à-dire
      que pour tout $x$ de $M$
      \begin{equation}
        \e\cdot x = x\cdot\e = x.
      \end{equation}
  \end{itemize}
\end{fdefinition}

\begin{exemple}
  Le singleton $\{x\}$ est un monoïde trivial pour $x\cdot x=x$.

  Étant donné un ensemble $A$, l'ensemble des fonctions de $A$ dans $A$
  est un monoïde utilisant la composition de fonctions~; la
  fonction identité sert simplement d'identité.

  L'ensemble des listes bâties sur un ensemble est un monoïde~:
  la concaténation sert d'opération binaire, et la liste vide
  d'identité.
\end{exemple}

Le couple $\tup{M,\cdot}$ est un \define{semigroupe}, et on appelle
donc aussi un monoïde un semigroupe avec identité. Un semigroupe
ne peut avoir qu'une seule identité.

%% Un monoïde est un \define{groupe} si chacun de ces éléments possède un
%% inverse dans $M$~; ce n'est pas le cas du monoïde des listes de
%% l'exemple précédent.

L'opération de concaténation $\cdot$ est souvent plus simplement
dénotée par la juxtaposition, c'est-à-dire que $x\cdot y$ s'écrit plus
simplement $xy$.

On définit ensuite sur la base de $\cdot$ la puissance $n$ d'un
élément $x$ de $M$ par
\begin{align}
  x^0 &= \e\text{ et}\\
  x^n &= x x^{n-1}\text{ pour }n>1.
\end{align}

On étend souvent les opérations sur des éléments de $M$ à des
opérations sur des sous-ensembles de $M$, dans le cas de $\cdot$, cela
donne étant donnés deux sous-ensembles $A$ et $B$ de $M$
\begin{equation}
  A\cdot B = \{x\cdot y\mid x\in A\text{ et }y\in B\}.
\end{equation}
Le triplet $\tup{2^M,\cdot,\{\e\}}$ est alors lui aussi un monoïde.

\begin{fdefinition}
  Un sous-ensemble $A$ d'un monoïde $M$ est \define{fermé} si pour
  tout nombre naturel $n$
  \begin{equation}
    x_1, \dots, x_n\in A\text{ implique }x_1\cdots x_n\in A.
  \end{equation}
\end{fdefinition}
Si $A$ est un sous-ensemble fermé de $M$, alors $\tup{A,\cdot,\e}$ est
aussi un monoïde.

\begin{fdefinition}
  La \define{fermeture} d'un sous-ensemble $A$ d'un monoïde $M$ est
  \begin{equation}
    A^\ast=\bigcup^\infty_{n=0}A^n.
  \end{equation}
\end{fdefinition}

\begin{lemme}
  Soit $A$ un sous-ensemble de $M$. Alors $A^\ast$ est le plus
  petit sous-ensemble fermé de $M$ contenant $A$.
\end{lemme}

$A$ génère $M$ si $A^\ast=M$, et le génère \define{librement} s'il
existe pour chaque élément $x$ de M une unique décomposition
$x_1\cdots x_n$ en éléments de $A$. Le triplet $\tup{A^\ast,\cdot,\e}$
est donc trivialement un monoïde libre généré par $A$.

\begin{lemme}
  Si $M$ est un monoïde libre, alors il est \define{simplifiable} à
  gauche et à droite, c'est-à-dire que pour tout $x$, $y$ et $z$ de
  $M$,
  \begin{align}
    zx=zy&\text{ implique }x=y\text{ et}\\
    xz=yz&\text{ implique }x=y.
  \end{align}
\end{lemme}

\subsection{Langages formels}
Un ensemble $\Sigma$ est un \define{alphabet} ou
\define{vocabulaire} s'il est fini et non vide.

\begin{frame}
  \frametitle<presentation>{Langages}

  \uncover<1->{\begin{fdefinition}
    Un \define{langage formel} sur un \define{alphabet} $\Sigma$ est
    un sous-ensemble du \define{monoïde libre} $\tup{\Sigma^\ast,\cdot,\e}$
    généré par $\Sigma$.
  \end{fdefinition}}

  \mode<presentation>{
    \begin{itemize}
    \item<2-> $\Sigma$ est un ensemble fini non vide

    \item<3-> $\cdot$ est une opération de concaténation \define{associative}
      \only<3>{~: $\cdot: \Sigma^\ast\times
        \Sigma^\ast\rightarrow \Sigma^\ast$ vérifie
        \begin{equation}
          x\cdot(y\cdot z) = (x\cdot y)\cdot z
        \end{equation}
      }

    \item<4-> $\e$ est son \define{identité}
      \only<4>{
        \begin{equation}
          x\in\Sigma^\ast\text{ implique }\e\cdot x = x\cdot\e = x
        \end{equation}
    }

    \item<5-> $\Sigma^\ast$ est la \define{fermeture} de $\Sigma$
      \only<5>{
        \begin{equation}
          \Sigma^\ast=\bigcup^\infty_{n=0}\Sigma^n%=\bigcup^\infty_{n=1}\{a\cdot
          %x\mid a\in\Sigma\text{ et }x\in\Sigma^{n-1}\}\cup\Sigma^0
        \end{equation}
        %où $\Sigma^0=\{\e\}$
      }
    \end{itemize}
  }

  \only<6>{
    \begin{exemple}
      Soit $\Sigma=\{a,b\}$~; $\{a^nb^n\mid n\geq 0\}$ et $\{ww\mid
      w\in\Sigma^\ast\}$ sont des langages.
    \end{exemple}
  }
\end{frame}

\begin{exercice}
  Donner un exemple de semigroupe qui n'est pas un monoïde.
\end{exercice}
\begin{exercice}
  Prouver qu'un semigroupe ne peut avoir qu'une unique identité.
\end{exercice}
\begin{exercice}
  Montrer que pour tout ensemble $A$, $\tup{2^A,\cap,A}$ et
  $\tup{2^A,\cup,\emptyset}$ sont des monoïdes.
\end{exercice}

\begin{frame}
  \frametitle{Le français comme un ensemble}
  \begin{exemple}
    {\colorize<2>
      \begin{equation*}\Sigma=\{\text{Adj},\text{Adv},\text{Det},\text{N},\text{Prep},\text{V}\},\end{equation*}}
    {\colorize<3>
      \begin{align*}
        {\cal L}_{\text{français}}=\{&\text{Det N V},\\
        &\text{Det Adj N V},\\
        &\text{Det N V Adj},\\
        &\text{Det Adj N V Adj},\\
        &\text{Det N V Det N},\\
        &\dots~\}.
      \end{align*}}
  \end{exemple}
  \uncover<4>{... pas très pratique... et aucune structure~!}
\end{frame}

\subsection{Opérations sur les langages}

La définition précédente n'est pas suffisante si l'on souhaite
\begin{enumerate}
\item se représenter un langage~: les langages non bornés sont souvent
  difficiles à représenter sous forme d'ensembles~;
\item associer une structure au langage~: que ce soit dans le cadre
  des langages de programmation ou dans celui des langues naturelles,
  l'analyse du texte a pour objectif d'expliciter la structure du
  texte et de permettre l'analyse sémantique.
\end{enumerate}

\begin{frame}
  \frametitle{Opérations}
  \begin{itemize}
    \colorize<2>\item opérations ensemblistes (union, intersection,
      complément)~: $\cup, \cap, -$,
    \colorize<3>\item concaténation (ou produit cartésien)~: ${\cal L}_1{\cal
    L}_2=\{xy\mid x\in{\cal L}_1,y\in{\cal L}_2\}$, étendue par ${\cal
    L}^0=\{\e\}$ et, pour $i\geq 0$, ${\cal L}^{i+1}={\cal L}^i{\cal
    L}$,
    \colorize<4>\item étoile de Kleene~: ${\cal L}^\ast=\cup_{i\geq 0}{\cal L}^i$,
    \colorize<5>\item plus de Kleene~: ${\cal L}^+=\cup_{i\geq 1}{\cal
      L}^i$,
    \colorize<6>\item quotient gauche~: ${\cal L}_2\backslash{\cal
      L}_1=\{w\mid\exists x\in{\cal L}_2, xw\in{\cal L}_1\}$,
    \colorize<6>\item quotient droit~: ${\cal L}_1/{\cal
      L}_2=\{w\mid\exists x\in{\cal L}_2, wx\in{\cal L}_1\}$,
    \shades<7>\item ...
  \end{itemize}
\end{frame}\footnote{%
L'ensemble $\Sigma^\ast$ avec les opérations d'union $\cup$ et de
concaténation $\cdot$ et la fonction d'étoile de Kleene $^\ast$ forme
une \define{algèbre de Kleene}. Les expressions finies dans cette algèbre
sont appelées \define{expressions rationnelles}, et définissent les
langages rationnels. Les structures algébriques sont encore un autre moyen
de décrire des classes de langages formels~!}

\begin{frame}
  \frametitle{Diviser pour régner}
  \begin{exemple}\label{ex:diviser}
      \begin{align*}
        {\cal L}_{\text{français}}=&{\cal L}_\text{Ph}^+\\
        {\cal L}_\text{Ph}=&{\cal L}_\text{SN}{\cal
          L}_\text{SV}\\
        \cup&{\cal L}_\text{SN}{\cal L}_\text{SV}{\cal L}_\text{SP}\\
        \cup&\dots\\
        {\cal
          L}_\text{SN}=&\{\text{Det}\}{\cal L}_\text{SA}\{\text{N}\}{\cal L}_\text{SA}\\
    {\cal L}_\text{SV}=&\{\text{V}\}\\
    \cup&\{\text{V}\}{\cal L}_\text{SA}\\
    \cup&\{\text{V}\}{\cal L}_\text{SN}\\
    \cup&\dots\\
    {\cal L}_\text{SA}=&\{\text{Adj}\}^\ast\\
    &\dots
      \end{align*}
  \end{exemple}
\end{frame}
En subdivisant le langage ${\cal L}_{\text{français}}$ en ses
constituants, sa structure devient apparente. Nos deux objectifs de
formalisation et de structuration de la syntaxe semblent maintenant
remplis. En revanche, la dérivation d'un analyseur syntaxique depuis
cette formalisation n'est pas encore très claire. De plus, la
formulation est un peu lourde.

Les deux formulations suivantes sont plus lisibles. Elles ont été
développées indépendamment par Chomsky dans~\cite{chomsky56} en vue de
formaliser la syntaxe de la langue anglaise, et par Backus
dans~\cite{bnf} pour la syntaxe d'{\sc Algol 60}~\cite{algol60}.  On
devra à Ginsburg le rapprochement des communautés de linguistes et
d'informaticiens~\cite{GinsburgR62}.

\begin{frame}
  \frametitle{Grammaire syntagmatique~\cite{chomsky56}}
  \begin{exemple}\mode<presentation>{\vspace{-3em}}\label{ex:cfg}
    \begin{align*}
      \text{français}\P&\text{français}~\text{Ph}\\
      \text{français}\P&\text{Ph}\\
      \text{Ph}\P&\text{SN}~\text{SV}\\
      \text{Ph}\P&\text{SN}~\text{SV}~\text{SP}\\
      \text{Ph}\P&\dots\\
      \text{SN}\P&\text{Det}~\text{SA}~\text{N}~\text{SA}\\
      \text{SV}\P&\text{V}\\
      \text{SV}\P&\text{V}~\text{SA}\\
      \text{SV}\P&\text{V}~\text{SN}\\
      \text{SV}\P&\dots\\
      \text{SA}\P&\text{SA}~\text{Adj}\\
      \text{SA}\P&\e
    \end{align*}
  \end{exemple}
\end{frame}

\begin{frame}
  \frametitle{Forme de Backus-Naur (BNF)~\cite{bnf}}
  \begin{exemple}\mode<presentation>{\vspace{-3em}}\label{ex:bnf}
    \begin{align*}
      \N{francais}::=&\N{francais}~\N{Ph}\\
      \N{francais}::=&\N{Ph}\\
      \N{Ph}::=&\N{SN}~\N{SV}\\
      \N{Ph}::=&\N{SN}~\N{SV}~\N{SP}\\
      \N{Ph}::=&\dots\\
      \N{SN}::=&\text{Det}~\N{SA}~\text{N}~\N{SA}\\
      \N{SV}::=&\text{V}\\
      \N{SV}::=&\text{V}~\N{SA}\\
      \N{SV}::=&\text{V}~\N{SN}\\
      \N{SV}::=&\dots\\
      \N{SA}::=&\N{SA}~\text{Adj}\\
      \N{SA}::=&\e
    \end{align*}
  \end{exemple}
\end{frame}

Nous allons vérifier que ces formulations sont bien équivalentes à la
décomposition en sous-langages de l'Exemple~\ref{ex:diviser}.

\section{Systèmes de réécriture}

Les formalisations précédentes sont en fait des systèmes de
réécriture.

\subsection{Définitions}

\begin{frame}
  \frametitle{Systèmes de réécriture}
  \begin{fdefinition}
    $\tup{V,P}$ est un \define{système de réécriture}
    \begin{itemize}
    \colorize<2>\item $V$ est un vocabulaire et
    \colorize<3>\item $P$ un sous-ensemble de $\Va\times\Va$.
    \end{itemize}
    \uncover<4>{Les éléments $\a\P\b$ de $P$ sont appelés des
      \define{règles de réécriture}.}
  \end{fdefinition}
\end{frame}

\begin{frame}
  \frametitle{Dérivations}
  \begin{fdefinition}\mode<article>{Soit $\tup{V,P}$ un système de réécriture.}
    La relation de \define{dérivation} $\Di[r]$ sur $\Va$ est
    définie \mode<article>{pour tout $\f$ et $\s$ de $\Va$} par
    \begin{equation}
      \f{\colorize<2>\a}\s\Di[r]\f{\colorize<3>\b}\s\text{ ssi
      }r={\colorize<2>\a}\P{\colorize<3>\b}\in P.
    \end{equation}

    \uncover<4-> {Cette relation est étendue aux séquences de règles dans le
      monoïde libre $P^\ast$ par
      \begin{align*}
        \Di[\e]&=\text{id}_{\Va}\\
        \Di[r\pi]&=\Di[r]\Di[\pi].
      \end{align*}
    }\mode<article>{Enfin,}\mode<presentation>{\vspace{-3em}}
    \uncover<5>{%
      \begin{align*}
        \D&=\bigcup_{r\in P}\Di[r]\text{ et}\\
        \Da&=\bigcup_{\pi\in P^\ast}\Di[\pi].
      \end{align*}
    }
  \end{fdefinition}
\end{frame}

\begin{frame}
  \frametitle{Langage décrit par un système de réécriture}
  On distingue souvent une chaîne de caractères $\r$ de $\Va$~; on peut
  alors définir un langage par
  \begin{itemize}
  \colorize<2>\item génération depuis l'axiome $\r$ comme
    \begin{equation}
      \L(\tup{V,P})=\{\w\mid\r\Da\w\},
    \end{equation}\mode<article>{ou bien par}
  \colorize<3>\item reconnaissance dans l'état d'acceptation $\r$ comme
    \begin{equation}
      \L(\tup{V,P})=\{\w\mid\w\models^\ast\r\}.
    \end{equation}
  \end{itemize}
  \uncover<3>{(Dans ce dernier cas, on substitue les notations
    $\vdash$ et $\models$ à $\P$ et $\D$.)}

  {\colorize<4> Deux systèmes $\tup{V_1,P_1}$ et $\tup{V_2,P_2}$ sont
    équivalents si $\L(\tup{V_1,P_1})=\L(\tup{V_2,P_2})$.}
\end{frame}

\subsection{Grammaires}
\begin{frame}
  \frametitle{Grammaires syntagmatiques~\cite{chomsky59}}
  \begin{fdefinition}
    Un quadruplet $\tup{\Sigma,N,S,P}$ est une \define{grammaire
      syntagmatique} $\G$ (en anglais \textit{phrase structure grammar})~:
    \begin{itemize}
      \colorize<2>\item $\Sigma$ est l'alphabet terminal,
      \colorize<3>\item $N$ est l'alphabet non terminal,
      \colorize<4>\item $S\in N$ est l'axiome,
      \colorize<5>\item $P$ est un ensemble de règles de la forme $\f
      A\s\P\f\a\s$ où $A\in N$.
    \end{itemize}
    \uncover<6>{Soit $V=\Sigma\cup N$ le vocabulaire, $\tup{V,P}$ est bien un
      système de réécriture génératif.}
  \end{fdefinition}
\end{frame}

\begin{frame}
  \frametitle{Conventions de notation}
  \begin{itemize}
    \colorize<2>\item $a,b,c,d, \dots$ sont des éléments de $\Sigma$;
    \colorize<3>\item $A,B,C,D, \dots$ sont des éléments de $N$;
    \colorize<4>\item $X,Y,Z$ sont des éléments de $V$;
    \colorize<5>\item $u,v,w,x,y,z$ sont des éléments de
    $\Sigma^\ast$;
    \colorize<6>\item $\a,\b,\g,\d, \dots$ sont des éléments de $\Va$.
  \end{itemize}
\end{frame}


\begin{frame}
  \frametitle{Hiérarchie de Chomsky~\cite{chomsky59}}
  Restrictions sur la forme des règles de $P$~:
  \begin{enumerate}\setcounter{enumi}{-1}
    \colorize<2>\item $\a\P\b$ avec $\a$ dans $\Vp$ et $\b$ dans $\Va$~:
    grammaires contextuelles avec effacement~;\mode<article>{ ne sont
    pas des grammaires syntagmatiques~;}
    \colorize<3>\item $\f A\s\P\f\a\s$ avec $\f$ et $\s$ dans $\Va$, $A$ dans $N$
    et $\a$ dans $\Vp$~: grammaires contextuelles ou monotones~;
    \colorize<4>\item $A\P\a$ avec $A$ dans $N$ et $\a$ dans $\Va$~: grammaires
    non contextuelles ou algébriques~;
    \colorize<5>\item $A\P\a$ avec $A$ dans $N$ et $\a$ dans $\Sigma^\ast$ ou dans
    $\Sigma^\ast\cdot N$~: grammaires linéaires à droite.
  \end{enumerate}
\end{frame}

\begin{frame}
  \frametitle{Machines et automates}
  La hiérarchie de Chomsky trouve un écho dans les systèmes de
  réécriture recognitifs~:
  \begin{enumerate}\setcounter{enumi}{-1}
    \colorize<2>\item Langages récursivement énumérables,
    reconnaissables par une Machine de Turing (TM)~;
    \colorize<3>\item Langages contextuels,
    reconnaissables par une Machine de Turing dont le ruban a une
    longueur linéaire de la taille des données traitées (LBTM)~;
    \colorize<4>\item Langages non contextuels ou algébriques,
    reconnaissables par un automate à pile (\textit{Push-Down
    Automaton}, PDA)~;
    \colorize<5>\item Langages rationnels, reconnaissables par un
    automate d'états finis (\textit{Finite-State Automaton}, FSA).
  \end{enumerate}
\end{frame}

Nous voici en possession d'une équivalence entre langages générés par
certains systèmes génératifs et langages reconnus par certains
systèmes recognitifs. Nous ne sommes plus si éloignés d'une dérivation
automatique d'un analyseur syntaxique.

\begin{exercice}
  Donner un algorithme de transformation d'une grammaire linéaire à
  droite en grammaire linéaire à gauche.
\end{exercice}
\begin{exercice}
  Donner un algorithme de construction d'un automate d'états finis
  équivalent à une grammaire linéaire à droite. On en déduit par le
  théorème de Kleene~\cite{kleene} que les expressions rationnelles
  sont une autre description finie des grammaires linéaires.
\end{exercice}

\subsection{Grammaires algébriques}

Les grammaires algébriques modélisent les notations vues dans les
Exemples~\ref{ex:cfg} et~\ref{ex:bnf}.

\begin{frame}
  \frametitle{Langages algébriques}
  L'ensemble des langages algébriques est fermé par
  \begin{itemize}
    \colorize<2>\item union
    \colorize<3>\item concaténation
    \item<4> intersection avec un langage rationnel
    \item<5> homomorphisme
    \item<6> \dots
  \end{itemize}
\end{frame}

Les deux premiers points montrent que les notations de Chomsky et
de Backus-Naur des Exemples~\ref{ex:cfg} et~\ref{ex:bnf} sont bien
équivalentes aux équations de langages de l'Exemple~\ref{ex:diviser}.

\begin{frame}
  \frametitle{Dérivations droites et gauches}
  \begin{fdefinition}
    Une \define{dérivation droite} $\Dr$ est définie par
    \begin{equation}
      \f {\colorize<2>Ax}\Dr\f{\colorize<3>\a x}\text{ ssi }A\P\a\in P
    \end{equation}
  \end{fdefinition}
  \begin{fdefinition}
    Une \define{dérivation gauche} $\Dl$ est définie par
    \begin{equation}
      {\colorize<4> yA}\s\Dl {\colorize<5> y\a}\s\text{ ssi }A\P\a\in P
    \end{equation}
  \end{fdefinition}
\end{frame}

\begin{frame}
  \frametitle{Parcours d'un arbre syntaxique}
  \begin{exemple}
    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->{\begin{center}\includegraphics{../fig/artiste_Dr4_fig}\end{center}}
  \end{exemple}
  \uncover<5>{Une seule dérivation droite (ou gauche) par arbre de
    dérivation.}
\end{frame}

\begin{frame}
  \frametitle{Ambiguïté}
  L'existence de deux arbres syntaxiques différents marque une
  ambiguïté.
  \begin{theoreme}
    Soit $\G$ une grammaire algébrique~; elle est ambiguë si et
    seulement si une phrase de ${\cal L}_\G$ possède plus d'une
    dérivation droite (ou gauche).
  \end{theoreme}
  Il existe des langages algébriques intrinsèquement ambigus.
  \begin{exemple}[\cite{parikh}]
    Le langage $\{a^ib^jc^k\mid i=j\text{ ou }j=k\}$ est intrinsèquement ambigu.
  \end{exemple}
  \begin{theoreme}[\cite{cantor,CS63}]
    Le problème de l'ambiguïté d'une grammaire algébrique n'est pas
    décidable.
  \end{theoreme}
\end{frame}

\subsection{Analyseurs}

\begin{frame}
  \frametitle{Automate à pile}
  \begin{fdefinition}
    Un \define{automate à pile} ${\cal A}=\tup{Q,\Sigma,R,\f_s,F,\$,\|}$
    est un système de réécriture $\tup{Q\cup\Sigma\cup\{\$,\|\},R}$
    recognitif où
    \begin{itemize}
      \colorize<2>\item $Q$ est l'alphabet de pile,
      \colorize<3>\item $\Sigma$ est l'alphabet d'entrée,
      \colorize<4>\item $R\subseteq\{\$\}\cdot Q^\ast\cdot\{\|\}\cdot\Sigma^\ast\cdot\{\$\}$ est un ensemble de règles
      \begin{equation}
        \f\|xy\vdash\psi\|y,
      \end{equation}\mode<presentation>{\vspace{-2em}}
      \colorize<4>\item $\f_s\in Q^\ast$ est le contenu initial de la
      pile,
      \colorize<5>\item $F\subseteq Q^\ast$ est l'ensemble des contenus
      finaux de la pile,
      \colorize<6>\item $\$$ est le marqueur de fin, et
      \colorize<7>\item $\|$ est le délimiteur de sommet de pile.
    \end{itemize}
    {\colorize<8>\begin{equation}
      {\cal L}_{\cal A}=\{w\mid\$\f_s\|w\$\models^\ast\$\f_f\|\$\text{
      avec }\f_f\in F\}.
      \end{equation}
    }
  \end{fdefinition}
\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{Transducteur à pile}
  L'analyse précédente ne dit que si une phrase appartient au langage
  de $\G$ ou non.
  \begin{fdefinition}
    Un \define{transducteur à pile} $\tup{{\cal A},\t}$ pour $\G$ est
    constitué d'un automate à pile ${\cal A}$ pour $\G$ et d'un
    homomorphisme $\t$ de $R^\ast$ dans $P^\ast$ défini par
    \begin{align*}
      \t([A\P\a\p B\a']\|\vd{predict}[A\P\a B\p\a'][B\P\p\b]\|)=&B\P\b,\\
      \t([A\P\a\p a\a']\|a\vd{match}[A\P\a a\p\a'])=&\e, et\\
      \t([A\P\a\p]\|\vdash\|)=&\e.
    \end{align*}
  \end{fdefinition}
  L'exemple précédent donnait les productions dans l'ordre d'une dérivation
  gauche.
\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>{La suite du cours sera consacrée à des constructions de machines
  déterministes plus puissantes.}
\end{frame}

\section{Conclusion}
\begin{frame}
  \frametitle{En résumé}
  Les grammaires algébriques permettent
  \begin{enumerate}
    \colorize<2>\item de générer des langages formels de la classe des
    langages algébriques~;
    \colorize<3>\item de structurer la syntaxe sous forme d'arbres de
    dérivation~;
    \colorize<4>\item une analyse à l'aide d'automates à pile.
  \end{enumerate}
  \uncover<5->{Sur la dérivation d'un analyseur syntaxique généraliste,
    lire~\cite{earley} en préparation de la séance numéro~4.}
\end{frame}

\begin{frame}
  \frametitle{Questions~?}
\end{frame}

\subsection{Exercices}
\begin{frame}
  \frametitle{Exercices}
  \only<1>{\begin{exercice}
      Soit la grammaire
      \gdf[ETF]{E\P E+T\gor T,~T\P T*F\gor F,~F\P a\gor(E).}
      Donner les arbres de dérivation correspondant aux phrases
      \begin{enumerate}
      \item $a+a*a+a$ et
      \item $a*(a+a+a)$.
      \end{enumerate}
      Donnez les étapes de l'analyse de ces phrases par
      un automate à pile récursif descendant.
  \end{exercice}}
  \only<2>{\begin{exercice}
      Le langage $\{a^ib^jc^k\mid i=j\text{ ou }j=k\}$ est
      intrinsèquement ambigu. Donnez une grammaire algébrique générant
      ce langage. Montrez l'ambiguïté de cette grammaire.
  \end{exercice}}
\end{frame}

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

\end{document}