Aide pour comprendre les first - follow - lookahead d'une grammaire LL1 et LL2
Bonjour,
Tout d'abord j'espère être dans la bonne section pour poster mon sujet, sinon je m'en excuse.
Je n'arrive pas à comprendre ce qu'est le first et follow dans les calculs des k-lookahead en Théorie des langages.
En effet, lors de certains exercices il est demandé de trouver k tel que G (la grammaire) soit LL(k).
Par exemple:
Soit une grammaire G d'axiome S':
- S' -> S$^k 0
- S -> aTb 1
- S -> ε 2
- T -> aT 3
- T -> bT 4
- T -> ε 5
Donc pour savoir k tel que G soit LL(k) on commence avec k = 0:
G n'est pas LL(0) car il y a plusieurs choix pour l'axiome S ou T.
Avec k = 1:
Pour l'axiome S il n'y a pas d'ambiguïté si le mot commence "a" on utilise la règle 1 et si le mot commence par "$" on prend la règle 2.
Pour l'axiome T, on vérifie avec les lookahead:
E0 1.lookahead (T -> aT) = first1 (aT.follow1(T)) = {a} "a" car ce qui suit directement après la flèche avec l'axiome T c'est a à la règle 3
E1 1.lookahead (T -> bT) = first1 (bT.follow1(T)) = {b} "b" car ce qui suit directement après la flèche avec l'axiome T c'est b à la règle 3
E2 1.lookahead (T -> ε) = first1 (ε.follow1(T)) = {b} "b" car comme on tombe sur ε, on regarde les follows de T dans la règle 1 et on trouve b qui suit T
Ensuite on fait l'intersection de l'ensemble est comme il n'est pas vide ( car on retrouve deux fois "b" ), on en conclu que la grammaire n'est pas LL(1).
On essaie donc avec k=2 et c'est là que ça se corse pour moi...:
E0 2.lookahead (T -> aT) = first2 (aT.follow2(T) = a.first1(T.follow2(T)) = {?} Ca commence par "a" mais après...
E1 2.lookahead (T -> bT) = first2 (bT.follow2(T) = b.first1(T.follow2(T)) = {bb, ??} "bb" car on commence par "b" et le follow de T dans la règle 1 c'est "b" ce qui nous donne "bb"
E2 2.lookahead (T -> ε) = first2 (ε.follow2(T) = {??} Je ne sais pas non plus...
J'ai du mal à comprendre et à trouver les firsts ou follows quand k=2. Je ne sais pas si on peut remonter, où on peut remonter, pourquoi...
Si vous pouvez m'expliquer clairement et simplement (car des formules avec des € N* et d'autres signes mathématiques j'en ai plein mes cours) pour que je comprenne ça serait génial ! Merci !
