matser

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 D
D -> sep d D
  -> 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 Ri
Ri -> sep i Ri
   -> epsilon

Si on veut une liste éventuelle de 'd' puis une liste de 'i', on serait tenté d'écrire:

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 D
D -> sep d D
  -> epsilon
S  -> i Ri
Ri -> sep i Ri
   -> epsilon

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

Code :

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

 L => C sep S => d D sep S

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

Voici la fusion de ces deux listes

Code :

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

1
2
3
4
5
C -> d  sep C
  -> S
S -> i Ri
Ri -> sep i Ri
   -> epsilon

On obtient soit une liste de d suivi de la liste S, soit une liste de d, soit la liste S.
S ne peut pas être annulable (être vide) sinon la liste pourrait se terminer par sep. C n'est donc pas annulable . Si on veut que C soit annulable, il faut utiliser un non terminal pouvant prendre la forme d'un C ou de epsilon:

Code :

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

1
2
Copt -> C
     -> epsilon

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
corps -> déclaration point-virgule corps
      -> séquence
séquence -> instruction Ri
Ri -> point-virgule instruction Ri
   -> epsilon

En reprenant les symboles Copt C d S et sep, on peut écrire le schéma de traduction dirigé par la syntaxe suivant :

Code :

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

1
2
3
4
5
6
7
Copt -> { C.h = f( Copt.h) } C { Copt.s = C.s }
     -> epsilon { Copt.s = nil }
C -> d { C1.h = g( C.h , d.unilex ) } sep  C1 { C.s = C1.s }
  ->  S { C.s = S.s }
S -> i { Ri.h = k(  S.h , i.unilex ) } Ri { S.s = Ri.s }
Ri -> sep i { Ri1.h = l( Ri.h , i.vallex ) } Ri1 { Ri.s = Ri1.s }
   -> epsilon { Ri.s = Ri.h }