IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

matser

fusion de liste grammaire hors contexte LL

Noter ce billet
par , 05/12/2021 à 02h38 (880 Affichages)
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 ε est la production vide
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
C -> d D
D -> sep d D
  -> ε
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
   -> ε
Si on veut une liste éventuelle de 'd' puis une liste de 'i', on serait tenté d'écrire:
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) (voir ci-dessous).
ceci fait que la table d'analyse LL contient, à la ligne D et à la colonne 'sep', les productions [D -> sep d D] et [D -> ε ]
la table contient donc deux productions dans une même case, et ceci fait que cette grammaire est ambiguë
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
avec la production L -> C sep S, sep est un élément de suivants(C)
avec la production C -> d D, suivant(C) est inclus dans suivants(D)
comme sep est un élément de suivants(C) et que suivants(C) est inclus dans suivants(D), on en déduit
que sep est un élément de suivants(D)
voici la fusion de ces deux listes
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
C -> d R
  -> S
R -> sep C
  -> ε
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:
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
corps -> déclaration restedéclaration
      -> séquence
restedéclaration -> point-virgule corps
                 -> ε
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
8
9
Copt -> { C.h = nil } C { Copt.s = C.s }
     -> epsilon { Copt.s = nil }
C -> d { R.h = f( C.h , d.valex ) } R { C.s = R.s }
  -> S { C.s = S.s }
R -> sep { C.h = R.h } C { R.s = C.s }
  -> ε { R.s = R.h }
S -> i { Ri.h = g( i.vallex ) } Ri { S.s = Ri.s }
Ri -> sep i { Ri1.h = h( Ri.h , i.vallex ) } Ri1 { Ri.s = Ri1.s }
   -> epsilon { Ri.s = Ri.h }
Dans la dernière production, h( Ri.h , i.vallex) est une fonction mathématique h appliquée à Ri.h et i.vallex.

Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog Viadeo Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog Twitter Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog Google Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog Facebook Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog Digg Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog Delicious Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog MySpace Envoyer le billet « fusion de liste grammaire hors contexte LL » dans le blog Yahoo

Mis à jour 12/01/2022 à 07h27 par matser

Catégories
Sans catégorie

Commentaires