Scribd
Importer
43 vues3 pages

LR 0

Le document décrit la méthode de calcul de la fermeture d'un ensemble d'items par rapport à une grammaire, ainsi que la construction d'un automate LR(0) à partir de ces items. Il explique comment définir les états de l'automate, les états finaux, et comment utiliser la fonction Aller à() pour déterminer les transitions. Enfin, il présente la construction d'une table d'actions à partir de l'automate, précisant les actions à effectuer selon les états et les symboles rencontrés.

Transféré par

Hermane
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
43 vues3 pages

LR 0

Le document décrit la méthode de calcul de la fermeture d'un ensemble d'items par rapport à une grammaire, ainsi que la construction d'un automate LR(0) à partir de ces items. Il explique comment définir les états de l'automate, les états finaux, et comment utiliser la fonction Aller à() pour déterminer les transitions. Enfin, il présente la construction d'une table d'actions à partir de l'automate, précisant les actions à effectuer selon les états et les symboles rencontrés.

Transféré par

Hermane
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Definition de fermeture et Aller a():

1. Fermeture
Soit Fermeture(I), la fermeture de I a calculer par rapport a une grammaire
G.
Fermeture(I) se calcule en appliquant les regles suivantes:

• Ajouter tout item de I a fermeture(I): Fermeture(I) ← I

• Si A → α • Bβ est dans Fermeture(I) et que la production B → γ


appartient a G, alors ajouter B → •γ a Fermeture(I).
Fermeture(I) ← Fermeture(I)∪{B → •γ}

• Appliquer la seconde regle jusqu’a ce qu’aucun nouvel item ne peut etre


ajouter a Fermeture(I)

Construction de l’automate:

• Chaque etat est defini par un ou plusieurs items LR(0)

• Etat initial de l’automate est l’etat qui contient la regle S ′ → •S$ :


I0 = S ′ → •S

• Etats finaux de l’automate sont des etats qui contiennent au moins un item
LR(0) de la forme A → α•

• Les etats (et les transitions) de l’automate LR(0) se calculent en utilisant la


fonction Aller a() encore appele Go to()

1
E → E + T• I8

I6
′ + E → E + •T
E → E• T → (E•)
I1 T → •(E) I5
E → E • +T + E → E • +T
T → •id
E
id )
E ′ → •E id I4
E → •E + T
I0 E → •T T → id• E T → (E)•
(
T → •(E) I7
(
T → •id
id

T
T → (•E)
E → •E + T
I2 E → T • E → •T (
T
T → •(E)
T → •id
I3

2
Construction de la table a partir de l’autamate:

• si S ′ → S est dans l’etat Ii , ACTION[i,$] = ACCEPT

• si A → α • (A ̸= S) est dans l’etat Ii : ACTION[i,a] = reduce avec A → α


pour tout a.

• si A → X1 X2 . . . Xi • Xi+1 . . . Xn est dans l’etat Ii et qu’il y’a une transition


vers l’etat Ij par le terminal Xi+1 : ACTION[i, Xi+1 ] = shift j

• si A → X1 X2 . . . Xi • Xi+1 . . . Xn est dans l’etat Ii et qu’il y’a une transition


vers l’etat Ij par le non-terminal Xi+1 : Goto(i,Xi )

État id + ( ) $ E T
I0 d4 d3 1 2
I1 d5 acc
I2 r3 r3 r3
I3 d4 d3 6 2
I4 r5 r5 r5
I5 d4 d3 7
I6 r2 d8 r2
I7 r4 r4 r4
I8 r1 r1 r1

Vous aimerez peut-être aussi