Besoin d'aide en théorie des langages - First et Follow [Résolu]

[touftouf57]

Bonjour à tous,


Je tiens à préciser aux modérateurs que j'ai recherché le meilleur endroit pour ce message et que honnêtement je ne voyais pas ou j'aurais pu le mettre. Si ce n'est pas le bon endroit, je m'en excuse platement d'avance.

Revenons au sujet

Quelqu'un pourrait-il m'expliquer comment calculer First et Follow d'une grammaire en théorie des langages?
J'ai bien trouvé des pdf sur le web, mais j'obtiens des résultats différents sur la même grammaire.

Bien entendu j'attaque le calcul des First et Follow en ayant supprimer les improductifs et les inaccessibles de la grammaire.

Pour First: il faut bien ajouter tous les éléments terminaux (Vt) en début de production.
Pour les Follow: on utilise les règles:

• A --> alpha B beta ==> First(beta \ {epsilon} ) est inclut dans Follow(B)
• A --> alpha B ==> Follow(A) est inclut dans Follow(B)
• A --> alpha B beta avec epsilon appartenant à First(beta) ==> Follow(A) est inclut dans Follow(B)

Par exemple:

Code :

1
2
3
S --> c | ABS
A --> B | a
B --> b | epsilon

moi je trouve:

Code :

1
2
3
4
5
6
7
First(S)={a, b, c, epsilon}
First(A)={a, b, epsilon}
First(B)={b, epsilon}

Follow(S)={epsilon}
Follow(A)={a, b, c, epsilon}
Follow(B)={a, b, c, epsilon}

J'aimerais savoir si cela est correct.

Si une âme qui maitrise le sujet pouvait me donner 3 ou 4 exercices que je les fasses seul puis qu'il les corrige, cela serait tout simplement génial pour moi et pour tous ceux qui peinent sur le sujet.

Merci d'avance

[dividee]

Bonjour,

Ce n'est plus très frais pour moi, mais j'arrive à ceci:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
S → c | ABS
A → B | a
B → b | ε

First(B) = {b, ε}
First(A) = {a, b, ε}
First(S) = {a, b, c}
First(BS) = {a, b, c}         <-- utile dans le calcul de Follow(A)

Follow(S) = {$}
Follow(A) = {a, b, c}
Follow(B) = {a, b, c}

First(X) ne contiendra ε que si X peut produire la chaîne vide. Ici, ce n'est pas le cas de S, la chaîne vide n'est pas valide dans ce langage.

ε n'apparaît jamais dans Follow(X). Tu peux d'ailleurs le voir avec les règles que tu as écrites: il n'y aucun moyen d'introduire un ε avec cet algorithme...
Par contre l'ensemble Follow du symbole de départ (et éventuellement d'autres) contient toujours un marqueur de fin de chaîne ($). C'est ce qu'on m'a appris, en tout cas.
Ici, il n'est pas inclus dans Follow(A) ni Follow(B) car un A ou un B sera toujours suivi d'une production non vide (de S).

[touftouf57]

Merci dividee

Tes explications m'ont inspiré. J'ai trouvé un site sur lequel on lui donne la grammaire et lui nous fait les calculs de First Follow et Nullable.
C'est super intéressant pour faire des exos et s'assurer d'avoir bien compris la méthodologie.

Voila le site
http://www.marco-maniscalco.de/?p=246

Il faut faire gaffe au format qu'on lui passe, il n’accepte pas les caractères mathématiques (+,*,(,),...). Il suffit de les remplacer par un caractère "standard", par exemple p pour plus, f pour fois, o pour parenthèse ouvrante....)
Moi cela m'a bien servi, soit j'oubliais une règle, soit je la faisait à l'envers
par exemple: A--> B. Le follow de B contient le follow de A et non l'inverse.

Encore merci.

Je suis de toute façon toujours prêt à m'améliorer dans cette matière.

[AuraHxC]

ça me rappelle mes cours de compilation
Si tu veux bien maîtriser et aller plus loin, je te conseil ce livre : Compilateurs : principes, techniques et outils (dit le Dragon Book). Les explications et les exemples sont vraiment excellent

[lejuifnoir]

Merci beaucoup les gars, je travaille actuellement sur un logiciel de saisie de grammaire et de calcul de First. Cette partie m'a beaucoup aidé ! Je ne réfuserais pas d'autres conseils et guides !