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

matser

une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche

Noter ce billet
par , 22/08/2019 à 03h40 (403 Affichages)
je vais vous parler ici de la fusion de deux listes en une seule, avec la première qui peut être annulable, dans une grammaire LL.

voici une grammaire LL pour une liste associative à gauche 'A', d’éléments 'a' séparés par un séparateur 'sep', sachant que ε est la production vide
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
A  -> a A'
A' -> sep a A'
   -> ε
idem pour une liste B de 'b' séparés par le même séparateur 'sep'
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
B -> b B'
B' -> sep b B'
   -> ε
Si on veut une liste éventuelle de 'a' puis une liste de 'b', on serait tenté d'écrire:
et bien non:
d'une part 'sep' est dans premier(A') avec la production A' -> sep a A'
et est d'autre part dans suivant(A') (voir ci-dessous).
ceci fait que la table d'analyse LL contient, à la ligne A' et à la colonne 'sep', les productions [A' -> sep a A'] et [A' -> ε ]
la table contient donc deux productions dans une seule case, ce qui fait que cette grammaire est ambiguë
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
avec la production L -> A sep B, sep est un élément de suivant(A)
avec la production A -> a A', suivant(A) est inclus dans suivant(A')
on en déduit que sep est un élément de suivant(A')
pour fusionner ces deux listes, on ne va plus directement utiliser A dans sa totalité. les 'a' seront consommés un à un. En fait la liste A est convertie en liste associative à droite
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
C  -> A
A  -> a sep A
   -> B
B  -> b B'
B' -> sep b B'
   -> ε

Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog Viadeo Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog Twitter Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog Google Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog Facebook Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog Digg Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog Delicious Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog MySpace Envoyer le billet « une grammaire hors contexte LL pour une liste constituée de deux autres listes associatives à gauche » dans le blog Yahoo

Mis à jour 09/05/2020 à 03h01 par matser

Catégories
Sans catégorie

Commentaires