Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Filière : SMI5 Compilation Série 3 Exercice 1 1 Ecrire une grammaire pour gén

1 Filière : SMI5 Compilation Série 3 Exercice 1 1 Ecrire une grammaire pour générer les identificateurs d’un langage comme Pascal ou C. On considérera qu’un identificateur est valide s’il commence par une lettre (majuscule ou minuscule) suivi d'un nombre quelconque (éventuellement aucun) de symboles. Ces symboles sont constitués par des lettres, des chiffres, et du caractère '_'. Sol : ID → Lettre Suite_de_symbole Suite_de_symbole → Symbole Suite_de_symbole | ε Symbole → Lettre | Chiffre | _ Lettre → a|b|c|….|z|A|B|….|Z Chifre →0|1|2|…..|9 2 Une constante de type chaîne de caractères est délimitée par des apostrophes et constituée d'un nombre quelconque de caractères. Pour permettre à une apostrophe de faire partie d'une chaîne de caractères, on double celle-ci. 2.1. Ecrire la grammaire qui permet de générer cette unité lexicale. Constante_Chaine →'Suite_de_caractère' Suite_de_caractère → Caractère Suite_de_caractère|ε Caractère → Lettre|Chiffre|"|@|..... 2.2. Construire l’automate qui permet de reconnaitre cette unité lexicale. lettre|chiffre|"|@|..... ' ' q0 q1 q2 2.3. Donner quelques lexèmes qui sont définis par cette unité lexicale. CH1= 'SMI_S5' , CH2= 'L"examen de compilation' , CH3= 'Rapport de TP' 2.4. Trouver des constantes qui ne sont pas reconnues par cette unité lexicale. CT1= 200, CT2=0,12 Exercice 2 Soit la grammaire G=(VT, VN, R,E) telle que: VT=(+,*,(,),nbr), telle que: VN=(E,T,F,E’,T’) et R=(E→TE’, E’→+TE’, E’→ε, T→FT’, T’→*FT’, T’→ε, F→(E), F→nbr). 1 Décrire le langage généré par cette grammaire Le langage génère des expressions arithmétiques. 2 Calculer les deux ensembles First et Follow pour les éléments de VN . Ensemble First : First(E)=First(TE‘)=First(T)={(,nbr} First(TE’)=First(T)={ ( ,nbr } 2 First(T)=First(FT’)=First(F)={( , nbr} First(FT’)=First(F)={( , nbr} First(F)={ ( ,nbr } (ε n’appartient pas à {( , nbr}) First(E’)= First(+TE’)={ + } , et puisque E’→ε alors First(E’)={+ , ε} First(T’)={ *,ε } Ensemble Follow : Follow(E)={ $ , ) } Follow(E’)=Follow(E)= { $ , ) } Follow(T)=First(E’\{ε })={ + }, et puisque ε appartient au First (E’) Follow(T)={+} U Follow(E)={ +,$,) } Follow(T’)=Follow(T)={ +,$,) } Follow(F)={ +,*,$,) } Exercice 3 Soit la grammaire G0 définie par les productions suivantes: S →aE|bF ; E→bE|ε ; F→aF|aG ; G→Gc|d 1 Montrer que G0 est non LL(1). G0 est non de type LL(1) car First(aF) ∩First(aG) ≠ Ø. 2 Ecrire une grammaire G1 non récursive a gauche telle que L(G1) = L(G0). S →aE|bF E→bE|ε F→aF|aG G→dG’ G’→cG’|ε 3 Ecrire une grammaire G2 factorisée a gauche telle que L(G2) = L(G1). S →aE|bF E→bE|ε F→aF’ F’→F|G G→dG’ G’→cG’|ε 4 Calculer les ensembles First(A) et Follow(A) pour les symboles A non terminaux de G2, et First() pour les parties droites des règles de G2. L’ensemble First est : First(S)= {a,b } First(E)={b,ε } First(F)={a} First(F’)=First(F)∪First(G)={a,d} First(G)={d} First(G’)={c, ε } L’ensemble Follow est : Follow(S)={$} Follow(E)={$} Follow(F)={$}∪Follow(F’)={$} Follow(F’)=Follow(F)={$} Follow(G)=Follow(F’)={$} Follow(G’)=Follow(G)={$} 3 5 Montrer que G2 est de type LL(1). First(aE)∩First(bF)=Ø E→bE| ε , on a Follow(E)∩First(bE)= Ø F’→F|G , on a First(F) ∩First(G)= Ø G’→G| ε , on a Follow(G’) ∩First(G)= Ø Exercice 4 Soit la grammaire G=(VT, VN, R,E) de l’exercice 2 1 Construire la table de transition de l’analyseur syntaxique du langage généré par la grammaire G. Numéroter les règles de production et construire la table d’analyse: 1: E→TE’, 2: E’→+TE’, 3: E’→ε, 4 : T→FT’, 5: T’→*FT’, 6: T’→ε, 7 : F→(E), 8:F→nbr. + * ( ) nbr $ E -1 -1 1 -1 1 -1 E’ 2 -1 -1 3 -1 3 T -1 -1 4 -1 4 -1 T’ 6 5 -1 6 -1 6 F -1 -1 7 -1 8 -1 2 Appliquer l’algorithme de l’AS prédictif non récursif sur la chaine suivante: CH1= nbr*(nbr+nbr)$ pile Tampon Action E$ nbr*(nbr+nbr)$ E→TE’ TE’$ nbr*(nbr+nbr)$ T→FT’ FT’E’$ nbr*(nbr+nbr)$ F→nbr nbr T’E’$ nbr*(nbr+nbr)$ Dépiler et avancer T’E’$ *(nbr+nbr)$ T’→*FT’ *FT’E’$ *(nbr+nbr)$ Dépiler et avancer FT’E’$ (nbr+nbr)$ F→(E) (E)T’E’$ (nbr+nbr)$ Dépiler et avancer E)T’E’$ nbr+nbr)$ E→TE’ TE’)T’E’$ nbr+nbr)$ T→FT’ FT’E’)T’E’$ nbr+nbr)$ F→nbr nbr T’E’)T’E’$ nbr+nbr)$ Dépiler et avancer T’E’)T’E’$ +nbr)$ T’→ε E)T’E’$ +nbr)$ E’→+TE’ +TE’)T’E’$ +nbr)$ Dépiler et avancer FT’E’)T’E’$ nbr)$ F→nbr nbr T’E’)T’E’$ nbr)$ Dépiler et avancer T’E’)T’E’$ )$ T’→ε E’)T’E’$ )$ E’→ε )T’E’$ )$ Dépiler et avancer T’E’$ $ T’→ε E’$ $ E’→ε $ $ succès 4 CH2=nbrnbr+nbr$ Pile Tampon Action E$ nbr nbr+nbr$ E→TE’ T E’$ nbr nbr+nbr$ T→FT’ F T’E’$ nbr nbr+nbr$ F→nbr nbr T’E’$ nbr nbr+nbr$ Dépiler et avancer T’E’$ nbr+nbr$ Echec uploads/Finance/ correction-de-la-serie-td3.pdf