Théorie des langages : Td 9 analyse ll
Télécharger PDFL3 - Langages et Compilation1
TD 9 - Analyse LL
Qu 1.On consid`ere la grammaireG=( {a,b,c},{S},S,{S→aSa|bSb|c}) .
a.Quel est le langage engendr ́e par cette grammaire ?
b.Construire la table d’analyseLL(1) de la grammaireG.
c.Simuler l’analyse pr ́edictive pour les motsbacabetbcba. En cas de succ`es, donner l’arbre d’analyse
syntaxique et la d ́erivation gauche r ́esultants.
Qu 2.Soit la grammaireG=( {a,b},{S},S,{S→aSa|bSb|ε}) .
a.Quel est le langage engendr ́e par cette grammaire ?
b.En construisant sa table d’analyse, montrer queGn’est pasLL(1).
Qu 3.Soit la grammaireG=( {;,if,(,),begin,bla,end,else},{INSTR,EXPR,BLOCK,SEQ,
REST},INSTR, P) o`u l’ensemble des r`eglesPest : INSTR→EXPR;|BLOCK|if(EXPR)BLOCK REST
EXPR→bla|ε
BLOCK→begin SEQ end
SEQ→INSTR SEQ|ε
REST→else INSTR|ε
a.Quelles sont les variables effa ̧cables ?
b.Donner la table des ensemblesPremier.
c.On note $ le terminal sp ́ecial qui marque la fin des mots `a analyser.
Donner les relations du typePremier(A)⊆Suivant(B)impliqu ́ees par les productions deGet,
pour chacune, pr ́eciser la production en jeu.
Donner les relations du typeSuivant(A)⊆Suivant(B)impliqu ́ees par les productions deGet,
pour chacune, pr ́eciser la production en jeu et le rˆole ́eventuel des variables effa ̧cables.
Donner la table des ensemblesSuivant.
d.Construire la table d’analyseLL(1) deG. Distinguer les entr ́ees qui mettent en jeu les ensembles
Suivantde celles qui mettent en jeu les ensemblesPremier.
e.Faire l’analyse du mot suivant :begin bla; ;end$
f.Peut on remplacer la productionSEQ→INSTR SEQpar la productionSEQ→SEQ INSTR?
Justifier.
g.Peut on supprimer la variableRESTen rempla ̧cant
les productionsREST→else INSTR,REST→ε,INSTR→if(EXPR)BLOCK REST
par les productionsINSTR→if(EXPR)BLOCK else INSTRetINSTR→if(EXPR)BLOCK?
Justifier.
h.Telle qu’elle est ́ecrite,Gn’accepte pas les deux mots suivants :
if(bla)bla; $ etif(bla)bla;else bla; $ .
L’id ́ee est alors de remplacer la productionINSTR→if(EXPR)BLOCK RESTpar la production
INSTR→if(EXPR)INSTR REST.
Que se passe-t-il alors pourG? Peut-on y rem ́edier ?
Qu 4.Soit la grammaireGd’axiomeDet de terminaux{int,float,;,id}d ́efinie par : D→T L
T→int|float
L→L;id|id
a.Pourquoi cette grammaire n’est pasLL(1) ?
b.Proposer une grammaireLL(1) ́equivalente et construire sa table d’analyse pour le prouver.