diff options
| -rw-r--r-- | notes-inf105.tex | 22 |
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. + |