SLR
But: d’optimiser l’implémentation de la table d’analyse construite à partir des items LR(0).
G est SLR G est LR(k)
La table d’analyse :
SLR(1) = LR(0)
Si [A→α·] La réduction R,k : A→α est ajoutée pour tous les suivants(A)
note: Pour qu’une grammaire G soit SLR, il faut que la table d’analyse soit mono-définie.
Exemple:
S→ aSb/Ac
A→ aAb/ε
Calculer l’ensemble des items LR(0) de la grammaire
Soit l’ensemble des items LR(0) suivant :
I0= {[Z→·S], [S→·aSb], [S→·Ac], [A→·aAb], [A→·]}//R4, tous les suivants de A : b et c
I1= GOTO (I0, S) = {[Z→S·]} //CA
I2=GOTO (I0, A) = {[S→A·c]}
I3=GOTO (I0, a) = {[S→a·Sb], [A→a·Ab], [S→·aSb], [S→·Ac], [A→·aAb], [A→·]} //R4, tous les
suivants de A : b et c
I4=GOTO (I2, c) = {[S→Ac·]}//R2, tous les suivants de S : b et #
I5=GOTO (I3, S) = [S→aS·b]
I6=GOTO (I3, A) = {[A→aA·b], [S→A·c]}
I3=GOTO (I3, a)
I7=GOTO (I5, b) = {[S→aSb·]} //R1, tous les suivants de S : b et #
I8=GOTO (I6, b) = {[A→aAb·]} //R3, tous les suivants de A : b et c
I4=GOTO (I6, c) = {[S→Ac·]} // R2, tous les suivants de S : b et #
La table d’analyse :
a b c # S A
0 D, 3 R, 4 R, 4 1 2
1 CA
2 D, 4
3 D, 3 R, 4 R, 4 5 6
4 R, 2 R, 2
5 D, 7
6 D, 8 D, 4
7 R, 1 R, 1
8 R, 3 R, 3
Note : La table d’analyse est mono-définie, donc on peut faire de l’analyse syntaxique
SLR(1). L’analyse syntaxique SLR est identique à l’analyse LR.
On construit un automate d’états finis correspondant à l’analyse SLR et on vérifie les cas de
multidéfinition.
LALR
Note : Si une grammaire G est non SLR Alors elle peut être LALR.
Deux cas de multi-définition peuvent exister :
– Décalage/Réduction.
– Réduction/Réduction.
Si la multi-definition est de type Réduction/Réduction Alors G n’est pas LALR.
LALR a deux méthodes aussi :
1. Méthode base sur SLR. (items LR(0))
2. Méthode base sur le calcul des noyaux (cœurs). (items LR(1))
Exemple: exo 4 de TD
S→ CC
C→ cC/d
1. Méthode base sur SLR. (items LR(0)) :
Réduction : ex : I1 = Ab. //R2 : f la ligne I1 avec colonne ta3 suiv de A nktbo R2.
Calculer l’ensemble des items LR(0) de la grammaire :
I0= {[Z→·S], [S→·CC], [C→·cC], [C→·d]}
I1 = GOTO (I0, S) = {[Z→S.]} //CA
I2 = GOTO (I0, C) = {[S→C.C], [C→·cC], [C→·d]}
I3 = GOTO (I0, c) = {[C→c.C], [C→·cC], [C→·d]}
I4 = GOTO (I0, d) = {[C→d.]} //R3, tous les suivants de C : c et d
I5 = GOTO (I2, C) = {[S→CC.]} //R1, tous les suivants de S : #
I3 = GOTO (I2, c) = {[C→c.C], [C→·cC], [C→·d]}
I4 = GOTO (I2, d) = {[C→d.]} //R3, tous les suivants de C : c et d
I6 = GOTO (I3, C) = {[C→cC.]} //R2, tous les suivants de C : c et d
I3 = GOTO (I3, c) = {[C→c.C], [C→·cC], [C→·d]}
I4 = GOTO (I3, d) = {[C→d.]} //R3, tous les suivants de C : c et d
La table d’analyse :
c d # S C
0 D, 3 D, 4 1 2
1 CA
2 D, 3 D, 4 5
3 D, 3 R, 4 D, 4 R, 4 6
4 R, 3 R, 3
5 R, 1
6 R, 2 R, 2
2. Méthode base sur le calcul des noyaux (cœurs). (items LR(1)) :
S→ CC
C→ cC/d
Calculer l’ensemble des items LR(1) de la grammaire :
I0= {[Z→·S, #], [S→·CC,#], [C→·cC, c/b], [C→·d, c/d]}
I1 = GOTO (I0, S) = {[Z→S.]} //CA
I2 = GOTO (I0, C) = {[S→C.C, #], [C→·cC, #], [C→·d, #]}
I3 = GOTO (I0, c) = {[C→c.C, c/d], [C→·cC, c/d], [C→·d, c/d]}
I4 = GOTO (I0, d) = {[C→d., c/d]} //R3, tous les suivants de C : c et d
I5 = GOTO (I2, C) = {[S→CC.,#]} //R1, tous les suivants de S : #
I6 = GOTO (I2, c) = {[C→c.C, #], [C→·cC, #], [C→·d, #]}
I7 = GOTO (I2, d) = {[C→d., #]} //R3, tous les suivants de C : c et d
I8 = GOTO (I3, C) = {[C→cC., c/d]} //R2, tous les suivants de C : c et d
I3 = GOTO (I3, c) = {[C→c.C, c/d], [C→·cC, c/d], [C→·d, c/d]}
I4 = GOTO (I3, d) = {[C→d., c/d]} //R3, tous les suivants de C : c et d
I9 = GOTO (I6, C) = {[C→cC., #]} //R2, tous les suivants de C : c et d
I6 = GOTO (I6, c) = {[C→c.C, #], [C→·cC, #], [C→·d, #]}
I7 = GOTO (I6, d) = {[C→d., #]} //R3, tous les suivants de C : c et d
Les items de la méthode LR (1) : I0, I1, I3,…, I9
Les items de la méthodes LALR (1) : I0, I1, I2, (I3,I6), (I4,I7),(I8,I9)
La table d’analyse LALR (avec LR(1) ):
c d # S C
0 D, 36 D, 47 1 2
1 CA
2 D, 36 D, 47 5
36 D, 36 D, 47 89
47 R, 3 R, 3 R, 3
5 R, 1
89 R, 2 R, 2 R, 2
