Analyse Syntaxique ascendante

Définition d'analyse ascendante LR
Définition de poignée et préfixe viable
Structure d'un analyseur ascendant
Définition et construction des Items LR(k)
Définition et construction des tables LR(k)
Un exemple LR(0)
Un exemple LR(1)
Construction des tables SLR
Construction des tables LALR(1)

Analyse ascendante

Cette méthode cherche a construire une dérivation droite en la reconstituant à l'envers à partir de la chaîne de terminaux vers le symbole initial, ou de façon équivalente, cherche à construire un arbre de dérivation a partir des feuilles selon un parcours inverse d'un parcours en profondeur d'abord de gauche a droite.

Pour savoir simplement quand l'analyse s' arrête avec succès pour une grammaire G, on travaille toujours sur une grammaire dite augmentés G' qui est G avec un nouveau symbole S' comme symbole de départ, un nouveau symbole terminal $ et une transition supplémentaire

$\begin{displaymath}S'\quad\rightarrow\quad S\$ \end{displaymath}$

Terminologie

Notation 1.1 Dans ce qui suit, on utilisera les conventions suivantes:

des lettres majuscules $A,\ldots{} Z$: indiquent des symboles non-terminaux
des lettres grecques $\alpha,\beta,\gamma,\ldots{}$: indiquent des séquences de symboles terminaux ou non-terminaux
des lettres minuscules $a,b,c,\ldots{}$: indiquent des symboles terminaux
des lettres minuscules $\ldots{},u,v,x,y,w,z$: indiquent des séquences de symboles terminaux

Définition 1.2 Analyseurs LR Les analyseurs ascendants le plus connus sont dans la classe LR des analyseurs qui lisent le flot de tokens en entrée de gauche a droite (le L dans LR) pour reconstruire une dérivation droite (le R dans LR).

Définitions techniques

Définition 1.3 (Dérivation droite) Une dérivation droite est une dérivation qui remplace à chaque étape le symbole non terminal le plus à droite.
On notera $\ensuremath{\alpha\Rightarrow_{d}\beta}$ une étape de dérivation droite entre $\alpha$ et $\beta$ , et on notera $\ensuremath{\alpha\Rightarrow^{\ast}_{d}\beta}$ une série (même vide) d'étapes de dérivation droite entre $\alpha$ et $\beta$ .

