summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-16 15:58:37 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-16 15:58:37 (GMT)
commit2df4c8300a6c0923868288b3421641b43ceb1f43 (patch)
treecf201b776c00254f7140e12f2e4a190c12c4ccb1 /notes-inf105.tex
parentd3e561fe3210830f1bb640dede4fc3868b7d29dc (diff)
downloadinf105-2df4c8300a6c0923868288b3421641b43ceb1f43.zip
inf105-2df4c8300a6c0923868288b3421641b43ceb1f43.tar.gz
inf105-2df4c8300a6c0923868288b3421641b43ceb1f43.tar.bz2
Provide a short (and very hastily written) summary of the LL/LR approach.
Diffstat (limited to 'notes-inf105.tex')
-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.
+