emmesse

Je vais vous parler ici de la fusion de deux listes en une seule dans une grammaire LL.

Voici une grammaire LL pour une liste de 'd' séparés d'un 'sep', sachant que epsilon est la production vide

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
C -> d Cprim
Cprim -> sep d Cprim
      -> epsilon

Idem pour une liste S de 'i' séparés par le même séparateur 'sep'

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
S  -> i Sprim
Sprim -> sep i Sprim
      -> epsilon

Si on veut une liste éventuelle de 'd' puis une liste de 'i', on serait tenté d'ajouter le non-terminal L suivant, qui prend une liste C et une liste S, et les sépare par le séparateur sep:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
L -> C sep S | C | S
C -> d Cprim
Cprim -> sep d Cprim
      -> epsilon
S -> i Sprim
Sprim -> sep i Sprim
      -> epsilon

Et bien non:
D'une part 'sep' est dans premiers(Cprim) par la production Cprim -> sep d Cprim
et est d'autre part dans suivants(Cprim) car on a par dérivation gauche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 L => C sep S => d Cprim sep S

Ceci fait que la table d'analyse LL contient, à la ligne Cprim et à la colonne 'sep', les productions [Cprim -> sep d Cprim] et [Cprim -> epsilon ]
La table contient donc deux productions dans une même case, et ceci fait que cette grammaire est ambiguë

Voici la fusion d'une liste de d suivit par une liste de i, séparés d'un sep:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
C0 -> C
   -> epsilon
C -> d  Cprim
  -> S
Cprim -> sep C
      -> epsilon
S -> i Sprim
Sprim -> sep i Sprim
      -> epsilon

On obtient soit une liste de d suivi de la liste S, soit une liste de d, soit la liste S, ou soit la liste vide.
voici le schéma de traduction dirigé par la syntaxe (le symbole || est la concaténation d'attributs):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
C0 -> { C.h = C0.h } C { C0.s = C.s }
   -> epsilon { C0.s = C0.h }
C -> d { Cprim.h = C.h || d.s } Cprim { C.s = Cprim.s }
  -> { S.h = C.h } S { C.s = S.s }
Cprim -> sep { C.h = Cprim.h } C { Cprim.s = C.s }
      -> epsilon { Cprim.s = Cprim.h }
S -> i { Sprim.h = S.h || i.s } Sprim { S.s = Sprim.s }
Sprim -> sep i { Sprim1.h= Sprim.h || i.s } Sprim1 { Sprim.s = Sprim1.s }
      -> epsilon { Sprim.s = Sprim.h }

Ceci peut servir pour les corps d'instruction constitués de déclarations et d'une séquence d'instructions (ici le point-virgule n'indique pas la fin d'une instruction mais la séquentialité entre déclarations et instructions, entre déclarations, ou entre instructions):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
corpsopt -> corps
         -> epsilon
corps -> déclaration corpsprim
      -> séquence
corpsprim -> point-virgule corps
          -> epsilon
séquence -> instruction sequenceprim 
sequenceprim -> point-virgule instruction sequenceprim
             -> epsilon