par , 20/02/2023 à 02h18 (6983 Affichages)
Introduction
Cet algorithme prend en entrée une grammaire non contextuelle et donne la liste des non terminaux à parcourir pour obtenir les récursivités à gauches.
Lignes d'enchaînement
Définition
Une ligne d'enchaînement est une suite de non terminaux tel que chacun de ces non terminaux, si celui-ci ne débute pas la ligne, soit l'un des premiers symboles du non terminal précédent.
Exemple de construction d'une liste de lignes d'enchaînement
Soit la grammaire suivante:
1
2
3
4
5
6
| A -> B a
A -> C b
B -> c i
C -> d e f
C -> F g
F -> f h |
Il y a deux productions qui ont A pour tête, et donnent ainsi deux lignes d'enchaînement qui commencent par A. La liste des lignes d'enchaînement est pour l'instant:
Comme le non terminal B est l'un des premiers symboles de A, on l'ajoute à une des lignes qui commencent par A, lesquelles sont identiques. De même pour le non terminal C. On a donc pour l'instant les deux lignes suivantes:
Soit la production B:
Comme c est un terminal, on ajoute rien à la première ligne se terminant par B, qui est unique.
Comme on a deux productions dont C est la tête, on prend une ligne se terminant par C, et on la duplique. On a alors les lignes:
Considérons la production
Comme d est un terminal, on ajoute rien, ici, aux ligne se terminant par C.
Dans la production suivante
Le symbole non terminal F étant l'un des premiers symboles de C, on ajoute F à l'une des lignes se terminant par C. Ces lignes sont identiques car AC a été dupliqué. On a donc la liste des enchaînements:
Dans la production suivante:
Le symbole f étant un terminal, on ajoute rien à la ligne se terminant par F.
En définitive, on a la liste des lignes d'enchaînement suivante:
Si l'opérateur ou ( "|" ) a été utilisé, on considère chaque opérande comme une production. La tête de la production est distribuée à chacune de ces production.
Si un non terminal se répète dans une ligne, on a une récursivité à gauche
l'algorithme
Nous considéreront chaque production de la grammaire les unes après les autres.
Soit la production A → B R où B est le premier symbole de la partie droite de cette production et R le reste de cette production.
Si A est absent des fins de ligne de la liste, on ajoute A en début de ligne autant de fois que A apparaît en tête de production.
Si B est un non terminal:
On cherche B dans les lignes, de la liste, se terminant par A. Si ce B est trouvé dans une de ces lignes, une récursivité à gauche a été trouvée. On supprime les premiers non terminaux différents du symbole A. On met cette ligne de côté et on la supprime de la liste.
Sinon, si B est absent de toutes les lignes se terminant par A, on ajoute B à l'une et seulement l'une de ces lignes, et on fait apparaître cette ligne autant de fois que B apparaît en tête de production.
Si B est un terminal, on supprime une ligne se terminant par A.
Les lignes misent de côté indiquent les récursivités à gauche qui ont été trouvés
un exemple
la grammaire est la suivante:
1
2
3
4
5
| S → A a
S → b
A → A c
A → S d
A → ε |
La première production est S → A a. Il y a deux productions dont la tête est S, on écrit donc deux ligne avec juste S. Le premier symbole de cette production est A. C'est un non terminal. Comme les deux lignes sont constitués d'un seul S, on ne trouvera pas de A dans ces lignes. Il y a trois productions dont la tête est A. on ajoute A au premier S et on fait apparaître 3 fois cette nouvelle ligne. La liste est alors la suivante:
pour la production suivante, S → b, b est un terminal. On supprime alors la première ligne se terminant par S. La liste est:
à la production A → A c, A est un non terminal. Il apparaît dans au moins une ligne se terminant par A. Une récursivité à gauche est détectée. On supprime au début de cette ligne les non terminaux différents de A. Cela donne une ligne ne contenant un seul A. On archive cette ligne et on la supprime de la liste. Il reste donc dans la liste les lignes suivantes:
la production suivante est A → S d. Le premier symbole est S. On le trouve dans au moins une ligne se terminant par A. La deuxième récursivité à gauche est détectée. Elle commence par S, on la garde donc telle quelle. On l'archive et il reste dans la liste:
La dernière production est A → ε. ε est un terminal. On supprime alors la première ligne se terminant par A. La liste est alors vide. On a considéré toutes les productions. L'algorithme est terminé. On a alors archivé les lignes A et S-A. Ce qui s’interprète de la sorte: Le premier A indique une récursivité directe dans la production A, et S-A une récursivité indirecte qui commence à la production S → A a puis se termine à A → S d.
un autre exemple
Voici un autre exemple avec la grammaire suivante où les non terminaux A et B sont inaccessibles:
1
2
3
4
5
6
7
8
9
| X → Y
Y → Y D
Y → Y a
Y → b
A → B
B → B d
C → c
D → D C
D → ε |
1. X → Y
X n'apparaît sur aucune ligne de la liste car elle est vide. On ajoute donc une ligne commençant par X à cette liste. Puis on ajoute Y à cette ligne. Et comme Y apparaît dans trois têtes de production, on fait apparaître trois fois cette ligne:
2. Y → Y D
La tête de cette production est Y. Nous allons donc nous occuper de la première ligne, où apparaît ce Y en fin de ligne. on considère ensuite le premier symbole de la partie droite, qui est aussi Y. Comme ce Y est déjà présent dans cette ligne, on a trouvé une récursivité à gauche. On supprime du début de la ligne les symboles différents de Y. la ligne devient Y tout court. On l'archive et on la supprime de la liste. La liste est alors:
3. Y → Y a
Comme précédemment, on a trouvé une récursivité à gauche. Seul Y est archivé car X est au début de la ligne et est différent de Y. Une ligne de la liste est supprimée. La liste est alors:
4. Y → b
la tête de production est Y. On considère une ligne se terminant par Y, puis on la supprime car b est un terminal. La liste est ainsi vide
5. A → B
La liste étant vide, on ajoute A, qui ne se trouve qu’une fois en tête de production, sur une ligne. Puis on considère le premier symbole, qui est B, et est ajouté à la ligne A. B étant présent qu'une fois en tête de production, cette ligne ne doit apparaître qu'une fois dans la liste, que voici:
6. B → B d
La tête et le premier symbole sont tous les deux B. On considère la ligne de la liste, qui est A B car elle se termine par B. B, le premier symbole, est présent dans A-B. Il y a donc récursivité à gauche. On supprime les non terminaux du début de la ligne, jusqu'à B. On a donc B seul. On l'archive et supprime cette ligne. La liste est alors vide.
7. C → c
La liste étant vide, on ajoute C à cette liste. Or 'c' est un terminal. La ligne précédemment ajoutée est supprimée. La liste est encore vide
8. D → D C
La liste est vide, D apparaît deux fois en tête de production.on ajoute donc deux lignes débutant par D. Mais D est aussi le premier symbole de la partie droite de la production. Étant présente dans au moins une des lignes, qui est constituée de D seul, on est encore face à une récursivité à gauche. La première ligne commençant par D, elle est archivée telle quelle et supprimée de la liste.
9. D → ε
ε est un terminal. La ligne se terminant par D est supprimée. La liste est vide et on a utilisé toutes les productions.
l'archive est (Y;Y;B;D). Ces quatre éléments n'ont qu'un symbole. Il s'agit donc de récursivités à gauches immédiates. Deux en Y, une en B et une en D
Consulter le profil
Marquer ce blog comme lu
