\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
%\usepackage[french]{babel}
%\frenchbsetup{StandardLists=true}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{amsthm}
\usepackage{enumitem}
\usepackage{multirow}

\usepackage[french, onelanguage, ruled,vlined]{algorithm2e}
\SetKwFor{Tantque}{Tant que}{ :}{}
\SetKwBlock{Choix}{Choisir :}{}
\SetKwFor{Soit}{soit}{}{}
\SetKw{ChoisirKw}{Choisir}

\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}

\usepackage{tikz}
\usetikzlibrary{arrows, automata, positioning}

\makeatletter
\newcommand{\xRightarrow}[2][]{\ext@arrow 0359\Rightarrowfill@{#1}{#2}}
\makeatother
\newcommand{\T}[1]{\mathrm{#1}}
\newcommand{\sbullet}{\text{\footnotesize $\bullet$}}

\title{Exemple d'analyse LR(0)}
\author{Mathias Millet}
\date{2014}




\begin{document}

\maketitle

\section*{Introduction}

Analyse syntaxique : à partir d'un mot, on souhaite :
\begin{itemize}
\item savoir s'il appartien au language d'une grammaire donnée.
\item reconstruire l'arbre syntaxique qui l'a engendré.
\end{itemize}



\paragraph{Définitions préliminaires et conventions :}
Soit  $G = (V_N, V_T, P, S)$ une grammaire non-contextuelle, c'est à dire que l'on a :
\begin{itemize}
\item $V_N$ est l'ensemble des symboles non-terminaux. 
\item $V_T$ est l'ensemble des symboles terminaux.
\item $P$ est l'ensemble des productions de la grammaire, avec $P \subset V_N \times (V_N + V_T)^*$.
\item $S \in V_N$ est l'axiome de la grammaire.
\end{itemize}


On utilisera les conventions suivantes :
\begin{itemize}
\item Les éléments de $V_N$ seront représentés par les lettres $A, B, C, D, ...$ et  $S$
\item Les éléments de $V_T$ seront représentés par les lettres $\T{a, b, c}, ...$; les éléments de $V_T^*$ par les lettres $\T{u, v, w}, ...$
\item Les éléments de $V_N \cup V_T$ seront représentés par les lettres $X, Y, ...$; les éléments de $(V_N \cup V_T)^*$ par les lettres $\alpha, \beta, ...$. Le mot vide sera représenté par $\epsilon$.
\item Un élément $(A, \alpha)$ de $P$ sera noté $A \rightarrow \alpha$.
\end{itemize}


\subsection*{Analyse syntaxique ascendante}

L'analyse ascendante (avec lecture de gauche à droite) fonctionne de la manière suivante :
\begin{itemize}
\item On garde en mémoire un mot $\alpha$ sur $V_N \cup V_T$, qui correspondra à la partie déjà reconnue.
\item On peut alors 
	\begin{itemize}
		\item Soit lire un caractère supplémentaire du mot d'entrée, auquel cas on ajoute ce caractère à $\alpha$
		\item Soit identifier le suffixe de $\alpha$ à la partie droite $\delta$ d'une production de la grammaire $D \rightarrow \delta$, auquel cas on remplace $\delta$ par la partie gauche $D$ associée.
	\end{itemize}
\end{itemize}

Cela correspond à l'algorithme non-déterministe ci-dessous :

\begin{algorithm}[H]
\DontPrintSemicolon
\caption{Analyse ascendante()}
 \KwIn{Grammaire $G$, mot $\T w$}
 $\alpha \longleftarrow ""$\; 
 $i \longleftarrow 0$\;
 
\Tantque{$\alpha \not = S \text{ et } i \leq |w|$}{
	\Choix{
		\Soit{Lecture}{$\alpha \longleftarrow \alpha \T w_i$\;
		$i \longleftarrow i +1$
		}
		\Soit{Réduction}{
				\ChoisirKw $(\delta_0, D_0, \beta_0) \in \{(\delta, D, \beta) \text{ tels que } \alpha = \beta \delta \text{ et } (D \rightarrow \delta) \in P\}$\;
				$\alpha \longleftarrow \beta_0 D_0$ \;
		}
	}
}
\end{algorithm}






\subsection*{Exemple}
Nous illustrerons ce développement à l'aide de la grammaire suivante :
\begin{center}
$G_0 = (\{S\}, \{c, + \}, \{S \rightarrow SS+, S \rightarrow c \}, S)$
\end{center}
qui représente les expressions arithmétiques de l'opérateur $+$ en notation post-fixée.

\begin{figure}[h]
\centering \caption{Arbre syntaxique correspondant au mot $cc+c+$}
\begin{tikzpicture} [scale=.6]
\tikzstyle{level 1}=[sibling distance=20mm] 
\tikzstyle{level 2}=[sibling distance=10mm] 
\tikzstyle{level 3}=[sibling distance=10mm] 

 \node{S}  
  child{ node{S}child{node{S}child{node{c}}}
  				child{node{S}child{node{c}}}
  				child{child{node{+}}}}
   child{node{S}child{child{node{c}}}}
   child{child{child{node{+}}}}
  ; 
 \end{tikzpicture}
\end{figure}
 
 
\section*{Automate des items}

%Soit  $G = (V_N, V_T, P, S)$ une grammaire non-contextuelle, on appelle grammaire augmentée de $G$ la grammaire $G' = (V_N', V_T, P', S')$ avec $V_N' = V_N \cup \{S'\}$, et $P' = P  \cup (S \rightarrow S')$. Ainsi, on a seulement rajouté un axiome fictif à $G$, qui n'apparaitra dans aucune autre règle.


\paragraph{Définition (Item)} Les items de la grammaire $G$ sont les triplets $(A, \alpha, \beta)$ tels que $A \rightarrow \alpha \beta$ est une production de $P$. On notera $[A \rightarrow \alpha \sbullet \beta]$ un tel item. 

Un item $[A \rightarrow \alpha \sbullet]$ sera dit complet.\\

À partir des items d'une grammaire, on considèrera l'automate non déterministe $AFN_G = (Q, V_N \cup V_T, \Delta, Q_0, F)$ suivant, appellé automate des items de la grammaire :
\begin{itemize}
\item Chaque état de $Q$ correspond à un item de la grammaire.
\item L'alphabet d'entrée est constitué des terminaux et des non-terminaux.
\item La fonction de transition $\Delta$ est telle que 
	\begin{itemize}
	\item $\Delta([A \rightarrow \alpha \sbullet B \beta], \epsilon) = \{ [B \rightarrow \sbullet \gamma] \text{ où } B \rightarrow  \gamma \text{ est une production} \}$ 
	\item $\Delta([A \rightarrow \alpha \sbullet X \beta], X) = \{[A \rightarrow \alpha  X \sbullet \beta] \}$
	\end{itemize}
\item L'ensemble des états initiaux est  $Q_0 = \{[S \rightarrow \sbullet \alpha] , S \rightarrow \alpha \in P\}$.
\item Tous les états sont finaux : $F = Q$.
\end{itemize}

\paragraph{Théorème}
Soit $\gamma \in (V_N \cup V_T)^*$, on a, pour tout item $[A \rightarrow \alpha \sbullet \beta]$ tel que $\alpha$ est un suffixe de $\gamma$ (avec $\delta$ tel que $\gamma = \delta\alpha$):
\begin{center}
$[ A \rightarrow \alpha \sbullet \beta] \in \Delta(q_0, \delta \alpha)\quad $ ssi 
$\quad \exists \T w \text{ tels que } S \xRightarrow{*}_d \delta A \T w \Rightarrow \delta \alpha \beta \T w$
\end{center}

Autrement dit, la lecture d'un mot $\gamma$ par l'automate nous amène dans les états correspondants aux items $[ A \rightarrow \alpha \sbullet \beta]$ où $\alpha$ est un suffixe de $\gamma$. Cela correspond au fait que l'on est en train d'essayer d'associer un suffixe de $\gamma$ avec la partie droite de $(A \rightarrow \alpha \beta)$, et que $\alpha$ a déjà été reconnu. Si tout $\beta = \epsilon$, toute la partie droite de la règle est reconnue, et on pourra alors réduire en $A$, comme on le verra dans la partie suivante.

\subparagraph{Idée de la démonstration} 
\begin{description}
\item[$\boxed{\Rightarrow}$] Induction sur la longueur du chemin.
\item[$\boxed{\Leftarrow}$] On montre que $[A \rightarrow \sbullet \alpha \beta] \in \Delta(q_0, \delta)$ par induction sur la longueur de la dérivation $S \xRightarrow{*}_d \delta A \T w \Rightarrow_d \delta \alpha \beta \T w$

\end{description}

\begin{figure}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
  thick,state/.style={rectangle,draw}]
  
  \node[initial above, state] (0) {$[S \rightarrow \sbullet SS+]$};
  \node[state] (1) [right=3cm of 0] {$[S \rightarrow S \sbullet S+]$};
  \node[state] (2) [below of=1] {$[S \rightarrow SS \sbullet +]$};
  \node[state] (3) [below of=2] {$[S \rightarrow SS+ \sbullet ]$};
  \node[initial left, state] (4) [below of=0] {$[S \rightarrow \sbullet c ]$};
  \node[state] (5) [below of=4] {$[S \rightarrow c \sbullet ]$};

  \path[every node/.style={font=\sffamily\small}]
  	(0) edge [bend left] node [above] {$S$} (1)
  		edge node [left] {$\epsilon$} (4)
  		edge [loop left] node [right] {$\epsilon$} (0) 
  	(1) edge node [right] {$S$} (2)
  		edge node [below] {$\epsilon$} (0)
  		edge node [below] {$\epsilon$} (4)
  	(2) edge node [right] {$+$} (3)
  	(4) edge node [right] {$c$} (5)
  	;
\end{tikzpicture}
\caption{Automate des items de la grammaire $G_0$}
\end{figure}

\section*{Automate de la grammaire}

On a construit dans la section précédente un automate fini (non déterministe) reconnaissant les préfixes viables des proto-phrases de la grammaire (ce qui montre au passage que le language des préfixes viables est régulier). On va ici construire un automate à pile qui reconnaîtra exactement le langage de la grammaire.


\paragraph{Première étape} On commence par déterminiser l'automate précédent. On obtient ainsi $AFD_G = (\bar{Q}, V_N \cup V_T, \bar{\Delta}, q_0)$. On notera $q_0, ..., q_n$ les éléments de $\bar Q$.

\paragraph{Deuxième étape} On ajoute les opérations de pile $\Lambda$ suivantes:
\begin{itemize}
\item Pour toute transition $q_i \xrightarrow{a} q_j \in \bar \Delta$, $\quad (\gamma, q_i)  \xrightarrow{a}  (\gamma q_i, q_j) \in \Lambda$.

Ces transitions, dites de lecture, servent à garder la trace des lectures effectuées, de manière à pouvoir associer au mot de pile un mot de $(V_N \cup V_T)^*$.
\item Aux états contenant des items complets, on ajoute les transitions de pile suivantes :

Si $[A \rightarrow \alpha \sbullet] \in q_i$, alors il existe un préfixe viable $\gamma$ tel que $S \xRightarrow{*}_d \gamma A \T w \Rightarrow_d \gamma \alpha \T w$. Soit alors $q_j = \bar \Delta(\gamma A, q_0)$, on ajoute une série de transitions telles que$(\gamma \alpha, q_i) \xrightarrow{\epsilon}^* (\gamma, q_j)$ à $\Lambda$ (on ne peut pas le faire en une seule transition car un automate à pile ne peut dépiler qu'un symbole par transition).

Ces transitions, dites de réduction, correspondent à la reconnaissance de la phrase $\alpha$ comme étant la dérivation du symbole $A$.
\end{itemize}

Ainsi, $A_G$ va lire son mot d'entrée jusqu'à se trouver dans un état contenant un item complet, auquel cas il pourra réduire. Si $\mathcal{A}_G$ a reconnu $\T x \T y$, sa pile contient exactement $\T x \T y$; s'il se trouve dans un état contenant $[A \rightarrow \T y \sbullet]$, on pourra réduire $\T y$ en $A$, auquel cas la pile contiendra maintenant $\T x A$. On pourra alors continuer les lecture, ou réduire, jusqu'à épuiser l'entrée. 
Si alors le mot correspondant à l'état de la pile est exactement l'axiome, c'est à dire si l'on a réussi à réduire le mot d'entrée en l'axiome de la grammaire, alors il sera reconnu comme un élément de $L(G)$.\\



\begin{figure}
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
  thick,state/.style={rectangle,draw}]

	\node[state, initial, align=center] (0) {
  		\begin{tabular}{c|l}
  			\multirow{2}{*}{$0$} & $[S \rightarrow \sbullet SS+]$\\
  		  					 	 & $[S \rightarrow \sbullet c ]$
  		\end{tabular}
  		};
	\node[state, align=center] (1) [right=3cm of 0] {
  		\begin{tabular}{c|l}
  			\multirow{3}{*}{$1$} & $[S \rightarrow \sbullet SS+]$\\
  							 	 & $[S \rightarrow S \sbullet S+]$\\
  							 	 & $[S \rightarrow \sbullet c ]$
  		\end{tabular}
  };
	\node[state, align=center] (2) [below=1cm of 1] {
  		\begin{tabular}{c|l}
  		\multirow{4 }{*}{$2$} & 
  		$[S \rightarrow \sbullet SS+]$\\& $[S \rightarrow S \sbullet S+]$\\
  		& $[S \rightarrow SS \sbullet +]$\\& $[S \rightarrow \sbullet c ]$	
  		\end{tabular}	
  };
	\node[state] (3) [right=2cm of 2] {
  		\begin{tabular}{c|l}
	$3$ & $[S \rightarrow SS+ \sbullet]$
  		\end{tabular}
	};
	\node[state] (4) [below of=0] {
  		\begin{tabular}{c|l}
	$4$ & $[S \rightarrow c \sbullet ]$
  		\end{tabular}
	};

  \path[every node/.style={font=\sffamily\small}]
  	(0) edge node [above] {\textcolor{gray}{$(\gamma,$}$S$\textcolor{gray}{$)\rightarrow \gamma 1$}} (1)
  		edge node [right] {\textcolor{gray}{$(\gamma,$}$c$\textcolor{gray}{$)\rightarrow \gamma 4$}} (4) 
  	(1) edge node [right] {\textcolor{gray}{$(\gamma,$}$S$\textcolor{gray}{$)\rightarrow \gamma 2$}} (2)
  		edge node [above] {\textcolor{gray}{$(\gamma,$}$c$\textcolor{gray}{$)\rightarrow \gamma 4$}} (4)
  	(2) edge node [above] {\textcolor{gray}{$(\gamma,$}$+$\textcolor{gray}{$)\rightarrow \gamma 3$}} (3)
  		edge node [above] {\textcolor{gray}{$(\gamma,$}$c$\textcolor{gray}{$)\rightarrow \gamma 4$}} (4)
  		edge [loop below] node [below] {\textcolor{gray}{$(\gamma,$}$S$\textcolor{gray}{$)\rightarrow \gamma 2$}} (2)
  	;
  	\path[draw=red, every node/.style={font=\sffamily\small}, dashed]
  	(4) edge  [bend right =10] node [right] {\textcolor{red}{$(\gamma 04, \epsilon) \rightarrow^* \gamma 0 1$}} (1)
  	(3) edge node [right] {\textcolor{red}{$(\gamma 0123, \epsilon) \rightarrow^* \gamma 0 1$}} (1)
  	(4) edge  [bend right =10] node [below, align=center] {
  		\textcolor{red}{$(\gamma 14, \epsilon) \rightarrow^* \gamma 12$}\\
  		\textcolor{red}{$(\gamma 24, \epsilon) \rightarrow^* \gamma 22$}	} (2)
  	;
\end{tikzpicture}
\caption{Automate à pile $\mathcal{A}_{G_0}$ correspondant à la grammaire $G_0$}
\end{figure}

\begin{figure}
\centering
\begin{tabular}{r|l|l}
Mot d'entrée & arbre syntaxique & état de la pile \\
 & \multirow{6}{*}{ \begin{tikzpicture} [scale=.6, every child/.style={level distance = 0.8cm}]
 \node{S}child{child{child{child{node{S}child{node{c}}}}}}
  				child{child{node{S}child{node{c}}}}
  				child{node{+}};
 \end{tikzpicture}} & 01 \\
 & & 0123 \\
+ & & 012 \\
+ & & 014 \\
c+ & & 01\\
c+ & & 04\\
cc+ & & 0
\end{tabular}
\caption{Reconnaissance du mot $cc+$ par l'automate $\mathcal{A}_{G_0}$.}
\end{figure}


\paragraph{LR(0)}
Enfin, la grammaire $G$ sera dite LR(O) si l'automate à pile obtenu est déterministe, c'est à dire qu'il n'y aura aucun conflit entre deux transitions de l'automate.

Les conflits peuvent être de deux ordres :
\begin{itemize}
\item \textit{Lecture-réduction} Lorsque l'automate se trouve dans un état contenant un item complet $[A \rightarrow \alpha \sbullet]$ et une transition par lecture d'un terminal $[ B \rightarrow \beta \sbullet b \beta'] \xrightarrow{b} [ B \rightarrow \beta b \sbullet \beta']$, si le caractère suivant du mot d'entrée est un $b$, alors l'automate devra faire un choix non-déterministe.
\item \textit{Réduction-réduction} Lorsque l'automate se trouve dans un état contenant deux items complets, l'automate devra choisir de manière non déterministe entre les deux réductions.
\end{itemize}

Si aucun de ces cas ne se produit, ce qui peut se vérifier facilement, alors l'automate aura un fonctionnement déterministe. Dans ce cas, la construction de $\mathcal{A}_G$ nous donne une procédure effective pour savoir si $G$ est $LR(0)$, et, le cas échéant, nous permet de reconnaître les mots de $L(G)$ de manière efficace.

\section*{Références}
\begin{itemize}
\item J. E. Hopcroft, J. D. Ullman \textit{Introduction to automata theory, languages and computation}

Seule source (presque) sérieuse et (presque) claire trouvée pour traiter LR.

\item Willhelm, Maurer \textit{Compilers}

Très formel, manque d'explications; traite LR de manière tordue; preuve au gros coup de bluff.

\item \textit{Dragon}

Pas assez formel, mais fournit une partie de l'intuition.
\end{itemize}
\end{document}