Définition 1.4 (Protophrase d'une grammaire tex2html_wrap_inline$G$) Une protophrase est une séquence de symboles terminaux et non terminaux qui peut apparaître en cours d'une dérivation du symbole initial S d'une grammaire G.
On parle de protophrase droite (resp. gauche) lorsque cette séquence peut apparaître dans une dérivation droite (resp. gauche) de G.

Définitions techniques, suite

Définition 1.5 (Poignée (handle)) Dans une protophrase $\phi$ , la séquence $\gamma$ est une poignée á la position n pour la grammaire G si ell'est la partie gauche d'une production
$X\rightarrow \gamma$ , et que cette production doit être appliquée à $\phi$ en position n pour construire la protophrase précédente dans une dérivation droite á partir de S vers $\phi$ avec la grammaire G.

Définition 1.6 (Préfixe viable) Une séquence $\gamma$ est un préfixe viable pour une grammaire G si $\gamma$ est un préfixe de
$\alpha\beta$ , où
$\phi=\alpha\beta w$ est une protophrase droite de G est $\beta$ est une poignée dans cette protophrase.
Autrement dit, un préfixe viable est un préfixe $\gamma$ d'une protophrase $\phi$ , mais qui ne s' étend pas plus à droite d'une poignée $\beta$ de $\phi$ .

Un exemple

Sur la grammaire augmentée

$\begin{displaymath}\begin{array}{c@{\qquad\rightarrow\qquad}l} S & E\; \$ \\ E & E + T\; \vert\; T \\ T & id \\ \end{array}\end{displaymath}$

l'unique dérivation droite pour $id+id+id\;\$$ est la suivante:

$\begin{displaymath}\begin{array}{l}\overline{S} \\ \overline{E}\;\$\\ {E + \... ...} + id + id\; \$\\ \underline{id}+ id + id\; \$\\ \end{array}\end{displaymath}$

Chaque ligne est une protophrase droite, en surligné les symboles produits, et en souligne les poignées.
Les préfixes viables sont les préfixes qui ne s'étendent pas plus loin qu'une poignée. Par exemple, sur la protophrase ${E} + \underline{id} + id\;\$$ ce sont $\epsilon,E,E+,E+id$ .

Définitions techniques, fin

Définition 1.7 (tex2html_wrap_inline$FIRST_k()$) Étant donnée une grammaire G, l'ensemble
$FIRST_k(\gamma)$ contient les préfixes de longueur k des séquences de non terminaux de longueur au moins kdérivables à partir de $\gamma$ dans G, et les séquences de non terminaux de longueur inférieur à k dérivables depuis $\gamma$ .

Définition 1.8 (tex2html_wrap_inline$EFF_k()$ (tex2html_wrap_inline$-free FIRST_k$)) Étant donnée une grammaire G, EFF_k est le sousensemble de FIRST_kobtenu en considérant seulement les dérivations qui ne réduisent pas sur $\epsilon$ un non terminal en tête de chaîne.

Exemples

Pour la grammaire:

$\begin{displaymath}\begin{array}{c@{\qquad\rightarrow\qquad}l} S & A\;B \\ A ... ...B & C\;b\;\vert\;C \\ C & c\;\vert\;\epsilon \\ \end{array}\end{displaymath}$

on a:

FIRST₂(S): = $\{\epsilon,a,b,c,ab,ac,ba,ca,cb\}$
EFF₂(S): = $\{ca,cb\}$

Grammaires LR(k)

On peut maintenant donner la définition formelle de la classe des grammaires LR(k).

Définition 1.9 (Grammaire LR(k)) Une grammaire G est dans LR(k) ( $k\geq 0$ ) si les trois conditions suivantes:

$S\ensuremath{\Rightarrow^{\ast}_{d}}\alpha Aw \ensuremath{\Rightarrow_{d}}\alpha\beta w$
$S\ensuremath{\Rightarrow^{\ast}_{d}}\gamma Bx \ensuremath{\Rightarrow_{d}}\alpha\beta y$
FIRST_k(w) = FIRST_k(y)

impliquent $\alpha=\gamma, A=B, x=y$

Autrement dit, il suffit de regarder les premiers k symboles en entrée au moment ou il faut choisir une production pour la réduction dans la dérivation droite.

Structure de l'analyseur

Les grammaires LR(k) sont celles dont le langage est reconnu par un analyseur déterministe LR(k). Cet analyseur utilise une pile et le flot d'entrée, qui décrivent une configuration de l'analyseur, notée

$\begin{displaymath}\begin{array}{@{(}l@{\qquad,\qquad}r@{)}}X_1\ldots{}X_j & a_i\ldots{}a_{n}\end{array}\end{displaymath}$

où les X sont de symboles, terminaux ou non terminaux, stoqués sur la pile, alors que les a sont seulement des symboles terminaux, et correspondent aux terminaux non encore lus sur le flot d'entrée.

L'analyseur travaille en effectuant quatre actions possibles:

shift (décalage): on transfert le terminal a_i du flot d'entrée vers la pile
reduce (réduction): on reconnaît sur le sommet de la pile une partie droite d'une production $Y\rightarrow X_{j-k}\ldots{}X_{j}$ , on l'enlève et on la remplace par sa partie gauche Y
erreur: l'analyseur s'arrête et signale un erreur
accept: l'analyseur s'arrête et signale que la phrase a été reconnue

Pour choisir les actions, on utilise une table d'analyse que l'on verra plus avant.

Un exemple

Sur la grammaire augmentée

$\begin{displaymath}\begin{array}{c@{\qquad\rightarrow\qquad}l} S & E\; \$ \\ E & E + T\; \vert\; T \\ T & id \\ \end{array}\end{displaymath}$

Une possible séquence de reconnaissance pour $id+id+id\;\$$ pour un analyseur ascendant serait:

$\begin{displaymath}\begin{array}{@{(}l@{\qquad,\qquad}r@{)\qquad}l}\obeyspaces ... ...nderline{E + T} & \$ & reduce\\ E & \$ & accept\\ \end{array}\end{displaymath}$

Remarques Importantes

Configurations et protophrases:

la concatenation de la partie gauche et droite d'une configuration d'un analyseur ascendant pour une grammaire Gest toujours une protophrase droite de G (si l'analyse se termine avec succès).

Préfixes viables:

un préfixe viable peut toujours se compléter en une protophrase droite. En d'autre termes, il n'y a pas d'erreur au cours de l'analyse tant que l'on a sur la pile un préfixe viable.

Un autre exemple, avec look-ahead

Sur la grammaire augmentée

$\begin{displaymath}\begin{array}{ccc} S & \rightarrow & E\; \$ \\ E & \rightarrow & T + E \;\vert\; T \\ T & id \\ \end{array}\end{displaymath}$

Une possible séquence de reconnaissance pour $id+id+id\;\$$ pour un analyseur ascendant serait:

$\begin{displaymath}\begin{array}{@{(}l@{\qquad,\qquad}r@{)\qquad}l}& id + id + i... ...ne{T + E} & \; \$ & reduce\\ E & \; \$ & accept\\ \end{array}\end{displaymath}$

Analyseurs LR

Un analyseur LR est composé de

une pile et un flot d'entrée: comme vu dans les exemples
une table d'analyse: qui décrit un automate à états finis augmenté avec des actions á effectuer éventuellement sur la pile (shift, reduce, accept, error)

L'exécution de l'automate est censée décaler sur la pile des symboles jusqu'à atteindre une préfixe viable maximale (i.e. pas extensible à droite, i.e. contenant une poignée $\gamma$ en fond à droite, i.e. en sommet de pile), puis réduire la poignée en la remplaçant avec la partie droite Xde la production $X\quad\rightarrow\quad\gamma$ concernée.

Fonctionnement d'un analyseur LR

Sur un état d'analyseur $(\alpha\quad,\quad xw)$ le fonctionnement de l'analyseur LR est le suivant:

exécuter l'automate à partir de l'état initial s₁ sur la pile $\alpha$ , ce qui nous laisse sur un état s_k
exécuter l'action décrite dans la table d'analyse associée au symbole terminal x en entrée pour l'état s_k

shift
(noté s) déplacer le symbole d'entrée x sur la pile,
reduce n
(noté rn) sur le sommet de la pile il y a la partie gauche de la règle numéro n, disons $X\rightarrow \gamma$ ; dépiler $\gamma$ et empiler X
accept
(noté a) arrêter avec succès
error
(noté par une case vide) arrêter sur erreur
recommencer avec le nouvel état d'analyseur

Exemple d'exécution avec une table d'analyse LALR(1)

<!-- MATH: \begin{displaymath} \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c@{\quad}c@{\qquad\rightarrow\qquad}l} 0 & S & E\; \$ & 2 & E & T \ 1 & E & T + E & 3 & T & id \end{array}

\end{displaymath} -->

$\begin{displaymath}\begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c... ...\; \$ & 2 & E & T \\ 1 & E & T + E & 3 & T & id \end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{c\vert ccc\vert ccccc\vert} & \multicolumn{3}{... ...} & \; \$ & reduce\\ {}_1E{}_2 & \; \$ & accept\\ \end{array}\end{displaymath}$

Ici on a marqué en bas les états de l'automate après lecture de chaque symbole sur la pile.

Analyseur avec états sur la pile

Si on garde les états sur la pile, en modifiant la notion de configuration pour que chaque symbole soit suivi par un état, on peut éviter de relire toute la pile à chaque fois: sur une configuration d'analyseur $(s_1X_1\ldots{}s_{k-1}X_{k-1} s_k\quad,\quad xw)$ le fonctionnement de l'analyseur LR est le suivant:

exécuter l'action décrite dans la table d'analyse associée au symbole terminal x en entrée pour l'état s_k

shift k
déplacer le symbole d'entrée x sur la pile, et empiler l'état numéro k
reduce n
sur le sommet de la pile il y a la partie gauche de la règle numéro n, disons $X\rightarrow \gamma$ ; dépiler $\gamma$ et tous les états associés, en découvrant l'état s'; empiler X et l'état s'' contenu dans la table á la ligne s', colonne X
accept
arrêter avec succès
error
arrêter sur erreur
recommencer avec le nouvel état d'analyseur

Comment produire une table d'analyse?

Il faut savoir reconnaître les préfixes viables, et savoir déterminer quelles productions utiliser pour les réductions, éventuellement en utilisant k tokens en entrée pour aider dans la décision.

Pour reconnaître les préfixes viables, on définit d'abord

Définition 1.10 (ITEM LR(k)) Un ITEM LR(k) pour une grammaire G est une production

$X\quad\rightarrow\quad\gamma$ de G plus une position j dans $\gamma$ et une séquence w de longueur $\leq k$ . Cela est noté, si $\gamma=\alpha\beta$ avec jla longueur de $\alpha$

$\begin{displaymath}X\quad\rightarrow\quad\alpha\cdot\beta, w\end{displaymath}$

sauf dans le cas LR(0) pour lequel on écrit simplement

$X\quad\rightarrow\quad\alpha\cdot\beta$

L'intuition de $(A\;\rightarrow\;\alpha\cdot\beta,w)$ est que l'on a déjà vu en entrée le préfixe $\alpha$ d'une protophrase et que l'on attende sur l'entrée une séquence dérivable à partir de $\beta w$ .

Reconnaître les préfixes viables: la fermeture

Si on a $(A\quad\rightarrow\quad\alpha\cdot X\beta,z)$ , i.e. on a a déjà vu en entrée le préfixe $\alpha$ et on attende une séquence dérivable à partir de $X\beta z$ , on est aussi en condition d'attendre une séquence dérivable depuis X, suivie d'une séquence dérivable depuis $\beta z$ . C'est cela que capture la notion suivante de fermeture

Définition 1.11 (Fermeture (Closure) LR(k))

Fermeture(I) = répéter tant queIgrandit pour tout item $(A\quad\rightarrow\quad\alpha\cdot X\beta,z)$ dans I pour toute production $X\quad\rightarrow\quad\gamma$ pour tout $w\in FIRST_{k}(\beta z)$ $I \leftarrow I \cup \{(X\quad\rightarrow\quad\cdot\gamma,w)\}$ retourner I

Reconnaître les préfixes viables: GOTO

Définition 1.12 (GOTO)

Supposons d'avoir $(A\quad\rightarrow\quad\alpha\cdot X\beta,z)$ , pour un symbole terminal ou non terminal X: on a donc déjà vu en entrée le préfixe $\alpha$ et on attende une séquence dérivable à partir de $X\beta z$ . Si maintenant l'on reconnaît X, alors on a vu $\alpha X$ et on attende une séquence dérivable à partir de $\beta z$ .
C'est cela que capture la notion suivante de GOTO

Goto(I,X) = $J\leftarrow \emptyset$ pour tout item $(A\quad\rightarrow\quad\alpha\cdot X\beta,z)$ dans I $J \leftarrow J \cup \{(X\quad\rightarrow\alpha X\cdot\beta,z)\}$ retourner Fermeture(J)

L'automate qui reconnaît les préfixes viables

Soit G un grammaire augmentée, et soit ${\cal I}$ la collection $\{s_0;s_1;\ldots{};s_k\}$ d'ensembles d'ITEMS LR(k) attaignables depuis la fermeture de l'item $s_0=(S'\;\rightarrow\;\cdot S\$,\epsilon)$ par la fonction GOTO.
On peut alors construire l'automate à état fini suivant:

