From 2df4c8300a6c0923868288b3421641b43ceb1f43 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 16 Jan 2017 16:58:37 +0100
Subject: Provide a short (and very hastily written) summary of the LL/LR
 approach.

---
 notes-inf105.tex | 22 ++++++++++++++++++++--
 1 file changed, 20 insertions(+), 2 deletions(-)

(limited to 'notes-inf105.tex')

diff --git a/notes-inf105.tex b/notes-inf105.tex
index a3e7fe5..67cb074 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3222,8 +3222,8 @@ L'intersection d'un langage \emph{algébrique} et d'un langage
 
 \subsection{Autres exemples de grammaires hors contexte}
 
-\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire
-(d'axiome $S$)
+\thingy\label{example-lr-non-ll-grammar} Sur l'alphabet $\Sigma =
+\{a,b\}$, considérons la grammaire (d'axiome $S$)
 \[
 \begin{aligned}
 S &\rightarrow AT\\
@@ -3872,6 +3872,24 @@ aSbS \,|\, \varepsilon$, on peut écarter la règle $S \rightarrow
 \varepsilon$ quitte à ajouter des règles $S \rightarrow aSb$ et $S
 \rightarrow abS$ et $S \rightarrow ab$.
 
+\thingy Du point de vue pratique, il existe deux approches principales
+pour analyser les langages définis par des grammaires hors contexte
+(supposées \emph{au minimum} inambiguës) :
+\begin{itemize}
+\item les analyseurs LL qui procèdent de façon \emph{descendante},
+  parcourent le mot depuis la gauche (« L ») et génèrent la dérivation
+  gauche (« L ») de l'arbre d'analyse fabriqué,
+\item et les analyseurs LR qui procèdent de façon \emph{ascendante},
+  parcourent le mot depuis la gauche (« L ») et génèrent la dérivation
+  droite (« R ») de l'arbre d'analyse fabriqué.
+\end{itemize}
+
+L'idée générale à retenir est que les analyseurs LR sont strictement
+plus puissants que les analyseurs LL (ils sont capables d'analyser
+strictement plus de grammaires, cf. \ref{example-lr-non-ll-grammar}),
+mais leur écriture est plus difficile et les messages d'erreur qu'ils
+retournent sont plus difficiles à comprendre.
+
 
 
 
-- 
cgit v1.2.3

