summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex22
1 files changed, 20 insertions, 2 deletions
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.
+