états: $\{s_0;s_1;\ldots{};s_k\}$ avec s₀ état initial et comme états finaux ceux qui contiennent au moins un ITEM LR(k) avec le point au fond à droite (i.e. de la forme $(X\rightarrow\gamma\cdot,w)$ )
transitions: on a une transition de l'état s_i vers l'état s_j sur le symbole X si GOTO(s_i,X)=s_j

La construction de la table LR(k)

Soit G un grammaire augmentée, pour laquelle on a construit l'automate.
La table d'analyse a une ligne par état et un colonne par séquence de symboles terminaux de longueur $\leq k$ (le look-ahead) et une colonne par symbole terminal et non-terminal, que l'on remplit de la façon suivante:
Pour tout état $s_i\in {\cal I}$ ,

on met $reduce\;n$ dans la case s_i, u si $(A\rightarrow\beta\cdot,u)\in s_i$ et $A\rightarrow\beta$ est la production numéro $n\geq 1$
on met accept dans la case $s_i, \$$ si $(S'\rightarrow\beta\cdot,\$)\in s_i$
on met shift dans la case s_i, u si $(A\rightarrow\beta_1\cdot\beta_2,v)\in s_i$ et $u\in EFF_k(\beta_2 v)$
on laisse vide (i.e. on signale erreur) autrement

Theorem 1.13 (fondamental de l'analyse ascendante) Si une grammaire G est LR(k), alors l'automate construit reconnaît les préfixes viables de G et tout état contenant un ITEM LR(k) de la forme $(X\rightarrow\gamma\cdot,w)$ ne contient pas un ITEM $(X'\rightarrow\gamma_1\cdot\gamma_2,u)$ avec $w\in EFF_k(\beta_2 v)$ . (en d'autre terme, on n'aura pas dans la table des entrées multiples décaler et réduire ou entre deux réductions).

Comment l'analyseur peut-il choisir l'action à effectuer?

Un analyseur LR dispose de plus d'information qu'un analyseur LL pour déterminer la prochaine action.

Imaginons d'avoir en entrée une chaîne uvw, et d'avoir déjà lu u. Pour déterminer la production à appliquer

un analyseur LL(k) connaît u et FIRST_k(vw)
un analyseur LR(k) connaît uv (en effet, il connaît un préfixe viable $\gamma$ obtenu à partir de uv) et FIRST_k(w)

Un exemple LR(0)

La grammaire $% latex2html id marker 1326 $G~\ref{g:seq}$$ suivante est LR(0)

$\begin{displaymath} \begin{array}{crl@{\qquad}cr@{\quad\rightarrow\quad}l@{\qqua... ... ) & 3 & L & S\\ & & & 2 & S & x & 4 & L & L,S\\ \end{array}\end{displaymath}$

(1)

Voici la construction complète de la table LR(0) de $% latex2html id marker 1330 $G~\ref{g:seq}$$
États et transitions (2,4,6,7,9 sont terminaux)

1.

$\{ (\ensuremath{S'\rightarrow \cdot S\$} ), (\ensuremath{S\rightarrow \cdot (L)} ), (\ensuremath{S\rightarrow \cdot x} ) \}$

${}\qquad\ensuremath{\mbox{\bf goto}(1,S)=4}\quad \ensuremath{\mbox{\bf goto}(1,()=3}\quad, \ensuremath{\mbox{\bf goto}(1,x)=2}\quad$

2.

$\{ (\ensuremath{S\rightarrow x\cdot} ) \}$

3.

$\{ (\ensuremath{S\rightarrow (\cdot L)} ), (\ensuremath{L\rightarrow \cdot S}... ...ensuremath{S\rightarrow \cdot (L)} ), (\ensuremath{S\rightarrow \cdot x} ) \}$

${}\qquad \ensuremath{\mbox{\bf goto}(3,()=3}\quad \ensuremath{\mbox{\bf goto}(... ...suremath{\mbox{\bf goto}(3,S)=7}\quad \ensuremath{\mbox{\bf goto}(3,L)=5}\quad$

4.

$\{ (\ensuremath{S'\rightarrow S\cdot\$} ) \}$

5.

$\{ (\ensuremath{S\rightarrow (L\cdot)} ), (\ensuremath{L\rightarrow L\cdot ,S} ) \}$

${}\qquad\ensuremath{\mbox{\bf goto}(5,))=6}\quad \ensuremath{\mbox{\bf goto}(5,,)=8}\quad$

6.

$\{ (\ensuremath{S\rightarrow (L)\cdot} ) \}$

7.

$\{ (\ensuremath{L\rightarrow S\cdot} ) \}$

8.

$\{ (\ensuremath{L\rightarrow L,\cdot S} ), (\ensuremath{S\rightarrow \cdot(L)} ), (\ensuremath{S\rightarrow \cdot x} ) \}$

${}\qquad\ensuremath{\mbox{\bf goto}(8,x)=2}\quad \ensuremath{\mbox{\bf goto}(8,()=3}\quad \ensuremath{\mbox{\bf goto}(8,S)=9}\quad$

9.

$\{ (\ensuremath{L\rightarrow L,S\cdot} ) \}$

La table d'analyse LR(0)

Pour remplir la table LR(0), on écrit la table de transition de l'automate et on introduit les actions de décalage (s pour shift) comme décrit plus en haut.
Pour les réductions (rk pour reduce avec la production k), n'ayant pas de look-ahead dans les états, on met rk dans toute la ligne action de l'état j si l'état j contient un ITEM LR(0) $X\rightarrow\gamma\cdot$ , et que $X\rightarrow \gamma$ est la production numéro j.

$\begin{displaymath}\begin{array}{c\vert c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\... ...\ 9 & r4 & r4& r4 & r4 &r4 & & & & & & & \\ \hline \end{array}\end{displaymath}$

La table d'analyse LR(0), versions compacte

Remarque

Les générateurs d'analyseurs, comme Yacc, fusionnent les colonnes des actions et des transitions pour les terminaux: plutôt que d'avoir une case case (1,x) qui contient s(hift) pour les actions, et une case (1,x) qui contient 2pour les transitions, on préfère avoir une seule case (1,x) qui contient s2, pour

l'action est un shift et la transition est vers l'&#233;tat </FONT></FONT></FONT>2<FONT SIZE="+2"><FONT SIZE="+2"><FONT SIZE="+1">''.
<BR>
Dans ce cas, on &#233;crit souvent </FONT></FONT></FONT><I>gk</I><FONT SIZE="+2"><FONT SIZE="+2"><FONT SIZE="+1"> dans les colonnes transitions restantes
(celles des non-terminaux). C'est une abr&#233;viation pour

goto k'', plus lisible que juste k.

$\begin{displaymath}\begin{array}{c\vert c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\... ...& & g9 & \\ 9 & r4 & r4& r4 & r4 &r4 & & \\ \hline \end{array}\end{displaymath}$

Un exemple LR(1) non LR(0)

La grammaire $% latex2html id marker 1374 $G~\ref{g:sommes}$$

$\begin{displaymath}\begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c... ...\; \$ & 2 & E & T \\ 1 & E & T + E & 3 & T & id \end{array}\end{displaymath}$

(2)

est une grammaire LR(1) mais pas LR(0).
En effet, dans l'automate on a un problème pour l'état $\{(\ensuremath{E\rightarrow T\cdot+E} ),(\ensuremath{E\rightarrow T\cdot} ) \}$ .

$\begin{displaymath}\diagram \framed<5pt>{(1)\begin{array}{l} \ensuremath{S\righ... ...\ensuremath{E\rightarrow T+E\cdot}\end{array}} \ \enddiagram \end{displaymath}$

Un exemple LR(1) non LR(0) (suite)

Donc dans la table d'analyse LR(0) on trouve un conflit shift/reduce dans la case 3,+

$\begin{displaymath}\begin{array}{c\vert c@{\quad}c@{\quad}c@{\quad}\vert c@{\qua... ...5 & r3& r3& r3 & & \\ 6 & r1& r1& r1 & & \\ \hline \end{array}\end{displaymath}$

Les états LR(1) de $% latex2html id marker 1866 $G~\ref{g:sommes}$$

Regardons alors la construction LR(1), qui garde trace des look-aheads dans les états...

États et transitions (2, 5 et 6 sont terminaux)

$\begin{displaymath}\diagram \framed<5pt>{(1)\begin{array}{l} (\ensuremath{S\rig... ...ath{E\rightarrow T+E\cdot} ,\;\$) \end{array}} \ \enddiagram \end{displaymath}$

Comparons les automates LR(0) et LR(1) pour $% latex2html id marker 2068 $G~\ref{g:sommes}$$

$\begin{displaymath}LR(0)\qquad % \diagram \framed<5pt>{(1)\begin{array}{l} \ens... ...\ensuremath{E\rightarrow T+E\cdot}\end{array}} \ \enddiagram \end{displaymath}$

$\begin{displaymath}LR(1)\qquad % \diagram \framed<5pt>{(1)\begin{array}{l} (\en... ...ath{E\rightarrow T+E\cdot} ,\;\$) \end{array}} \ \enddiagram \end{displaymath}$

La table d'analyse LR(1) de $% latex2html id marker 2437 $G~\ref{g:sommes}$$

On garde trace des look-ahead pour introduire dans la table les actions reduce, donc il y en a moins et le conflit disparaît!

$\begin{displaymath}\begin{array}{c\vert ccc\vert cccccc\vert} & \multicolumn{3}... ...r3 & & & & & & \\ 6 & & & r1 & & & & & & \\ \hline \end{array}\end{displaymath}$

La table d'analyse LR(1) de $% latex2html id marker 2439 $G~\ref{g:sommes}$$ , version compacte

$\begin{displaymath}\begin{array}{c\vert c@{\quad}c@{\quad}c\vert c@{\quad}c@{\qu... ...g3\\ 5 & r3& & r3 & & \\ 6 & & & r1 & & \\ \hline \end{array}\end{displaymath}$

Comparons les tables LR(0) et LR(1) pour $% latex2html id marker 2479 $G~\ref{g:sommes}$$

$\begin{displaymath}\begin{array}{c@{\qquad}c} LR(0) & LR(1) \\ \begin{array}{c\... ...& r1 & & \\ \hline \end{array}& \input{tableslr}\\ \end{array}\end{displaymath}$

Trouver sa place parmi les LR(k)

Comme nous venons de voir, la classe d'analyseurs LR(0) est trop faible pour traiter les langages de programmations: même le simple langage des expressions pose problème.

Les classes LR(2), LR(3), ... ont par contre une table d'analyse trop grosse en pratique en raison du nombre de colonnes pour le ``look-ahead'': un analyseur moderne utilise plusieurs dizaines de tokens, et une colonne pour chaque séquence de token de longueur inférieur ou égale à k, pour $k\geq 2$ est déraisonnable.

Exercice: combien de séquences de longueur inférieure ou égale à ky-at-il si on se donne n tokens différents?

Trouver sa place entre LR(0) et LR(1)

Heureusement, la classe LR(1) est largement suffisante pour les langages modernes, et la table n'a qu'une colonne par token.
Mais là, c'est le nombre d'états qui grandit trop, en raisons de la présence de look-ahead dans les états qui départage des états qui sont très peu différents.

C'est pour cela que dans la pratique on utilise deux types d'analyseurs dont la puissance est comprise entre celle de LR(0) et celle de LR(1): SLR et LALR(1)

Analyseurs SLR

SLR: (Simple LR) est un analyseur dont l'automate est celui de LR(0), donc la partie transition est la même que LR(0), et les actions de décalage aussi, mais la table d'analyse est construite de une façon plus fine: on pallie à l'absence de look-ahead dans les état avec l'information contenue dans les ensembles FOLLOW construits à partir de la grammaire.
La règle de placement des réductions devient alors:

si l'état j contient un ITEM LR(0) $X\rightarrow\gamma\cdot$ , et que $X\rightarrow \gamma$ est la production numéro $j\geq 1$ , on met rk dans toutes les cases (j,t) telles que $t\in FOLLOW(X)$ .

SLR pour la grammaire G 2

L'automate SLR étant le même que celui LR(0), on ne le montrera pas à nouveau, mais maintenant la table SLR contiendra des entrées reduce seulement sur certains nonterminaux, pas tous! En particulier, on pourra éviter le conflit shift/reduce dans l'état $\{(\ensuremath{E\rightarrow T\cdot+E} ),(\ensuremath{E\rightarrow T\cdot} ) \}$ .

$\begin{displaymath}\begin{array}{c\vert c@{\quad}c@{\quad}c@{\quad}\vert c@{\qua... ...3 \\ 5 & r3& & r3 & & \\ 6 & & & r1 & & \\ \hline \end{array}\end{displaymath}$

Dans ce cas précis, SLR fait aussi bien que LR(1), avec bien moins d'effort.

Analyseurs LALR(1)

LALR(1): (Look-Ahead LR(1)) est une classe d'analyseurs dont l'automate est obtenu de l'automate LR(1) en fusionnant les états qui diffèrent seulement par leur look-ahead.

On dit aussi que l'on fusionne les états ayant le même coeur, le coeur d'un état étant l'ensemble des parties gauches des ITEMS LR(1) qu'il contient, i.e. sans le look-ahead, i.e. des ITEMS LR(0).
Donc un analyseur LALR(1) a autant d'états qu'un LR(0) ou SLR.

Les analyseurs LALR(1) sont les plus utilisés parce que, même s'ils ont moins d'états qu'un analyseur LR(1), il est très rare qu'on retrouve un conflit dans la table LALR(1) quand il n'y en a pas dans la table LR(1).
En particulier, on peut prouver que si un analyseur LR(1) n'a pas de conflits shift/reduce, l'analyseur LALR(1) n'en a pas non plus.
Par contre, on peut introduire des conflits reduce/reduce.

LALR(1) pour $% latex2html id marker 2728 $G~\ref{g:sommes}$$

Dans le cas précis de cette grammaire, l'automate LR(1) pour $% latex2html id marker 2730 $G~\ref{g:sommes}$$ n'ayant pas d'états différents avec le même coeur, la table d'analyse LALR(1) de $% latex2html id marker 2732 $G~\ref{g:sommes}$$ est la même que celle LR(1).

Mais la grammaire suivante, qui capture un sous-ensemble des expressions du langage C, est un exemple de grammaire LALR(1) qui n'est pas SLR et pour laquelle l'automate LALR(1) est plus petit que l'automate LR(1).

$\begin{displaymath} \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad... ...= E & 4 & V & id \\ 2 & S & E & 5 & V & * E \\ \end{array} \end{displaymath}$

(3)

LR préfère l'associativité à gauche

Contrairement à ce qui se passe dans le cas des analyseurs LL, dans l'analyse ascendante on a plutôt intérêt à utiliser des grammaires récursives à gauche.

Considérons les analyseurs LR pour la grammaire récursive à droite

$\begin{displaymath}\begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c... ...& E\; \$ & & E & T \\ & E & T + E & & T & id \\ \end{array}\end{displaymath}$

vus en cours: pour reconnaître $id+id+\ldots{}+id\$$ , ils empilent toute la suite de symboles (en réduisant id sur T à chaque coup) avant de faire la prémière reduction non triviale.
Par contre, la grammaire recursive à gauche

$\begin{displaymath}\begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c... ...& E\; \$ & & E & T \\ & E & E + T & & T & id \\ \end{array}\end{displaymath}$

mantiendra la dimension de la pile à un minimum.

Utilisation de grammaires ambiguës

Une grammaire ambiguë n'est jamais LR(k), quelque soit k.
Pourtant, on a intérêt à essayer d'utiliser une grammaire ambiguë, quitte à trafiquer l'automate LR(k), si on peut.

efficacité: dans une grammaire obténue par désambiguation, l'analyseur passe beaucoup de temps à reduire des productions triviales (comme $E\rightarrow T$ dans l'exemple précédent), dont le seul but était d'expliciter dans la grammaire les priorités entre opérateurs et leur associativité droite ou gauche.
praticité: si on peut décrire de façon concise ces priorités entre opérateurs et leur associativité droite ou gauche, sans toucher à la grammaire, on obtient une description plus modulaire du langage qui nous intéresse.

Exemple

Considérons la grammaire (ambiguë) suivante:

<!-- MATH: \begin{displaymath} \begin{array}{c@{\qquad\rightarrow\qquad}l} S & E\; \$ \ E & E * E \ E & E + E \ E & id \end{array}

\end{displaymath} -->

$\begin{displaymath}\begin{array}{c@{\qquad\rightarrow\qquad}l} S & E\; \$ \\ E & E * E \\ E & E + E \\ E & id \end{array}\end{displaymath}$

et sa table d'analyse SLR.

Voyons comment les nombreux conflits apparents peuvent s'expliquer en terme d'associativité et précedence d'opérateurs, que l'on peut résoudre en travaillant directement sur les entrées de la table...

(fait au tableau, pas dans les notes... si un ame gentille veut tout taper...)

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

The command line arguments were:
latex2html -split 0 Slides01.

The translation was initiated by Roberto Di Cosmo on 1999-11-24

Roberto Di Cosmo
1999-11-24