From 2df4c8300a6c0923868288b3421641b43ceb1f43 Mon Sep 17 00:00:00 2001 From: "David A. Madore" 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(-) 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